Java HashSet 查找复杂度？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6574916/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
HashSet look-up complexity?
提问by phoenix
A look-up operation OR containsfor single can be O(n)in worst-case right ? So, for nelements look up in hashSetwill be O(n^2)?
在最坏的情况下contains，单个的查找操作 OR可能是O(n)对的？那么，对于n元素查找hashSet将是O(n^2)?
采纳答案by JB Nizet
Yes, but it's really the worst case: if all the elements in the HashSethave the same hash code (or a hash code leading to the same bucket). With a correctly written hashCodeand a normally distributed key sample, a lookup is O(1).
是的，但这确实是最坏的情况：如果 中的所有元素HashSet都具有相同的哈希码（或导致同一个桶的哈希码）。使用正确写入hashCode和正态分布的密钥样本，查找是 O(1)。
回答by Penkov Vladimir
lookp takes O(c)
查找需要 O(c)
c = constant value
c = 常数值
回答by krasnerocalypse
Yes, but the whole reason we have HashSets is that we encounter this worst case with very, very low probability, and it's usually much faster than the guaranteed nlogn for a heap or a (self-balancing) TreeSet, or the guaranteed n^2 for an unsorted list.
是的，但是我们拥有 HashSet 的全部原因是我们遇到这种最坏情况的概率非常非常低，而且通常比保证的堆或（自平衡）树集的 nlogn 或保证的 n^2 快得多对于未排序的列表。
