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 回答