c# - HashSet<T>(IEqualityComparer<T>) 的查找时间复杂度是多少？

Question

在 C#.NET 中，我喜欢使用 HashSet，因为它们的查找时间复杂度为 O(1)。如果我要查询大量数据，我通常更喜欢使用 HashSet 而不是 List，因为它具有这样的时间复杂度。

令我困惑的是 HashSet 的构造函数，它采用 IEqualityComparer 作为参数:

http://msdn.microsoft.com/en-us/library/bb359100.aspx

在上面的链接中，注释指出“构造函数是一个 O(1) 操作”，但如果是这样的话，我很好奇查找是否仍然是 O(1)。

特别是，在我看来，如果我要编写一个比较器来传递给 HashSet 的构造函数，那么每当我执行查找时，都必须在每个键上执行比较器代码来检查以查看如果有比赛的话。这不是 O(1)，而是 O(n)。

当元素添加到集合中时，该实现是否会在内部构造一个查找表？

一般来说，我如何确定有关 .NET 数据结构复杂性的信息？

Answer 1

HashSet 通过对您插入的对象进行散列(通过 IEqualityComparer.GetHashCode)进行工作，并根据散列将对象放入存储桶中。桶本身存储在一个数组中，因此是 O(1) 部分。

例如(这不一定是 C# 实现的工作原理，它只是提供了一种 flavor )它采用哈希的第一个字符，并将哈希以 1 开头的所有内容放入存储桶 1。哈希为 2，存储桶 2 ， 等等。该存储桶内是另一个存储桶数组，它们按哈希中的第二个字符进行划分。对于哈希中的每个字符，依此类推......

现在，当您查找某些内容时，它会对其进行哈希处理，然后跳过适当的存储桶。它必须执行多次数组查找(哈希中的每个字符一次)，但不会作为 N(您添加的对象的数量)的函数而增长，因此是 O(1) 评级。

对于您的另一个问题，这里有一篇博客文章，介绍了许多集合操作的复杂性:http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html