177

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

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

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

4

15 回答 15

140

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

p碰撞= n / 容量

因此,即使元素数量适中的哈希映射也很可能至少会发生一次冲突。大 O 表示法允许我们做一些更有说服力的事情。对于任意的固定常数 k,请注意这一点。

O(n) = O(k * n)

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

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

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

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

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

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

于 2009-06-28T17:33:11.813 回答
40

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

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

于 2009-06-28T17:09:21.127 回答
38

在 Java 中,HashMap 是如何工作的?

  • hashCode用于定位对应的桶【桶内容器模型】。
  • 每个存储桶都是驻留在该存储桶中的项目的列表(或从 Java 8 开始的树)。
  • 项目被一一扫描,equals用于比较。
  • 添加更多项目时,一旦达到某个负载百分比,就会调整 HashMap 的大小。

因此,有时它必须与几个项目进行比较,但一般来说,它更接近O(1)而不是O(n)
出于实际目的,这就是您需要知道的全部内容。

于 2009-06-28T16:54:49.367 回答
32

请记住,o(1) 并不意味着每次查找只检查单个项目 - 它意味着检查的项目的平均数量保持不变 wrt 容器中的项目数量。因此,如果在包含 100 个项目的容器中查找一个项目平均需要 4 次比较,那么在包含 10000 个项目的容器中查找一个项目也应该平均需要 4 次比较,对于任何其他数量的项目(总是有有点差异,尤其是在哈希表重新散列的点周围,以及当项目数量非常少时)。

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

于 2009-06-28T17:04:59.680 回答
21

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

你说得对O(1),严格来说,哈希映射并不是真的,因为随着元素的数量变得任意大,最终你将无法在恒定时间内搜索(并且 O 表示法是根据可以任意大)。

但它并不意味着实时复杂度是O(n)——因为没有规定桶必须作为线性列表来实现。

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

于 2015-03-28T06:25:13.197 回答
5

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

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

于 2013-08-19T23:43:43.343 回答
4

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

O 表示法是关于当 n 越来越大时会发生什么。当应用于某些算法时,它可能会产生误导,哈希表就是一个很好的例子。我们根据期望处理的元素数量来选择存储桶的数量。当 n 的大小与 b 大致相同时,查找大致是恒定时间的,但我们不能将其称为 O(1),因为 O 是根据 n → ∞ 的限制定义的。

于 2009-06-28T18:05:53.950 回答
2

我们已经确定哈希表查找的标准描述为 O(1) 是指平均情况下的预期时间,而不是严格的最坏情况下的性能。对于通过链接解决冲突的哈希表(如 Java 的哈希图),这在技术上是 O(1+α) 且具有良好的哈希函数,其中 α 是表的负载因子。只要您存储的对象数量不超过表大小的常数因子,它仍然是常数。

还解释说,严格来说,可以构造需要 O( n ) 查找任何确定性哈希函数的输入。但考虑最坏情况的预期时间也很有趣,它不同于平均搜索时间。使用链接是 O(1 + 最长链的长度),例如当 α=1 时Θ(log n / log log n )。

如果您对实现恒定时间预期的最坏情况查找的理论方法感兴趣,您可以阅读动态完美哈希,它递归地解决与另一个哈希表的冲突!

于 2009-06-28T17:42:55.077 回答
2

只有当您的散列函数非常好时,它才是 O(1)。Java 哈希表实现不能防止不良哈希函数。

添加项目时是否需要增加表格与问题无关,因为它与查找时间有关。

于 2009-06-28T18:23:29.570 回答
2

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

location = (arraylength - 1) & keyhashcode

这里 & 表示按位与运算符。

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

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

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

在 java 8 的情况下,如果大小增长到超过 8,Linked List 存储桶将被替换为 TreeMap,这将最坏情况的搜索效率降低到 O(log n)。

于 2016-12-01T16:29:22.593 回答
1

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

如果表中不存在冲突,则只需进行一次查找,因此运行时间为 O(1)。如果存在冲突,则必须进行多次查找,这会将性能降低到 O(n)。

于 2009-06-28T17:03:15.750 回答
1

这取决于您选择避免冲突的算法。如果您的实现使用单独的链接,那么最坏的情况会发生,即每个数据元素都被散列到相同的值(例如散列函数的选择不当)。在这种情况下,数据查找与链表上的线性搜索没有什么不同,即 O(n)。但是,这种情况发生的概率可以忽略不计,并且查找最佳和平均情况保持不变,即 O(1)。

于 2009-06-28T17:15:38.043 回答
1

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

于 2015-10-19T11:36:26.437 回答
0

当然,hashmap 的性能将取决于给定对象的 hashCode() 函数的质量。但是,如果实现该函数以使冲突的可能性非常低,它将具有非常好的性能(在所有可能的情况下,这并不是严格意义上的 O(1),但在大多数情况下都是如此)。

例如,Oracle JRE 中的默认实现是使用随机数(存储在对象实例中以便它不会改变 - 但它也禁用偏向锁定,但这是另一个讨论)所以发生冲突的机会是非常低。

于 2009-06-28T16:55:09.757 回答
0

除了学者,​​从实际的角度来看,HashMap 应该被认为具有无关紧要的性能影响(除非您的分析器另有说明。)

于 2009-06-28T23:26:47.640 回答