哈希表的时间复杂度

Question

我对哈希表的时间复杂度感到困惑，许多文章都说它们的时间复杂度是"平摊O(1)"，而不是真正的O(1)，那么这在实际应用中意味着什么？在哈希表的实际实现中，操作的平均时间复杂度是多少？为什么这些操作不是真正的O(1)？

- marme

---

这个问题是相关的，尽管不完全相同：https://dev59.com/THE95IYBdhLWcg3wSsGD - Pascal Cuoq

这有助于回答插入的问题，但并没有解释其他操作的任何内容。我最感兴趣的是关于哈希表查找时间复杂度的解释。 - marme

在哈希函数的某些假设下，对于大多数哈希表实现来说，查找时间是真正的O(1)。事实上，在一些有限桶深度的实现中，它是通过设计恒定的。 - Pascal Cuoq

Answer 1

事先无法知道哈希函数会有多少次冲突，还有像需要调整大小之类的事情。这可能会给哈希表的性能增加一些不可预测性，使其不是真正的O(1)。然而，几乎所有哈希表实现在绝大多数插入操作上都提供了O(1)。这与数组插入相同-除非需要调整大小，在这种情况下，它是O(n)，再加上碰撞不确定性。

实际上，哈希冲突非常罕见，你只有在你的代码必须在非常紧的时间窗口内运行时才需要担心这些细节。对于几乎每个用例，哈希表都是O(1)。比O(1)插入更令人印象深刻的是O(1)查找。

- Puppy

---

好的，O(1)查找也适用于数组。 - Alexander Mills

Answer 2

对于一些哈希表的使用，事先无法创建“正确”大小的表格，因为不知道在表格的生命周期内需要同时保存多少元素。如果您想保持快速访问，您需要随着元素数量的增长不时地调整表格的大小。这种调整与表中已有的元素数量成线性关系，并且通常在插入时进行，当元素数量超过阈值时。

这些调整操作可以减少到足够少，使得插入的摊销成本仍然是常数（例如按照几何级数调整表格的大小，每次调整时加倍大小）。但是，偶尔的一个插入需要O(n)时间，因为它会触发调整。

实际上，这不是一个问题，除非您正在构建硬实时应用程序。

- Pascal Cuoq

---

考虑的不仅是大小，还有哈希冲突。有不同的处理方式，但无论你做什么，它都不会在O(1)时间内发生。然而，在实践中，平均情况仍然接近于O(1)，除非哈希表变得相当满。 - Jords

@Jords 我不知道 "close to O(1)" 意味着什么。此外，我非常有信心文献中提到的 "amortized O(1)" 对应于对哈希函数假设桶深度保持在一个固定限制之下的情况，因此是常数时间。因为如果没有调整大小的查找不是常数时间，那么摊销后的查找肯定也不是常数时间。 - Pascal Cuoq

Answer 3

将值插入哈希表中，平均情况下需要O(1)时间。哈希函数被计算，然后从哈希表中选择桶并插入项。在最坏的情况下，所有元素的哈希值都相同，这意味着必须遍历整个桶列表或者在开放地址法的情况下，必须探查整个表直到找到一个空位。因此，在最坏的情况下，插入需要O(n)时间。

参考：http://www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf（哈希表部分）

- Rohit Jain

---

如果是“平均情况”，那么应该写成Θ(1)（大O记号）。大O表示最坏情况。 - Paulius Liekis