我在SO re Java hashmaps及其O(1)次查找时间上看到了一些有趣的说法.有人能解释为什么会这样吗？除非这些散列图与我购买的任何散列算法有很大的不同，否则一定存在一个包含冲突的数据集.
在这种情况下，查找将是O(n)而不是O(1).
谁能解释一下他们是否are O(1)，如果是的话，他们是如何做到这一点的？
我在SO re Java hashmaps及其O(1)次查找时间上看到了一些有趣的说法.有人能解释为什么会这样吗？除非这些散列图与我购买的任何散列算法有很大的不同，否则一定存在一个包含冲突的数据集.
在这种情况下，查找将是O(n)而不是O(1).
谁能解释一下他们是否are O(1)，如果是的话，他们是如何做到这一点的？
HashMap的一个特殊特性是，与平衡树不同，它的行为是概率的.在这些情况下，通常用最坏情况事件发生的概率来讨论复杂性是最有帮助的.对于散列映射，这当然是关于映射碰巧有多满而发生冲突的情况.碰撞是很容易估计的.
p碰撞=n/容量
因此，一个包含少量元素的哈希映射很可能至少会遇到一次冲突.大O符号允许我们做一些更有说服力的事情.观察任意固定常数k.
O(n)=O(k*n)
我们可以使用此功能来提高哈希映射的性能.我们可以考虑最多两次碰撞的概率.
p碰撞x2=(n/容量)2
这要低得多.由于处理一次额外冲突的成本与Big O性能无关，我们找到了一种在不改变算法的情况下提高性能的方法！我们一般可以把这个
p碰撞xk=(n/容量)k
现在我们可以忽略一些任意数量的碰撞，最终得到比我们所考虑的更多碰撞的可能性微乎其微.通过 Select 正确的k，可以将概率提高到任意微小的水平，而无需改变算法的实际实现.
我们说散列映射有O(1)access with high probability