HashSet<T>.Contains如何比List<T>.Contains更快？

Question

我有一个简单的需求：我有数百万个字符串，并想测试它们是否存在于一个小集合中。对于这个集合，我在使用List<T>和HashSet<T>之间犹豫。

当需求相反时，例如您有100个字符串并需要检查它们是否存在于数百万个字符串的集合中，我完全理解HashSet<T>是最佳选择。

但在我的情况下，似乎.NET在调用HashSet<T>上的Contains时必须计算数百万个哈希值（调用GetHashCode），因此调用List<T>的Contains可能更快？

有人能解释一下这个假设是否正确吗？

- Maestro

Answer 1

对我来说，这两者似乎都不合适 - HashSet<string> 听起来可能是我认为最好的方法。

是的，.NET必须为每个字符串计算哈希码 - 问题在于是否需要像检查候选集中的每个字符串的相等性一样长时间。

对于所有性能问题，您应该进行测试而不是猜测。例如，如果所有字符串长度不同并且都很长，则Equals将便宜地针对每个候选项，而GetHashCode可能需要很长时间。但是，如果您的所有字符串都是以相同的6个字符开头的长度为10的字符串，则GetHashCode将相对便宜，但每个字符串相等性检查都必须检查所有这些公共前缀字符。哪种情况更像实际情况？您的基准测试显示了什么？您需要多快？

- Jon Skeet

---

非常好的答案！我找到了HybridDictionary类，您可以将值存储为null，使其基本上与HashSet相同。 - Maestro

@Joshua：我不会在没有一些具体性能数据的情况下使用非泛型的HybridDictionary类（它用于将键映射到值，而不仅仅是包含元素）。 List<string>和HashSet<string>对您来说都太慢了吗？请注意，HybridDictionary不知道何时转换点是有意义的 - 这取决于实际数据以及Equals与GetHashCode调用的成本如何。 - Jon Skeet

我目前使用 HashSet<string>，但有时它只包含3个值，有时则会有数千个值，因此我正在寻找类似于 HybridHashset 的东西，在项目数量大于100时自动切换。我知道它永远无法准确计算“100”，但其估计值可能已经足够好了。 - Maestro

@Joshua：你可以很容易地创建这样的东西...但是这些字符串有多长？这实际上是一个性能瓶颈吗？你的性能目标是什么，HashSet<string> 对你来说如何工作？（我可能可以提供一个例子，即使对于3个候选值，计算哈希的成本也比检查相等要低。） - Jon Skeet

这些字符串大约有20个字符长，所以也许这是一种过早优化的情况，但我想知道是否有针对这种情况的解决方案。 - Maestro

@Joshua：我已经问了几次了 - 你有检查过当前的性能吗？你的基准测试结果如何？如果你还没有得到基准测试结果，那么现在进行优化肯定为时过早。不要在没有证据的情况下进行优化。 - Jon Skeet

Answer 2

我认为字典缓存键的哈希值，并且只会计算一次您正在搜索的字符串的哈希值。我要补充一点，如果您的字符串集是静态的且很少修改，您可以更快地对不可变列表进行排序并使用Array.BinarySearch，但我可能不会这样做，因为它会使代码过于复杂（除非通过基准测试验证它比较快）。

- xanatos

---

我认为你误解了问题。问题在于我正在搜索数百万个字符串，因此无法缓存任何内容。 - Maestro

所以你的问题是：将一个字符串进行哈希处理，然后通过哈希值在100个其他字符串中搜索，还是直接比较100次进行搜索更快？你需要对其进行基准测试。我认为这个临界点并不是固定的。 - xanatos

我认为我找到了一个解决方案：HybridDictionary类，在断点处自动切换。 - Maestro

请注意，这个类是预泛型时代的。这句话显然没有什么意义，但记住它很重要。 - xanatos