Java哈希图搜索真的是O（1）吗？

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

p_碰撞 = n / 容量

因此，即使具有适度数量的元素的哈希映射也很可能至少遇到一次冲突。Big O符号使我们能够做一些更引人注目的事情。观察，对于任何任意的、固定的常数 k。

O（n） = O（k * n）

我们可以使用此功能来提高哈希映射的性能。相反，我们可以考虑最多2次碰撞的概率。

p_{碰撞 x 2} = （n / 容量）²

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

p_{碰撞 x k} = （n / 容量）^k

现在，我们可以忽略任意数量的碰撞，最终导致碰撞的可能性微乎其微，其数量超过了我们的考虑范围。您可以通过选择正确的k将概率提高到任意小的水平，而无需改变算法的实际实现。

我们通过说哈希映射具有高概率的O（1）访问来谈论这一点

您似乎将最坏情况的行为与平均情况（预期）运行时混为一谈。前者对于一般的哈希表确实是O（n）（即不使用完美的哈希），但这在实践中很少相关。

任何可靠的哈希表实现，再加上半个体面的哈希，在预期的情况下，在非常小的方差范围内，具有非常小的因子（实际上是2）的O（1）的检索性能。