设计一个支持动态扩容和缩容的哈希表（使用再哈希策略）

这是一个经典的哈希表设计问题，它不仅要求实现基础的增删查功能，还需要引入负载因子（load factor）作为触发条件，在表过满时自动扩容，在表过空时自动缩容。为了解决冲突，我们将采用开放地址法中的线性探测。而再哈希策略是指在扩容/缩容时，创建一个新的、大小不同的数组，并将原表中的所有键值对重新计算哈希值后插入到新表中。

下面我将循序渐进地为你讲解其设计原理、数据结构选择、关键操作步骤，以及再哈希过程。

第一步：理解核心概念与目标

1. 动态性：哈希表的大小不是固定的。当表中元素过多（即负载因子过高）时，查询、插入效率会下降，此时需要扩容。当删除大量元素后，为了节约内存，可以缩容。
2. 负载因子：这是触发扩容/缩容的关键指标。定义为 负载因子 = 已有元素数量 / 哈希表总容量。
   • 扩容阈值：通常设为 0.75。当负载因子超过 0.75，认为表太“拥挤”，冲突概率大增，需要扩容。
   • 缩容阈值：通常设为 0.25。当负载因子低于 0.25，且表容量大于某个初始最小值（如8）时，认为表太“空”，浪费空间，可以缩容。
3. 再哈希：在改变表容量后，因为哈希函数 hash(key) = key % capacity 中的 capacity 发生了变化，所有已存在键的存储位置都需要重新计算并放置到新表中。
4. 删除标记：由于我们使用线性探测法解决冲突，直接删除某个元素会在其探测路径上留下一个“空洞”，导致后续查找因遇到空洞而提前终止，误判为“不存在”。因此，我们删除一个元素时，并不是将其设为空，而是打上一个特殊的 “墓碑”标记。

第二步：设计数据结构

我们使用两个数组来实现：

1. keys：一个数组，用于存储键。每个位置可能存储一个键，也可能是 None（空位）或 TOMBSTONE（墓碑，代表已删除）。
2. values：一个数组，与 keys 一一对应，用于存储值。

初始时，我们设定一个较小的容量（例如 8），并定义扩容因子和缩容因子。

class DynamicHashTable:
    TOMBSTONE = object()  # 一个独特的对象，代表“墓碑”

    def __init__(self, initial_capacity=8, load_factor_up=0.75, load_factor_down=0.25):
        self.capacity = initial_capacity
        self.load_factor_up = load_factor_up  # 扩容阈值
        self.load_factor_down = load_factor_down  # 缩容阈值
        self.size = 0  # 当前存储的有效键值对数量
        self.keys = [None] * self.capacity
        self.values = [None] * self.capacity

第三步：实现基础辅助方法

1. 哈希函数：最简单的取模法。注意，键可能是不可哈希的类型，实际中需要处理，这里假设键是整数或字符串（可通过内置hash()函数转换）。

   def _hash(self, key):
       # 使用Python内置hash函数并取模，确保索引在数组范围内
       return hash(key) % self.capacity
   

2. 查找索引方法：这个方法是核心中的核心。它根据给定的键，返回其应该存放或已经存放的索引位置。如果找不到，则返回第一个可用的空位（None 或 TOMBSTONE）索引。

   def _find_index(self, key):
       index = self._hash(key)
       first_tombstone = -1  # 记录遍历过程中遇到的第一个墓碑位置
   
       while self.keys[index] is not None:
           if self.keys[index] == self.DELETED:
               # 遇到墓碑，记录下来
               if first_tombstone == -1:
                   first_tombstone = index
           elif self.keys[index] == key:
               # 找到了键本身
               # 如果之前遇到过墓碑，可以返回当前找到的键的位置，墓碑位置用于后续优化插入
               # 但简单实现中，我们直接返回找到的索引即可
               return index
           index = (index + 1) % self.capacity  # 线性探测，到达末尾则回到开头
   
       # 循环结束，说明遇到了None（空位）
       # 如果之前遇到过墓碑，优先返回墓碑位置，以便复用
       return first_tombstone if first_tombstone != -1 else index
   

第四步：实现基本操作（put, get, remove）

在实现基本操作时，我们暂时忽略扩容和缩容，只关注逻辑。

1. put(key, value)：
   • 调用 _find_index(key) 找到位置 idx。
   • 如果 keys[idx] 等于 key，说明是更新操作，直接覆盖 values[idx]。
   • 否则，说明是插入操作。在 keys[idx] 处放入 key，在 values[idx] 处放入 value，并将 size 加 1。
2. get(key)：
   • 调用 _find_index(key) 找到位置 idx。
   • 如果 keys[idx] 等于 key，返回 values[idx]。
   • 否则，返回 None（或抛出异常）表示未找到。
3. remove(key)：
   • 调用 _find_index(key) 找到位置 idx。
   • 如果 keys[idx] 等于 key，执行删除：将 keys[idx] 设为 TOMBSTONE，将 values[idx] 设为 None，并将 size 减 1。
   • 否则，表示键不存在。

第五步：实现再哈希与动态调整

这是本问题的核心。我们需要在 put 和 remove 操作之后，检查当前的负载因子，并决定是否触发再哈希。

1. _resize(new_capacity) 方法：

   • 创建新的 new_keys 和 new_values 数组，大小为 new_capacity。
   • 保存旧的 keys, values, capacity。
   • 将当前实例的 keys, values, capacity 指向新的空数组。
   • 关键步骤：遍历旧数组中的每一个位置。
     • 如果该位置的键既不是 None 也不是 TOMBSTONE，说明是一个有效的键值对。
     • 对这个键 重新计算哈希值（因为 capacity 变了，_hash 函数的结果也会变）。
     • 使用线性探测法，将它插入到新的 keys 和 values 数组中。
   • 注意：size 保持不变，因为只是移动了有效数据。

2. 在 put 操作中触发扩容：

   • 在 put 操作中，如果本次操作是插入（非更新），则在插入后 size 增加了。
   • 计算新的负载因子 self.size / self.capacity。
   • 如果负载因子 大于 self.load_factor_up，则调用 _resize(self.capacity * 2) 进行扩容（通常翻倍）。

3. 在 remove 操作中触发缩容：

   • 在 remove 操作成功后，size 减少了。
   • 计算新的负载因子 self.size / self.capacity。
   • 同时，为了避免在很小的表上频繁缩容，我们通常设定一个最小容量（如初始容量8）。
   • 如果负载因子 小于 self.load_factor_down 并且 self.capacity > initial_capacity，则调用 _resize(max(self.capacity // 2, initial_capacity)) 进行缩容（通常减半，但不小于初始容量）。

第六步：流程示例

假设初始容量=4，扩容阈值=0.75，缩容阈值=0.25。

1. 插入 a, b, c：
   • 插入 a, b, c 后，size=3，capacity=4，负载因子=0.75。未触发扩容（通常判断是 > 而非 >=）。
2. 插入 d：
   • 插入 d 后，size=4，负载因子=1.0 > 0.75，触发扩容。
   • 新容量 = 4 * 2 = 8。
   • 创建新的 size=8 的数组。
   • 将 a, b, c, d 四个键再哈希到新数组中。
3. 删除 a, b, c：
   • 连续删除 a, b, c 后，size=1，capacity=8，负载因子=0.125 < 0.25。
   • 当前容量8 > 初始容量4，触发缩容。
   • 新容量 = max(8 // 2, 4) = 4。
   • 创建新的 size=4 的数组。
   • 将仅剩的 d 再哈希到新数组中。

总结与关键点

• 为什么需要“墓碑”：在开放地址法中，删除元素时使用墓碑标记，是为了保持线性探测序列的连续性，避免查找失败。
• 再哈希是必须的：因为哈希函数依赖于表容量（capacity），容量改变后，所有元素的位置都必须重新计算，不能简单地复制旧数组。
• 时间复杂度：
  • 理想情况下（均匀哈希，负载因子适中），put, get, remove 的摊还时间复杂度为 O(1)。虽然单次再哈希是 O(n) 的，但它发生的频率足够低，平摊到每次操作上仍然是常数时间。
  • 最坏情况（所有键都冲突）是 O(n)。
• 设计权衡：
  • 扩容/缩容因子：阈值设置是空间和时间之间的权衡。较高的扩容因子（如0.9）节省内存但增加冲突；较低的因子（如0.5）提高效率但浪费空间。
  • 探测方法：我们使用了最简单的线性探测。二次探测或双重哈希可以减少“聚集”现象，但实现稍复杂。

通过以上步骤，你就完成了一个支持动态扩容和缩容、使用再哈希策略和线性探测的健壮哈希表。这个设计是许多编程语言（如Python字典、Java HashMap）中哈希表实现的核心思想的简化版本。