data-structures - 为什么 hashmap 查找是 O(1) 即常数时间？

Question

如果我们从 Java 的角度来看，那么我们可以说 hashmap 查找需要恒定的时间。但是内部实现呢？它仍然必须通过特定的桶（匹配哪个键的哈希码）来搜索不同的匹配键。那为什么我们说哈希图查找需要恒定的时间呢？请解释。

Answer 1

在对所使用的散列函数的适当假设下，我们可以说散列表查找花费预期的 O(1) 时间（假设您使用的是标准散列方案，如线性探测或链式散列）。这意味着平均而言，哈希表执行查找的工作量最多是某个常数。

直观地说，如果你有一个“好的”散列函数，你会期望元素在整个散列表中或多或少均匀分布，这意味着每个桶中的元素数量将接近于元素数量除以数量桶。如果哈希表实现将这个数字保持在较低水平（例如，每次元素与存储桶的比率超过某个常数时添加更多存储桶），那么预期完成的工作量最终会成为选择哪个存储桶的一些基线工作量应该被扫描，然后做“不要太多”的工作来查看那里的元素，因为预期该桶中只会有恒定数量的元素。

这并不意味着哈希表保证了O(1) 的行为。事实上，在最坏的情况下，散列方案会退化，所有元素最终都会放在一个桶中，在最坏的情况下，查找需要花费时间 Θ(n)。这就是为什么设计好的散列函数很重要。

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

有趣的事实：在某些类型的哈希表（cuckoo 哈希表、动态完美哈希表）中，元素的最坏情况查找时间是 O(1)。这些哈希表通过保证每个元素只能位于几个固定位置之一来工作，插入有时会在元素周围争先恐后地试图使一切都合适。

希望这可以帮助！

Answer 2

关键在于文档中的此语句：

如果要在一个 HashMap 实例中存储许多映射，则创建具有足够大容量的映射将比让它根据需要执行自动重新散列以增加表来更有效地存储映射。

和

负载因子是哈希表在其容量自动增加之前允许达到的程度的度量。当哈希表中的条目数超过负载因子和当前容量的乘积时，对哈希表进行重新哈希（即重建内部数据结构），使哈希表的桶数大约增加一倍。

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

如果超过负载因子，内部存储桶结构实际上将被重建，从而允许get和put的摊销成本为O(1)。

请注意，如果重建内部结构，则会引入可能为 O(N) 的性能损失，因此在摊销成本再次接近 O(1)之前可能需要进行相当多的get和put 。出于这个原因，适当地规划初始容量和负载系数，这样您既不会浪费空间，也不会触发可避免的内部结构重建。

Answer 3

哈希表不是 O(1)。

通过鸽巢原理，您无法比 O(log(n)) 更好地进行查找，因为您需要每个项目的 log(n) 位来唯一标识 n 个项目。

哈希表似乎是 O(1)，因为它们有一个小的常数因子，加上它们在 O(log(n)) 中的“n”被增加到这样的程度，对于许多实际应用，它与实际的数量无关您正在使用的物品。然而，大 O 表示法并不关心这个事实，而且它是（公认的，荒谬的普遍）滥用该表示法来调用哈希表 O(1)。

因为虽然您可以在哈希表中存储一百万或十亿个项目，并且仍然获得与单个项目哈希表相同的查找时间......如果您正在获取大约非十亿或 googleplex 项目，您将失去该能力。您永远不会真正使用 nonillion 或 googleplex 项目的事实对于大 O 表示法并不重要。

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

基本上，现实世界的计算机使每个数组查找大小小于其芯片位大小的数组与其最大的理论上可用的数组一样糟糕，并且由于 hastables 是在数组上执行的巧妙技巧，这就是为什么你似乎得到 O(1)

Answer 4

还要跟进 templatetypedef 的评论：

哈希表的恒定时间实现可以是哈希图，您可以使用它实现一个布尔数组列表，该列表指示特定元素是否存在于存储桶中。然而，如果你正在为你的 hashmap 实现一个链表，最坏的情况是需要你遍历每个存储桶并且必须遍历列表的末端。