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

问题描述

我已经看到了一些关于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).

有人可以解释他们是否是(em)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)

我们可以使用此功能来改善哈希图的性能.相反，我们可以考虑最多发生两次碰撞的可能性.

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/容量) ²

p_{collision x 2} = (n / capacity)²

这要低得多.由于处理一次额外碰撞的成本与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

p_{collision x k} = (n / capacity)^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哈希图搜索真的是O(1)吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！