我对哈希表的时间复杂度感到困惑，很多文章都说它们是“摊销 O(1)”而不是真正的 O(1)，这在实际应用中意味着什么。哈希表中操作的平均时间复杂度是多少（在实际实现中而不是理论上），为什么这些操作不是真正的 O(1)？
不可能提前知道哈希函数会发生多少次冲突，以及需要调整大小之类的事情。这会给哈希表的性能增加不可预测性，使其不是真正的 O(1)。然而，几乎所有哈希表实现都在大量、大量、绝大多数插入上提供 O(1)。这与数组插入相同 - 除非需要调整大小，否则为 O(1)，在这种情况下为 O(n)，加上碰撞不确定性。
实际上，哈希冲突非常罕见，您需要担心这些细节的唯一情况是当您的特定代码必须运行的时间窗口非常紧张时。对于几乎每个用例，哈希表的复杂度都是 O(1)。比 O(1) 插入更令人印象深刻的是 O(1) 查找。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
