Java hashmap映射真的是O（1）吗？

Java hashmap映射真的是O（1）吗？

HashMap的一个特殊功能是与平衡树不同，它的行为是概率性的。在这些情况下，就最坏情况发生的可能性而言，谈论复杂性通常是最有帮助的。对于哈希映射，当然是在映射恰好充满的情况下发生冲突的情况。碰撞非常容易估计。

pcollision = n / capacity

因此，即使元素数量很少的哈希图也很可能会经历至少一次碰撞。大O表示法使我们可以做一些更具吸引力的事情。观察任意固定的常数k的情况。

O(n) = O(k * n)

我们可以使用此功能来改善哈希图的性能。我们可以考虑最多发生两次碰撞的可能性。

pcollision x 2 = (n / capacity)2

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

pcollision x k = (n / capacity)k

现在，我们可以忽略任意数量的冲突，并且最终产生的冲突比我们所考虑的要少得多。通过选择正确的k，您可以将概率降低到任意微小的水平，而无需改变算法的实际实现。

我们通过说哈希映射很有可能具有O（1）访问来谈论此问题