通过线性探测实现调整哈希表大小的时间复杂度

Question

我已经阅读了一些文章，但仍然不清楚这个问题的答案。

假设我是否需要调整通过线性探测实现的哈希表的大小（即 h(x) = ((hash(x) mod 哈希表容量) + 1) 直到找到空槽）

调整哈希表的大小（假设容量达到一定百分比或迭代当前哈希表后无法插入新元素）

假设在调整大小操作中我们将当前哈希表大小加倍，我想象所需的步骤是

1. 获取哈希表中当前数据节点
2. 创建新的列表/数组，其空元素大小为 2m（m 是调整大小之前哈希表的当前容量）
3. 对于我们存储的每个数据节点，执行插入操作（这将通过新容量计算新哈希，并使用新哈希键将旧数据节点插入到新哈希表中，这里插入的最坏情况应该是 O(n) ！？因为在最坏情况下线性探测似乎需要遍历整个哈希表条目）

第三步在我看来是一个 O(n^2) 操作，因为它迭代数据节点（最坏情况有 n 个节点），并且对于每个节点都执行 O(n) 的插入操作，这是正确的理解吗？或者此处所述的操作未优化/与标准不同！？

大多数站点都表示哈希表的插入操作是 O(n)，但我认为他们要么使用二次探测，要么使用通用哈希函数，假设调整大小后插入操作将是 O(1)。只是想在这里确认我的理解。

提前致谢！

（我还在网上发现这个实现似乎与我的理解相呼应，resize()和put()供参考) https://algs4.cs.princeton.edu/34hash/LinearProbingHashST.java

Answer 1

在调整大小的步骤 3 中，可以在 O(n) 时间内重新插入所有条目。

首先，将源表中的条目按目标桶排序。使用线性时间桶排序:-)您可以使用新数组作为所需的临时存储。

然后按照目标桶的顺序重新插入所有条目。通过记住最后的插入位置，您可以从

max(target_slot, last_insert_slot+1)

开始每次搜索（小心环绕）。这会绕过所有重叠的搜索区域。