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

  • Z时代
  • 2024-01-10
  • 分类：问答

我已经看到了一些关于Java哈希图及其O(1)查找时间的有趣声明。有人可以解释为什么会这样吗？除非这些哈希图与我所购买的任何哈希算法有很大不同，否则必须始终存在包含冲突的数据集。

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

有人可以解释他们是否为 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）访问来谈论此问题

以上是 Java hashmap映射真的是O（1）吗？ 的全部内容， 来源链接： utcz.com/qa/406823.html

回到顶部