Java hashmap 搜索真的是 O(1) 吗? [英] Is a Java hashmap search really O(1)?

问题描述

我看到了一些关于 SO re Java 哈希映射及其 O(1) 查找时间的有趣声明.有人可以解释为什么会这样吗?除非这些哈希图与我购买的任何哈希算法大不相同，否则必须始终存在包含冲突的数据集.

I've seen some interesting claims on SO re Java hashmaps and their O(1) lookup time. Can someone explain why this is so? Unless these hashmaps are vastly different from any of the hashing algorithms I was bought up on, there must always exist a dataset that contains collisions.

在这种情况下，查找将是 O(n) 而不是 O(1).

In which case, the lookup would be O(n) rather than O(1).

有人可以解释他们是否 O(1)，如果是，他们是如何实现的?

Can someone explain whether they are O(1) and, if so, how they achieve this?

推荐答案

HashMap 的一个特殊功能是，与平衡树不同，它的行为是概率性的.在这些情况下，根据最坏情况发生的概率来讨论复杂性通常最有帮助.对于哈希映射，这当然是与映射恰好有多满有关的冲突的情况.碰撞很容易估计.

A particular feature of a HashMap is that unlike, say, balanced trees, its behavior is probabilistic. In these cases its usually most helpful to talk about complexity in terms of the probability of a worst-case event occurring would be. For a hash map, that of course is the case of a collision with respect to how full the map happens to be. A collision is pretty easy to estimate.

p_碰撞 = n/容量

因此，即使元素数量很少的哈希映射也很可能会遇到至少一次冲突.大 O 符号使我们能够做一些更引人注目的事情.观察任何任意的固定常数 k.

So a hash map with even a modest number of elements is pretty likely to experience at least one collision. Big O notation allows us to do something more compelling. Observe that for any arbitrary, fixed constant k.

O(n) = O(k * n)

O(n) = O(k * n)

我们可以利用这个特性来提高哈希映射的性能.相反，我们可以考虑最多发生 2 次碰撞的概率.

We can use this feature to improve the performance of the hash map. We could instead think about the probability of at most 2 collisions.

p_{碰撞 x 2} = (n/容量)²

这要低得多.由于处理一次额外碰撞的成本与 Big O 性能无关，因此我们找到了一种无需实际更改算法即可提高性能的方法！我们可以将其概括为

This is much lower. Since the cost of handling one extra collision is irrelevant to Big O performance, we've found a way to improve performance without actually changing the algorithm! We can generalzie this to

p_{碰撞 x k} = (n/容量)^k

现在我们可以忽略一些任意数量的碰撞，最终得到比我们所考虑的更多碰撞的可能性微乎其微.您可以通过选择正确的 k 将概率提高到任意微小的水平，而无需改变算法的实际实现.

And now we can disregard some arbitrary number of collisions and end up with vanishingly tiny likelihood of more collisions than we are accounting for. You could get the probability to an arbitrarily tiny level by choosing the correct k, all without altering the actual implementation of the algorithm.

我们通过说哈希映射具有 O(1) 访问高概率

We talk about this by saying that the hash-map has O(1) access with high probability

这篇关于Java hashmap 搜索真的是 O(1) 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！