Java HashMap真的是O(1)吗?

我已经看到了一些关于Java的hashps和它们的O(1)查找时间的有趣声明。 有人能解释为什么这样吗? 除非这些哈希algorithm与我所购买的任何哈希algorithm有很大的不同,否则肯定会存在一个包含冲突的数据集。

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

有人可以解释他们是否 O(1),如果是的话,他们是如何实现的?

HashMap的一个特殊之处在于,与平衡树不同,它的行为是概率的。 在这些情况下,就发生最坏情况事件的可能性而言,讨论复杂性通常是最有帮助的。 对于一个哈希映射来说,这当然是碰撞的情况下,地图碰巧有多满。 碰撞很容易估计。

碰撞 = n /容量

所以即使是less量元素的哈希映射也很可能会遇到至less一次碰撞。 大O符号可以让我们做更有说服力的事情。 观察任意的固定常数k。

O(n)= O(k * n)

我们可以使用这个特性来提高哈希映射的性能。 我们可以考虑最多2次碰撞的概率。

碰撞x 2 =(n /容量) 2

这是低得多。 由于处理一次额外碰撞的成本与大O性能无关,所以我们find了一种提高性能的方法,而不需要实际改变algorithm! 我们可以generalzie这个

p 碰撞xk =(n /容量) k

现在,我们可以忽略一些任意数量的碰撞,最终碰撞的可能性比我们所说的要小得多。 通过select正确的k,可以将概率提高到任意小的水平,而不会改变algorithm的实际实现。

我们通过说散列图具有高概率的 O(1)访问讨论这个问题

您似乎将平均情况(预期)运行时的最坏情况行为混淆在一起。 前者通常是散列表的O(n)(即不使用完美的散列),但这在实践中很less相关。

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

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

所以有时需要比较几个项目,但通常比O(n)更接近O(1)。 出于实际的目的,这就是你应该需要知道的。

请记住,o(1)并不意味着每个查找只检查一个项目 – 这意味着检查的项目的平均数量与容器中的项目数量保持不变。 因此,如果平均需要4次比较才能在100个物品的容器中find物品,则还应该平均进行4次比较,以find10000个物品的容器中的物品,并且对于任何其他数量的物品特别是在散列表重新扫描的点,以及什么时候只有很less的项目)。

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

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

你说得对,哈希映射并不是真正的O(1) ,严格地说,因为随着元素数量变得很大,最终你将无法在常量时间内进行search(并且O-notation是按照定义的数字可以得到任意大)。

但是并不是说实时复杂度是O(n) – 因为没有规则说桶必须作为线性列表来实现。

事实上,Java 8一旦超过阈值就会将存储桶实现为TreeMaps ,这使得实际时间O(log n)

如果桶的数量(称为b)保持不变(通常情况下),则查找实际上是O(n)。
当n变大时,每个桶中元素的数量平均为n / b。 如果冲突解决以一种常用的方式完成(例如链表),则查找是O(n / b)= O(n)。

O符号是关于当n越来越大时发生的事情。 应用于某些algorithm时可能会产生误导,哈希表就是一个例子。 我们根据我们期望处理的元素数量来select桶的数量。 当n与b的大小大致相同时,查找大致是恒定的,但是我们不能称之为O(1),因为O被定义为n→∞的极限。

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

如果实现设置k = n/alpha那么它是O(1+alpha) = O(1)因为alpha是一个常数。

我们已经确定,散列表查找的标准描述是O(1),是指平均情况的预期时间,而不是严格的最坏情况的性能。 对于一个散列表来解决与链接的冲突(如Java的hashmap),这在技术上是一个好的散列函数的 O(1 +α),其中α是表的加载因子。 只要您存储的对象数量不超过表格大小的常数因子,就仍然保持不变。

也有人解释说,严格来说,构buildinput需要对任何确定性散列函数进行O( n )查找。 但是考虑最坏情况的预期时间也是有趣的,这与平均search时间不同。 使用链接这是O(1 +最长链的长度),例如当α= 1时Θ(log n / log log n )。

如果您对理论上的方法感兴趣,以实现预期的最坏情况查找恒定时间,您可以阅读关于dynamic完美散列 ,它与另一个散列表recursion解决冲突!

只有你的散列函数非常好才是O(1)。 Java哈希表实现不能防止坏哈希函数。

无论您添加项目时是否需要增加表格,都与查询时间无关。

这基本上适用于大多数编程语言中的大多数哈希表实现,因为algorithm本身并不真正改变。

如果表中没有碰撞,则只需执行一次查找,因此运行时间为O(1)。 如果存在冲突,则必须进行多个查找,这会降低对O(n)的性能。

这取决于您select避免碰撞的algorithm。 如果您的实现使用单独的链接,那么在每个数据元素被哈希到相同的值(例如哈希函数的select不佳)的情况下会发生最糟糕的情况。 在这种情况下,数据查找与链接列表上的线性search(即O(n))没有区别。 然而,发生这种情况的可能性是微不足道的,查找最好,平均情况保持不变,即O(1)。

除了实际情况外,学者们认为HashMaps应该被认为具有不重要的性能影响(除非你的分析器另有告示)。

只有在理论情况下,当哈希码总是不同的,并且每个哈希码的桶也不同时,O(1)才会存在。 否则,它是恒定的顺序,即散列表的增量,其search顺序保持不变。

HashMap中的元素存储为链表(节点)的数组,数组中的每个链表都表示一个或多个键的唯一散列值的存储桶。
在HashMap中添加条目时,密钥的哈希码用于确定数组中的存储桶的位置,如下所示:

 location = (arraylength - 1) & keyhashcode 

这里&代表按位AND运算符。

例如: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

在获取操作期间,它使用相同的方式确定密钥桶的位置。 在最好的情况下,每个哈希码是唯一的,并为每个密钥产生一个独特的桶,在这种情况下,get方法只花费时间来确定桶位置并检索常量O(1)的值。

在最坏的情况下,所有密钥都具有相同的哈希码并存储在同一个桶中,这导致遍历整个列表,导致O(n)。

在java 8的情况下,如果链接列表存储区的大小增加到8以上,那么链接列表存储区被replace为TreeMap,这将最坏情况的search效率降低到O(log n)。

当然,hashmap的性能将取决于给定对象的hashCode()函数的质量。 但是,如果这个函数被实现,使得碰撞的可能性非常低,那么它将会有非常好的性能(这在每一个可能的情况下都不是严格的O(1),但是在大多数情况下)。

例如,Oracle JRE中的默认实现是使用一个随机数(存储在对象实例中以使其不会改变 – 但是也会禁用偏置locking,但是这是另一个讨论),所以碰撞的可能性是非常低。