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

Question

在C#.NET中,我喜欢使用HashSets,因为它们的查找时间复杂度为O(1).如果我要查询大量数据,我通常更喜欢将HashSet用于List,因为它具有这种时间复杂性.

令我困惑的是HashSet的构造函数,它将IEqualityComparer作为参数:

在上面的链接中,备注注意到"构造函数是一个O(1)操作",但如果是这种情况,我很好奇,如果查找仍然是O(1).

特别是,在我看来,如果我要编写一个Comparer来传递给HashSet的构造函数,每当我执行查找时,必须在每个键上执行Comparer代码以检查是否存在一场比赛.这不是O(1),而是O(n).

当元素添加到集合中时,实现是否在内部构建查找表？

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

Answer 1

A HashSet通过散列(via IEqualityComparer.GetHashCode)您插入的对象并按照散列将对象抛存到存储桶中.桶本身存储在阵列中,因此是O(1)部分.

例如(这不一定是C#实现的工作原理,它只是给出了一种风味)它占用了哈希的第一个字符,并将带有以1开头的哈希的所有内容抛入存储桶1.哈希为2,存储桶2,等等上.在该桶中是另一个桶阵列,它们通过哈希中的第二个字符进行分配.那么对于哈希中的每个字符....

现在,当你向上看时,它会散列它,然后跳过适当的桶.它必须进行多次数组查找(哈希中每个字符一次),但不会随着N的增加而增长,N是您添加的对象数,因此是O(1)等级.

对于您的另一个问题,这是一篇博客文章,其中包含许多馆藏运作的复杂性:http://c-sharp-snippets.blogspot.com/2010/03/runtime-complexity-of-net-generic.html

总是会出现@sll散列到桶中; 如果没有碰撞,则桶中有一个项目. (7认同)
@Kirby这里的基本解释是正确的,但基于字符的哈希实现不是.事实上,只有一个数组索引操作来检索哈希码的正确桶(没有跳转); 索引计算为`hashCode%buckets.Length`. (6认同)
谢谢你,斯科特.出于某种原因,我的解释非常清楚,特别是由于有关调用的问题,"IEqualityComparer.GetHashCode".现在,这很有道理. (2认同)
...当一个项目被添加到一个非空的桶中时，在列表上有一个线性搜索来查看该项目是否已经存在，如果没有，该项目被添加到列表的末尾。对于检索，有必要对列表进行线性搜索，直到找到匹配项。这就是为什么良好的散列分布很重要的原因。如果你的散列函数是 `return 0;` 那么你的散列集将具有链表的 O(n) 性能，但由于桶的巨大数组会占用更多的内存。 (2认同)

Answer 2

如果我要编写一个Comparer来传递给HashSet的构造函数,每当我执行查找时,必须在每个键上执行Comparer代码以检查是否存在匹配.这不是O(1),而是O(n).

让我们调用您正在搜索"查询"值的值.

你能解释为什么你认为必须在每个键上执行比较器以查看它是否与查询匹配？

这种信念是错误的.(除非比较器提供的哈希码对于每个键都是相同的!)搜索算法对哈希码与查询的哈希码匹配的每个键执行相等比较器,以哈希表中的桶数为模.这就是散列表获得O(1)查找时间的方式.

当元素添加到集合中时,实现是否在内部构建查找表？

是.

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

阅读文档.

要扩展"阅读文档",在某些地方文档有点稀疏.在这种情况下,对于大多数框架程序集,您只需阅读Microsoft提供的源代码(!),即[参考源程序](http://referencesource.microsoft.com/).当然,任何未记录的内容都可能会发生变化,但在许多情况下,您可以确定一些不太可能发生变化的事实. (3认同)