为什么HashMap查找时间复杂度是O(1)，也就是常数时间？

Question

如果我们从Java的角度来看，那么我们可以说哈希表查找具有常数时间。但是内部实现呢？它仍然需要在特定存储桶（其键的哈希码匹配）中搜索不同的匹配键。那么为什么我们会说哈希表查找具有常数时间？请解释。

- genonymous

---

可能是重复的问题：哈希表真的可以是O（1）吗？ - Boann

Answer 1

如果哈希函数满足适当的假设，我们可以说哈希表查找需要 O(1) 的期望时间（假设您使用线性探测或链式哈希等标准哈希方案）。这意味着平均而言，哈希表进行查找所需的工作量最多是一些常数。

直观地讲，如果您有一个“好”的哈希函数，您会期望元素在哈希表中分布得更或多或少均匀，这意味着每个桶中的元素数量接近于元素数量除以桶的数量。如果哈希表实现保持此数字较低（例如每次元素与桶的比率超过某个常数时添加更多桶），那么完成的期望工作量最终变成一些基本的工作量来选择应扫描的桶，然后在那里查看元素时进行“不太多”的工作，因为期望情况下该桶中只有常数个元素。

这并不意味着哈希表具有保证的 O(1) 行为。实际上，在最坏情况下，哈希方案将退化并使所有元素都在一个桶中，导致查找在最坏情况下需要 Θ(n) 的时间。这就是为什么设计好的哈希函数非常重要。

有关更多信息，您可能需要阅读算法教科书，以了解哈希表如何支持高效查找的正式推导。这通常作为典型大学算法和数据结构课程的一部分包含在内，并且有许多优秀的在线资源。

趣闻：某些类型的哈希表（cuckoo 哈希表、动态完美哈希表）具有 最坏情况下 O(1) 元素查找时间。这些哈希表通过保证每个元素只能在几个固定位置之一中出现，并且插入时有时会打乱元素以尝试使所有内容符合规定来实现。

希望这可以帮助您!

- templatetypedef

---

感谢您提供简单明了的答案。它很好地回答了我的问题。 - genonymous

你正确地回答了如何获取值。但是桶的位置呢？我们知道对于每个键（假设哈希函数很好，为每个键生成不同的哈希值），都会创建一个表来定位桶，即链表（在Java 7之前）。我的问题是，如果有1000K个不同的键值和1000K个桶，哈希映射如何确保即使查找桶位置也能达到O(1)？希望我对问题的描述清楚。谢谢。 - Sam

@Sam，这些桶通常被存储为一个数组（可以是原始数组，也可以是一些支持高效随机访问的包装器，比如 ArrayList）。因此，在计算哈希函数后，您可以在时间复杂度 O(1)（与桶的数量无关）内跳转到正确的桶。 - templatetypedef

Answer 2

哈希表并非O(1)。

基于鸽笼原理，查找的复杂度不可能比O(log(n))更好，因为你需要log(n)个位来唯一标识n个元素。

哈希表看起来像是O(1)，因为它们的常数因子很小，再加上它们中的'O(log(n))'随着实际使用的元素数量增加而增加的程度，对于许多实际应用程序而言，它是独立于实际使用的元素数量的。然而，大 O 表示法并不关心这个事实，把哈希表称为O(1)是一种（无可非议的，但极其普遍的）误用表示法。

因为当您在讨论非常巨大的数量级（"nonillion"或"googleplex"）时，即使您可以在哈希表中存储100万、10亿个元素，仍然会失去查找相同时间的能力。实际上您永远不会真正使用那么多的哈希表元素，但对于大 O 表示法来说这一点也不重要。

实际上，哈希表的性能可能比数组查找性能慢一个常数因子。这也是O(log(n))，因为您不可能做得更好。

基本上，现实世界中的计算机对小于其内部位数的大小的数组查找进行了优化，因此即使对于最大的理论可用数组，它们的性能也与真正使用的数组一样糟糕。由于哈希表是在数组上执行的聪明技巧，这就是为什么您看起来获得O(1)的原因。

- Steven Armstrong

---

你说得对，从理论和实践的角度来看，通常可以安全地假设计算机在常数时间内可以处理Ω(log n)位。否则，像“在数组中增加索引”这样的操作就不会花费恒定的时间。虽然有一些计算模型不做这个假设（决策树模型就是一个例子），但我们通常用于推理真实计算机的模型（比如传递二分模型）都做出了（合理的）假设，即机器字长大约为log n。 - templatetypedef

Answer 3

这个关键在于文档中的这句话：

如果要在HashMap实例中存储多个映射，使用足够大的容量创建它将允许映射比让它执行必要的自动重新散列以增加表的大小更有效地存储。

和

负载因子是一个衡量哈希表被允许变得多满之前其容量自动增加的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，哈希表被重新散列（即内部数据结构被重建），以便哈希表具有大约两倍的桶数。

http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html

如果超过了负载因子（load factor），内部桶结构将会被重新构建，从而实现get和put的平摊成本（amortized cost）为O(1)。

需要注意的是，如果重新构建内部结构，那么会引入一个性能惩罚，其复杂度可能为O(N)，所以在平摊成本再次接近O(1)之前，可能需要进行相当多的get和put操作。因此，请适当规划初始容量和负载因子，以便既不浪费空间，又不触发内部结构的不必要重构。

- Eric J.

Answer 4

继续templatetypedef的评论：

哈希表的常数时间实现可以是哈希映射，通过它你可以实现一个布尔数组列表，指示特定元素是否存在于桶中。然而，如果您为哈希映射实现了一个链表，最坏情况需要您遍历每个桶并穿越列表的末尾。

- jim-zed-li