HashSet<T>如果我为泛型in定义了自己的比较器System.Collections.Generic，并且它的运行时间为 O(1)，那么哈希集的查找时间是否仍为 O(1)？
我不认为只是因为似乎没有办法设置比较器。
问问题
631 次
2 回答
3
常规哈希集的查找时间为 O(1) 的原因是因为它使用开放寻址将对象放入数组中，因此即使您使用自己的比较器也不会改变。
于 2010-08-25T00:59:31.847 回答
1
在最好的情况下，它将插入摊销 O(1) 和查找 O(1)。
在更糟糕的情况下，它将插入摊销 O(n) 和查找 O(n)。
一个好的比较器将通过拥有一个好的散列方法来帮助保持真实情况比最差的情况更接近最好的情况。
一个糟糕的比较器会很糟糕。（写一个故意坏的比较器，为每个哈希码返回相同的值[有效，但毫无意义]，你将能够看到这个 O(n) 行为）。
一个好的比较器可能会不走运，但在大多数情况下，实际情况足够接近 O(1)，我们可以将其视为 O(1) 而不会被引导到很远的地方。
编辑：
错过了关于“无法设置比较器”的信息。有， HashSet 有一个构造函数，需要一个。
于 2010-08-25T01:06:34.483 回答