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