使用替代比较器时，在哈希集查找中维护 O(1)？
如果我在 System.Collections.Generic 中为泛型 HashSet 定义自己的比较器，并且其运行时间为 O(1)，则为哈希集的查找时间还是O(1)？
我认为不会，因为似乎没有办法设置比较器。
If I define my own comparator for the generic HashSet<T> in System.Collections.Generic, and its runtime is O(1), is the lookup time of the hashset still O(1)?
I would think no just because there doesn't appear to be a way to set the comparator.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
常规哈希集的查找时间之所以为 O(1) 是因为它使用开放寻址将对象放入数组中，因此即使您使用自己的比较器也不会改变。
The reason that the lookup time of a regular hashset is O(1) is because it uses open addressing to place objects into the array, so that won't change even if you use your own comparator.
在最好的情况下，插入的时间复杂度为 O(1)，查找的时间复杂度为 O(1)。
在最坏的情况下，插入的时间复杂度为 O(n)，查找的时间复杂度为 O(n)。
通过良好的散列方法，一个好的比较器将有助于使真实情况更接近最好的情况而不是最糟糕的情况。
一个糟糕的比较器将会很糟糕。 （故意编写一个糟糕的比较器，为每个哈希码返回相同的值[有效，但毫无意义]，您将能够看到这种 O(n) 行为）。
一个好的比较器可能会运气不好，但在大多数情况下，实际情况足够接近 O(1)，我们可以将其视为 O(1) 而不会被引导到很远的地方。
编辑：
错过了关于“无法设置比较器”的部分。 HashSet 有一个构造函数，它需要一个。
In its best case it will have a insertion of amortised O(1) and a lookup of O(1).
In its worse case it will have an insertion of amortised O(n) and a lookup of O(n).
A good comparator will help keep the real case closer to the best case than the worse, by having a good hash method.
A bad comparator will, well be bad. (Write a deliberately bad comparator that returns the same value for every hashcode [valid, but pointless] and you will be able to see this O(n) behaviour).
A good comparator can get unlucky, but for the most part the real cases are close enough to O(1) that we can think of it as O(1) and not be steered to far away.
Edit:
Missed the bit about "there being no way to set the comparator". There is, HashSet has a constructor that takes one.