Java hashmap真的是O（1）吗？

Question

Java hashmap真的是O（1）吗？我已经看到了一些关于SO re Java hashmaps及其O(1)查找时间的有趣声明。有人可以解释为什么会这样吗？除非这些哈希图与我买的任何哈希算法有很大的不同，否则必须始终存在包含冲突的数据集。在这种情况下，查找将是O(n)而不是O(1)。有人可以解释他们是否是 O（1），如果是，他们如何实现这一目标？

Answer 1

HashMap的一个特殊功能是，与平衡树不同，它的行为是概率性的。在这些情况下，通常最有助于谈论最坏情况事件发生概率的复杂性。对于哈希映射，当然是关于地图恰好是多么充分的碰撞的情况。碰撞很容易估计。

p _collision = n / capacity

因此，即使是适度数量的元素的哈希映射也很可能经历至少一次冲突。Big O表示法允许我们做一些更引人注目的事情。观察任何任意固定常数k。

O（n）= O（k * n）

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

p _{collision x 2} =（n / capacity）²

这要低得多。由于处理一次额外碰撞的成本与Big O性能无关，我们已经找到了一种在不实际更改算法的情况下提高性能的方法！我们可以将此概括为

p _{collision xk} =（n / capacity）^k

而现在我们可以忽略一些任意数量的碰撞，最终导致碰撞的可能性微乎其微。通过选择正确的k，您可以将概率提高到任意微小的水平，所有这些都不会改变算法的实际实现。

我们通过说哈希映射具有高概率的 O（1）访问来讨论这个问题

Answer 2

您似乎将最坏情况行为与平均情况（预期）运行时混淆。对于哈希表，前者确实是O（n）（即不使用完美的哈希），但这在实践中很少有用。

任何可靠的哈希表实现，加上一半体面的哈希，在非常小的方差范围内，在预期的情况下具有非常小的因子（实际上是2）的O（1）的检索性能。

Answer 3

在Java中，HashMap通过使用hashCode来定位存储桶。每个存储桶都是驻留在该存储桶中的项目列表。扫描项目，使用等于进行比较。添加项目时，一旦达到某个负载百分比，就会调整HashMap的大小。

因此，有时它必须与一些项目进行比较，但通常它比O（n）更接近O（1）。出于实用目的，这就是您应该知道的全部内容。