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