哈希表的时间复杂度

Question

我对哈希表的时间复杂性感到困惑很多文章表明它们是"摊销的O(1)"而不是真正的命令O(1)这在实际应用中意味着什么.哈希表中的操作的平均时间复杂度是多少,实际实现中不是理论上的,为什么操作不正确O(1)？

Answer 1

事先不可能知道你的哈希函数会有多少冲突,以及需要调整大小的事情.这可能会为哈希表的性能添加一个不可预测的元素,使其不是真的O(1).但是,几乎所有哈希表实现都在广泛,绝大多数的插入上提供O(1).这与数组插入相同 - 它是O(1),除非您需要调整大小,在这种情况下它是O(n),加上碰撞不确定性.

实际上,哈希冲突是非常罕见的,并且您需要担心这些细节的唯一条件是当您的特定代码具有必须运行的非常紧密的时间窗口时.对于几乎每个用例,哈希表都是O(1).比O(1)插入更令人印象深刻的是O(1)查找.

Answer 2

对于哈希表的某些用途,不可能提前创建"正确"大小的那些,因为不知道在表的生命周期中需要同时保持多少个元素.如果要保持快速访问,则需要随着元素数量的增加不时调整表的大小.此调整大小相对于表中已有的元素数量需要线性时间,并且通常在数字元素超过阈值时在插入时完成.

这些调整大小操作很少能够使得累积的插入成本仍然是恒定的(通过遵循表格大小的几何级数,例如每次调整大小时的大小加倍).但是,一次插入需要花费O(n)时间,因为它会触发调整大小.

实际上,除非您正在构建硬实时应用程序,否则这不是问题.