哈希表的时间复杂度
我对散列表的时间复杂性感到困惑，许多文章指出它们是“平摊的O（1）”而不是真正的O（1）这在实际应用中意味着什么。 在哈希表中的操作的平均时间复杂度是多less，在实际实现中不是理论上的，为什么这些操作不是真的O（1）？
事先不可能事先知道使用散列函数会碰到多less碰撞，以及需要resize等。 这可以添加一个哈希表的性能不可预测性的元素，使其不正确O（1）。 但是，实际上所有的哈希表实现都提供了O（1）在绝大多数的插入上。 这与数组插入相同 – 除非需要resize，否则就是O（1），加上碰撞的不确定性。
在现实中，散列冲突是非常罕见的，你需要担心这些细节的唯一条件是当你的特定代码有一个非常紧凑的时间窗口，它必须运行。 对于几乎每个用例，哈希表都是O（1）。 比O（1）插入更令人印象深刻的是O（1）查找。
对于散列表的一些用途，不可能提前创build它们的“正确”大小，因为不知道在表的生命周期中需要同时保存多less个元素。 如果您想保持快速访问，则需要随着元素数目的增长而不时调整表格的大小。 这个resize的时间与表中已经存在的元素的数量相关，并且通常在插入时完成，当数字元素通过阈值时。
这些resize的操作很less会使分摊的插入成本保持不变（通过遵循表格大小的几何级数，例如每次resize时将其大小加倍）。 但是一次插入需要O（n）次，因为它会触发一个resize。
实际上，除非您正在构build实时应用程序，否则这不是问题。
在一个哈希表中插入一个值， 平均情况下，O（1）时间 。 计算散列函数，从散列表中select反投影，然后插入项目。 在最坏的情况下，所有元素都被散列到相同的值，这意味着要么遍历整个桶列表，要么在开放寻址的情况下，整个表必须被探测，直到find一个空的地方。 因此，在最坏的情况下，插入需要O（n）次
请参阅： http : //www.cs.unc.edu/~plaisted/comp550/Neyer%20paper.pdf （哈希表部分）
