logo标签列表

Java中的哈希表搜索是否真的是O(1)？

javahashmapbig-otime-complexity
190

我在SO上看到一些有关Java哈希表及其O(1)查找时间的有趣说法。有人能解释下为什么会这样吗？除非这些哈希表与我曾经接触过的任何哈希算法大不相同，否则必定存在包含冲突的数据集。

如果是这样，查找时间将会是O(n)而不是O(1)。

有人能解释一下它们是否真的是O(1)，如果是，它们是如何做到的吗？

2
我知道这可能不是一个答案，但我记得维基百科有一篇关于这个话题的非常好的文章。别错过性能分析部分。 - victor hugo
32
大O符号为你正在进行的特定类型分析提供了一个上限。但仍需指明你是否感兴趣于最坏情况、平均情况等。 - Dan Homerick
15个回答
147
HashMap的一个特点是，与平衡树等数据结构不同，它的行为具有概率性。在这些情况下，通常最有帮助的方法是根据最坏情况发生的概率来讨论复杂度。对于哈希表而言，当哈希表达到一定程度满时，最坏情况就是出现碰撞。碰撞很容易估算。

p碰撞 = n / 容量

因此，即使只有少量元素的哈希表也很可能至少发生一次碰撞。大O符号允许我们做一些更具说服力的事情。注意到对于任意的、固定的常数k，都有：

O(n) = O(k * n)

我们可以利用这个特性来提高哈希表的性能。相反地，我们可以考虑最多发生2次碰撞的概率。

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

这要低得多。由于处理一个额外碰撞的成本对于大O性能来说无关紧要，我们找到了一种在不实际更改算法的情况下提高性能的方法！我们可以将其推广到：

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

现在，我们可以忽略一些任意数量的碰撞，以达到比我们考虑的更小的概率发生更多碰撞的程度。通过选择正确的k，您可以将概率降至任意小的水平，而无需更改算法的实际实现。
我们说哈希表具有O(1)访问时间，在很大程度上是成立的。
8
实际上，以上内容表明对于非极端的N值，O(log N)的影响被固定的开销所掩盖。 - Hot Licks
从技术上讲，您提供的那个数字是碰撞次数的期望值，它可以等于单个碰撞的概率。 - Simon Kuang
1
这与分摊分析类似吗？ - lostsoul29
您的概率假设了哈希码的一些良好分布。根据您的数据和hashCode方法，分布可能不利，因此您的论证可能会失败。 - Ole V.V.
1
@OleV.V. HashMap的良好性能始终取决于哈希函数的良好分布。您可以通过在输入上使用加密哈希函数来换取更好的哈希质量以获得更快的哈希速度。 - SingleNegationElimination
你在谈论碰撞，你指的是什么类型的碰撞？你能举个例子说明一下物体如何发生碰撞吗？ - DFSFOT
42

您似乎混淆了散列表最坏情况下的运行时间与平均情况（期望）下的运行时间。一般来说，（不使用完美哈希）散列表的最坏情况确实是O(n)，但在实际应用中这很少相关。

任何可靠的散列表实现，结合一个足够好的哈希函数，在期望情况下检索性能为O(1)，非常小的因子（实际上是2），方差非常窄。

8
我一直认为上限是最坏情况，但似乎我错了——你可以针对平均情况得出上限。因此，声称O(1)的人应该明确说明这是针对平均情况的。最坏情况是数据集中存在许多冲突，使其成为O(n)。现在这就有意义了。 - paxdiablo
2
你应该明确表示，当你在平均情况下使用大O符号时，你所说的是期望运行时间函数的上界，这是一个明确定义的数学函数。否则，你的回答就没有太多意义。 - ldog
1
gmatt：我不确定我理解你的反对意见：按定义，大O符号是函数的上界。因此，我还能有什么别的意思呢？ - Konrad Rudolph
3
通常在计算机文献中，您会看到大O符号表示算法的运行时间复杂度或空间复杂度的上限。在这种情况下，上限实际上是针对期望值的，而期望值本身不是函数，而是函数（随机变量）的操作符，并且实际上是一个积分（勒贝格积分）。能够限制这样的东西并不应该被视为理所当然，这并不是平凡的事情。 - ldog
39

在Java中，HashMap是如何工作的？

  • 使用hashCode定位对应的桶[在桶容器模型内]。
  • 每个桶都是一个LinkedList（或者从Java 8开始，在某些条件下是一个Balanced Red-Black Binary Tree）, 存储在该桶中的项目。
  • 使用equals进行比较，逐一扫描这些项目。
  • 当添加更多项目时，一旦达到一定的负载百分比，HashMap将被调整大小（加倍大小）。

因此，有时需要与几个项目进行比较，但通常它比O(n) / O(log n)更接近于O(1)。
对于实际目的，这就是您需要知道的全部内容。

11
既然大O标记法是用来确定算法复杂度的，那么它与O(1)的距离有多远并不重要。即使是O(n/10^100)，它仍然是O(n)。我理解你所说的效率会降低比率，但这仍然将该算法定为O(n)。 - paxdiablo
5
哈希映射分析通常是针对平均情况，其时间复杂度为O(1)（包括冲突）。在最坏情况下，可能会出现O(n)，但这种情况通常不会发生。关于差异 - O(1)意味着您可以在图表中的项目数量不同的情况下获得相同的访问时间，这通常是成立的（只要表格大小和“n”的比例良好）。 - Liran Orevi
5
值得注意的是，即使扫描桶花费了一些时间因为其中已经有一些元素，但它仍然是O(1)。只要桶具有固定的最大容量，这只是与O()分类无关的常数因子。但是如果添加了更多具有“相似”键的元素，则这些桶可能会溢出，此时就不能再保证时间复杂度为常数了。 - sth
@sth 为什么桶会有固定的最大尺寸呢？！ - Navin
34

要记住的是，o(1)并不意味着每次查找只会检查单个项 - 它意味着每个容器中平均检查的项数相对于容器中项数保持恒定。因此，如果在具有100个项目的容器中平均需要4次比较来查找一个项目，则在具有10000个项目的容器中查找一个项目也应平均需要4次比较，并且对于任何其他项目数（总会有一些变化，尤其是在哈希表重新散列的点和当项目数量非常少时）。

因此，冲突并不会阻止容器具有o(1)操作，只要每个桶中键的平均数量保持在固定的范围内。

21

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

你是对的，哈希映射不算严格的 O(1)，因为随着元素数量的任意增加，最终你将不能在常量时间内进行搜索（而O符号表示的是可以任意增大的数字）。

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

事实上，在Java 8中，一旦桶超过阈值，它们就会被实现为 TreeMaps，这使得实际时间复杂度为 O(log n)。

5

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

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

1
常量 alpha 代表什么？ - Prahalad Deshpande
在 java.util.HashMap 中，alpha 常量与构造函数中的 负载因子 参数相关。尽管不完全如此，因为 HashMap 在调整大小时选择大小的方式会使桶的数量 量化。（这种分析还假设键到桶的分布大致均匀；即它是一种 平均情况 复杂度，而不是 最坏情况 复杂度。） - Stephen C
4

如果桶的数量（称为b）保持不变（通常情况），那么查找实际上是O(n)。


随着n的增大，每个桶中的元素数量平均为n/b。如果采用了常规的冲突解决方式（例如链表），则查找是O(n/b)=O(n)。

O表示的是当n变得越来越大时会发生什么。当应用于某些算法时，它可能会误导人，哈希表就是一个例子。我们选择桶的数量基于我们期望处理的元素数量。当n与b大小相当时，查找大致上是恒定时间，但我们不能称之为O(1)，因为O是在n → ∞的极限意义下定义的。

3

HashMap中的元素被存储为链表（节点）数组。数组中的每个链表表示一个桶，用于存储一个或多个键的唯一哈希值。
在向HashMap中添加条目时，使用键的哈希码确定数组中桶的位置，类似于：

location = (arraylength - 1) & keyhashcode

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

例如：100 & "ABC".hashCode() = 64（键“ABC”的桶位置）

在get操作期间，它使用相同的方式确定键的桶位置。在最佳情况下，每个键都具有唯一的哈希码，并为每个键产生唯一的桶，在这种情况下，get方法仅花费时间来确定桶位置并检索值，这是常量O（1）。

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

在Java 8的情况下，如果大小增长到8个以上，则链表桶被TreeMap替换，这将最坏情况的搜索效率降低到O（log n）。

2
我们已经确定了哈希表查找的标准描述是O(1)，指的是平均情况下的期望时间，而不是严格的最坏情况性能。对于使用链式解决冲突的哈希表（如Java的hashmap），这在技术上是O(1+α)，其中α是表的负载因子，使用良好的哈希函数。只要存储的对象数量不超过表大小的常数倍，仍然是恒定的。
严格来说，可以构造需要任何确定性哈希函数进行O(n)次查找的输入。但考虑到最坏情况下的期望时间是有趣的，这与平均搜索时间不同。使用链接法，例如当α=1时，最坏情况下的期望时间是O(1 +最长链的长度)，例如Θ(log n / log log n)。
如果您对实现期望最坏情况下恒定时间查找的理论方法感兴趣，可以阅读有关动态完美哈希的内容，该方法使用另一个哈希表递归地解决冲突！
2

只有在哈希函数非常好的情况下，查找时间才为O(1)。Java哈希表实现并不防止使用较差的哈希函数。

无论添加项目时是否需要扩展表格都与问题无关，因为这涉及的是查找时间。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接