java - Java hashmap 搜索真的是 O(1) 吗？

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

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

谁能解释他们是否是 O(1)，如果是，他们是如何做到的？

最佳答案

HashMap 的一个特殊特性是与平衡树不同，它的行为是概率性的。在这些情况下，根据最坏情况事件发生的概率来讨论复杂性通常是最有帮助的。对于 HashMap ，这当然是关于映射恰好有多满的冲突的情况。碰撞很容易估计。

p_collision = n / capacity

因此，即使元素数量不多的 HashMap 也很可能至少会发生一次冲突。大 O 表示法允许我们做一些更有说服力的事情。观察任意的固定常数 k。

O(n) = O(k * n)

我们可以使用这个特性来提高 HashMap 的性能。相反，我们可以考虑最多 2 次碰撞的概率。

p_{collision x 2} = (n / capacity)²

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

p_{collision x k} = (n / capacity)^k

现在我们可以忽略任意数量的碰撞，最终得到比我们所考虑的更多碰撞的可能性微乎其微。您可以通过选择正确的 k 将概率提高到任意微小的水平，而所有这些都不会改变算法的实际实现。

我们通过说 HashMap 具有 O(1) 访问权限来讨论这个问题很有可能

关于java - Java hashmap 搜索真的是 O(1) 吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1055243/