Java HashMap真的是O（1）吗？ [英] Is a Java hashmap really O(1)?

问题描述

我已经看到了一些关于Java的hashmaps和它们的 O（1）查找时间的有趣声明。有人可以解释为什么这样吗？除非这些hashmaps与我购买的任何哈希算法有很大的不同，否则必须始终存在一个包含冲突的数据集。

在这种情况下，查找会是 O（n）而不是 O（1）。

有人可以解释他们是否是O（1），如果是的话，他们是如何实现这一点的？

解决方案

HashMap的一个特点就是与平衡树不同，它的行为是概率性的。在这些情况下，就发生最坏情况事件的可能性而言，讨论复杂性通常最有帮助。对于哈希映射来说，这当然是碰撞情况，即映射碰巧有多完整。碰撞很容易估计。

碰撞 = n / capacity

因此，即使只有少量元素的哈希映射很可能会遇到至少一次碰撞。大O符号允许我们做更有吸引力的事情。观察到任何固定的常数k。

blockquote
O（n）= O（k * n）

我们可以使用这个特性来提高哈希映射的性能。我们可以考虑最多2次碰撞的概率。

碰撞x 2 =（n /容量） ²

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

碰撞xk =（n /容量） ^k b


$ b现在我们可以忽略一些任意数量的碰撞，并且最终碰撞的可能性比我们所考虑的要小得多。通过选择正确的k，你可以将概率提高到一个任意小的水平，所有这些都不会改变算法的实际实现。

我们通过说hash -map具有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.

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

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

解决方案

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_collision = n / capacity

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)

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_{collision x 2} = (n / capacity)²

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_{collision x k} = (n / capacity)^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.

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

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