我对哈希表的时间复杂度感到困惑,许多文章都说它们的时间复杂度是"平摊O(1)",而不是真正的O(1),那么这在实际应用中意味着什么?在哈希表的实际实现中,操作的平均时间复杂度是多少?为什么这些操作不是真正的O(1)?
我对哈希表的时间复杂度感到困惑,许多文章都说它们的时间复杂度是"平摊O(1)",而不是真正的O(1),那么这在实际应用中意味着什么?在哈希表的实际实现中,操作的平均时间复杂度是多少?为什么这些操作不是真正的O(1)?
事先无法知道哈希函数会有多少次冲突,还有像需要调整大小之类的事情。这可能会给哈希表的性能增加一些不可预测性,使其不是真正的O(1)。然而,几乎所有哈希表实现在绝大多数插入操作上都提供了O(1)。这与数组插入相同-除非需要调整大小,在这种情况下,它是O(n),再加上碰撞不确定性。
实际上,哈希冲突非常罕见,你只有在你的代码必须在非常紧的时间窗口内运行时才需要担心这些细节。对于几乎每个用例,哈希表都是O(1)。比O(1)插入更令人印象深刻的是O(1)查找。
这些调整操作可以减少到足够少,使得插入的摊销成本仍然是常数(例如按照几何级数调整表格的大小,每次调整时加倍大小)。但是,偶尔的一个插入需要O(n)时间,因为它会触发调整。
实际上,这不是一个问题,除非您正在构建硬实时应用程序。