data-structures - 为什么 HashMap 查找是 O(1)，即恒定时间？

Question

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

Answer 1

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

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

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

有关更多信息，您可能需要阅读算法教科书以了解散列表为何如此高效地支持查找的形式推导。这通常包含在典型的大学算法和数据结构类(class)中，网上有很多很好的资源。

有趣的事实:有某些类型的哈希表(布谷鸟哈希表、动态完美哈希表)，其中元素的最坏情况查找时间是 O(1)。这些哈希表的工作原理是保证每个元素只能位于几个固定位置之一，插入有时会围绕元素争先恐后地尝试使所有内容都适合。

希望这可以帮助!