HashSet如何<T>。包含的速度比List <T> .Contains？

我有一个简单的要求：我有数百万个字符串，并且想要测试它们是否存在于一个小集合中。我对使用List<T> vs HashSet<T>这一套有疑问。HashSet如何<T>。包含的速度比List <T> .Contains？

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

但在我的情况下，似乎.NET对HashSet<T>调用Contains的时候，所以调用List<T>的Contains可能会更快，计算哈希值数百万的（调用GetHashCode）？

任何人都可以解释，如果这种假设是正确的？

2011-10-23 Muis

这些都不适合我 - 一个HashSet<string>听起来像它可能是我最好的方法。

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

根据所有性能问题，你应该真的测试这个而不是猜测。例如，如果所有字符串的长度不同并且都很长，那么Equals对每位候选人都很便宜，而GetHashCode可能需要很长时间。但是，如果所有字符串的长度均为10，并且开头的字符相同，那么GetHashCode将相当便宜，但每个字符串相等性检查都必须检查所有这些常用前缀字符。这些更像你的实际情况？你的基准测试显示了什么？ 需要多快？这是为什么？

来源

2011-10-23 16:26:56

非常好的答案！我找到了HybridDictionary类，在这里你可以将值存储为null，使它与我猜测的HashSet相同。 – Muis

@Joshua：如果没有一些具体的性能数据，我不会使用非泛型的'HybridDictionary'类（用于将键映射到值，而不仅仅用于包含元素）。 “List '和'HashSet '对你来说太慢了吗？请注意，'HybridDictionary'不知道切换点的合理位置 - 这取决于实际的数据，以及Equals vs GetHashCode调用的代价。 –

我目前使用HashSet ，但有时它包含3个值，有时它包含数千个值，所以我在寻找类似于HybridHashset的东西，例如当item-count> 100时它会自动切换。我知道它不能准确计算'100'，但估计可能会足够好。 – Muis

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

来源

2011-10-23 16:31:26 xanatos

我想你误解了这个问题。问题在于我搜索了数百万个字符串，因此无法缓存任何内容。 – Muis

所以你的问题是：散列一个字符串，并通过散列搜索100个其他字符串或通过比较它直接搜索100次更快？那么你必须对它进行基准测试。我不认为突破点是固定的。 – xanatos

我想我找到了一个解决方案：HybridDictionary类，它在切点处自动切换。 – Muis

HashSet如何<T>。包含的速度比List <T> .Contains？

回答

相关问题