Java HashMap真的是O(1)吗?

我已经看到了一些关于Java的hashmaps和它们的O(1)查找时间的有趣声明。 有人可以解释为什么这样吗? 除非这些哈希算法与我购买的任何哈希算法大不相同,否则肯定会存在包含冲突的数据集。

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

有人可以解释他们是否是O(1),如果是的话,他们是如何实现这一点的?


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

pcollision = n /容量

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

O(n)= O(k * n)

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

pcollision x 2 =(n /容量)2

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

pcollision xk =(n /容量)k

现在,我们可以忽略一些任意数量的碰撞,并最终以比我们所说的更少的碰撞可能性。 您可以通过选择正确的k来将概率提高到任意小的水平,而不会改变算法的实际实施。

我们通过说散列图具有高概率的 O(1)访问讨论这个问题


您似乎将平均情况(预期)运行时的最坏情况行为混淆在一起。 前者通常是散列表的O(n)(即不使用完美的散列),但这在实践中很少相关。

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


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

因此,有时它必须与几个项目进行比较,但通常它比O(n)更接近O(1)。 出于实用目的,这就是你应该需要知道的一切。

链接地址: http://www.djcxy.com/p/16403.html

上一篇: Is a Java hashmap really O(1)?

下一篇: Do zombies exist ... in .NET?