我对哈希表的时间复杂度感到困惑，很多文章都说它们是“摊销 O(1)”而不是真正的 O(1)，这在实际应用中意味着什么。哈希表中操作的平均时间复杂度是多少(在实际实现中而不是理论上)，为什么这些操作不是真正的 O(1)？
最佳答案
不可能提前知道哈希函数会发生多少次冲突，以及需要调整大小之类的事情。这会给哈希表的性能增加不可预测性，使其不是真正的 O(1)。然而，几乎所有哈希表实现都在大量、大量、绝大多数插入上提供 O(1)。这与数组插入相同 - 除非需要调整大小，否则为 O(1)，在这种情况下为 O(n)，加上碰撞不确定性。
实际上，哈希冲突非常罕见，您需要担心这些细节的唯一情况是当您的特定代码必须运行的时间窗口非常紧张时。对于几乎每个用例，哈希表的复杂度都是 O(1)。比 O(1) 插入更令人印象深刻的是 O(1) 查找。
关于hashtable - 哈希表的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3949217/