散列的最壞情況時間複雜度（插入）

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)。