当您调整哈希图的大小时，如果您正在进行线性探测，是否会保留已删除的项目

When you resize a Hashmap do you keep deleted items if you're doing linear probing

我知道您保留了这些项目，只是在使用线性探测在 HashMap 中删除它们时将它们标记为已删除。但是，当你调整 HashMap 的大小时，你是否也添加了已删除的项目？

有一个技巧可以轻松调整 HashMap 的大小——不要调整它的大小。相反，让您的 resize() 方法执行此操作：

  1. 创建第二个 HashMap，用比当前数组更大的内部数组初始化（两倍大就好）
  2. 遍历当前 HashMap 的内容，使用 HashMap 的常规 put(key,value) 方法（或任何您称之为的方法）将当前 HashMap 中的每个键值对插入新创建的 HashMap 中。 （由于您新创建的 HashMap 的内部数组比您当前的数组大得多，因此无需进一步调整大小即可保证适合）
  3. 交换当前 HashMap 和 newer/larger HashMap 的内容（如果您已将 HashMap 的内容分配为单独的堆对象，这可以像单个指针交换一样简单）
  4. 就是这样；现在你原来的 HashMap 被调整得更大了，你不必编写任何额外的调整大小逻辑来做到这一点，因为你重新使用了你已经实现的逻辑。现在可以丢弃第二个 HashMap（现在包含 older/smaller 内部数组）。

如果您在可调整大小的散列中使用这种线性探测 table，您应该对通常的调整大小规则进行一些更改。

记住目标是：

  1. 维持每次操作的预期摊销 O(1) 成本
  2. 使用的 table 个广告位绝不会少于四分之一（例如）
  3. 使用的 table 插槽永远不会超过一半（例如）

因此，当 table 填满时（在本例中为 1/2 插槽填满），您调整大小，并且：

  1. 新 table 的大小应该是 4N，其中 N 是 table.
    2. 中未删除项目的数量
  2. 只复制未删除的项目。这将使您正好有 1/4 的插槽已满。

调整 N 个未删除项目的大小需要 O(N) 时间，并且在每次调整大小之后至少需要 N 次操作才能到达下一个，这提供了 O(1) 分摊的每个操作的预期时间我们需要。

如果您的实现需要二次方或质数 table 大小，那么您可以选择最接近 4N 的大小，或者下一个更大的大小。