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

Question

我有一个简单的要求:我有数百万个字符串，并希望测试它们是否存在于一个小集合中。对于这个集合，我不确定是使用List<T>还是HashSet<T>。

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

但在我的例子中，.NET在HashSet<T>上调用Contains时似乎必须计算数百万次散列(对GetHashCode的调用)，因此调用List<T>的Contains可能会更快？

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

Answer 1

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

是的，.NET必须计算每个字符串的哈希码-问题是，这是否需要检查与候选集合中数百个字符串中的每个字符串是否相等。

根据所有性能问题，您应该对此进行真正的测试，而不是猜测。例如，如果所有的字符串都有不同的长度，并且它们都很长，那么对于每个候选者，Equals将是廉价的，并且GetHashCode可能需要很长的时间。但是，如果所有字符串都是以相同的6个字符开头的长度为10的字符串，那么GetHashCode将相当便宜，但每个字符串相等检查都必须检查所有这些常见的前缀字符。以下哪一项更符合您的实际情况？您的基准测试显示了什么？你需要多快？

Answer 2

我认为Dictionary缓存了键的散列，并且显然只会计算一次你正在搜索的字符串的散列。我要补充的是，如果您的字符串集是静态的，并且很少修改，您会发现对不可变列表进行排序并使用Array.BinarySearch会更快，但我可能不会这样做，因为这会使代码太复杂(除非我通过基准测试验证了它的速度要快得多)。