散列的最坏情况时间复杂度（插入）

Question

如果我通过将输入值重新定位到下一个空插槽来使用基本冲突处理，是否总共不需要n *（n + 1）/ 2次命中？

例如：

输入：0,0,0;

分配的大小= 3;

因此，总共需要6个命中来分配所有三个值。

我读过最糟糕的情况是O（n），但不应该是O（n^2）呢？

Answer 1

每个插入的平均值为O（1）（具有良好的散列函数和调整大小策略），但最差情况下为O（N）。所以在最坏的情况下N插入是O（N^2）。

Answer 2

平均而言，这是O(N)。

最糟糕的情况确实是O(N^2)。