哈希算法题目：设计一个支持动态扩容的哈希表（使用再哈希策略）

题目描述
设计一个哈希表，支持以下操作：

• put(key, value)：插入键值对。若键已存在，则更新值。
• get(key)：返回键对应的值。若键不存在，返回特定错误标识。
• remove(key)：删除键值对。

要求：

1. 使用除留余数法作为哈希函数，即 hash(key) = key % capacity。
2. 使用开放地址法（线性探测）解决哈希冲突。
3. 当哈希表的负载因子（元素数量 / 容量）超过阈值（如 0.75）时，自动扩容至原容量的 2 倍，并重新哈希所有已有元素。

解题过程

步骤 1：理解动态扩容的必要性

• 哈希表的性能取决于负载因子。负载因子过高会导致冲突概率激增，操作效率下降。
• 动态扩容通过降低负载因子来减少冲突，但需在扩容时重新排列所有元素（再哈希）。

步骤 2：设计哈希表的基本结构

• 使用数组 buckets 存储键值对，每个桶初始为 null，表示空位。
• 定义关键参数：
  • capacity：当前桶的数量。
  • size：当前已存储的键值对数量。
  • loadFactor：触发扩容的阈值（如 0.75）。
• 键值对需封装为节点类，包含 key、value 和标记位（用于软删除，避免中断探测链）。

class HashNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.is_deleted = False  # 标记是否被删除

步骤 3：实现哈希函数与冲突解决

• 哈希函数：hash(key) = key % capacity。
• 线性探测：若目标桶已被占用（且键不同），则循环检查下一个桶 (index + 1) % capacity，直到找到空桶或匹配的键。

插入逻辑示例：

1. 计算 index = key % capacity。
2. 若 buckets[index] 为空或标记为已删除，直接插入。
3. 若 buckets[index] 的键与当前键相同，更新值。
4. 否则，继续探测下一个位置。

步骤 4：处理删除操作的特殊性

• 直接删除桶内容会中断线性探测的链条，导致后续元素无法被访问。
• 解决方案：使用软删除，即标记节点为已删除（is_deleted = True），但保留其在数组中。后续插入时可复用该位置。

步骤 5：实现动态扩容与再哈希

1. 当 size / capacity > loadFactor 时，触发扩容。
2. 创建新数组，容量为原容量的 2 倍。
3. 遍历原数组的所有桶，将未被删除的节点重新插入新数组（使用新容量重新计算哈希值）。
4. 替换原数组为新数组，更新 capacity。

关键细节：

• 再哈希时需忽略已标记删除的节点。
• 新数组的初始容量需为质数或 2 的幂，以保障哈希分布均匀（本题假设容量为 2 的幂）。

示例演示
假设初始容量为 4，负载因子 0.75，依次插入键 3、7、11：

1. 插入 3：3 % 4 = 3，放入桶 3。
2. 插入 7：7 % 4 = 3，桶 3 已被占用，线性探测到桶 0（(3+1)%4=0）。
3. 插入 11：11 % 4 = 3，桶 3 已占用，探测桶 0 也占用，最终放入桶 1。
4. 此时负载因子 = 3/4 = 0.75，触发扩容。新容量为 8，重新哈希键 3、7、11：
   • 3 % 8 = 3 → 桶 3
   • 7 % 8 = 7 → 桶 7
   • 11 % 8 = 3 → 桶 3 冲突，线性探测到桶 4。

扩容后分布更稀疏，后续操作冲突减少。

总结
动态扩容哈希表通过适时调整容量平衡了空间与时间效率。核心难点在于：

1. 软删除维护探测链完整性。
2. 再哈希时需遍历所有有效元素，时间复杂度为 O(n)，但均摊后仍为 O(1)。