Java hashmap真的是O(1)吗？

Question

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

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

有人可以解释他们是否是 O(1),如果是,他们如何实现这一目标？

Answer 1

HashMap的一个特殊功能是,与平衡树不同,它的行为是概率性的.在这些情况下,通常最有助于谈论最坏情况事件发生概率的复杂性.对于哈希映射,当然是关于地图恰好是多么充分的碰撞的情况.碰撞很容易估计.

p _collision = n/capacity

因此,即使是适度数量的元素的哈希映射也很可能经历至少一次冲突.Big O表示法允许我们做一些更引人注目的事情.观察任何任意固定常数k.

O(n)= O(k*n)

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

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

这要低得多.由于处理一次额外碰撞的成本与Big O性能无关,我们已经找到了一种在不实际更改算法的情况下提高性能的方法!我们可以将此概括为

p _{collision xk} =(n/capacity)^k

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

我们通过说哈希映射具有高概率的 O(1)访问来讨论这个问题

Answer 2

您似乎将最坏情况行为与平均情况(预期)运行时混淆.对于哈希表,前者确实是O(n)(即不使用完美的哈希),但这在实践中很少有用.

任何可靠的哈希表实现,加上一半体面的哈希,在非常小的方差范围内,在预期的情况下具有非常小的因子(实际上是2)的O(1)的检索性能.

Answer 3

在Java中,HashMap通过使用hashCode来定位存储桶.每个存储桶都是驻留在该存储桶中的项目列表.扫描项目,使用等于进行比较.添加项目时,一旦达到某个负载百分比,就会调整HashMap的大小.

因此,有时它必须与一些项目进行比较,但通常它比O(n)更接近O(1).出于实用目的,这就是您应该知道的全部内容.

Answer 4

请记住,o(1)并不意味着每个查询仅检查单个项目 - 这意味着检查的项目的平均数量与容器中的项目数量保持不变.因此,如果平均需要4次比较来查找具有100个项目的容器中的项目,则还应该平均进行4次比较以在具有10000个项目的容器中找到项目,并且对于任何其他数量的项目(总是存在方差,特别是在散列表重新散列的点附近,以及当有非常少量的项目时).

因此,只要每个桶的平均密钥数量保持在固定范围内,冲突就不会阻止容器进行o(1)操作.

Answer 5

我知道这是一个老问题,但实际上有一个新的答案.

O(1)严格来说,你是正确的,哈希映射并不是真的,因为随着元素数量变得任意大,最终你将无法在恒定时间内进行搜索(并且O-notation是根据数字来定义的得到任意大的).

但这并不意味着实时复杂性O(n)- 因为没有规则说桶必须实现为线性列表.

实际上,Java 8 TreeMaps一旦超过阈值就实现了桶,这就是实际时间O(log n).

Answer 6

O(1+n/k)其中k是桶的数量。

如果实现设置，k = n/alpha则它是一个O(1+alpha) = O(1)常量alpha。