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

题目描述：设计一个哈希表，支持插入（put）、删除（remove）和查找（get）操作。当哈希表的负载因子（元素数量/桶数量）超过阈值时自动扩容（例如翻倍桶数量），当负载因子低于某个阈值时自动缩容（例如减半桶数量）。扩容和缩容过程需使用再哈希策略重新分配所有元素。

解题步骤：

1. 基本结构设计

   • 使用固定大小的桶数组，每个桶存储键值对列表（链地址法解决冲突）
   • 定义负载因子阈值（如扩容阈值0.75，缩容阈值0.25）
   • 记录当前元素数量（count）和桶数量（capacity）

2. 哈希函数设计

   • 使用简单的取模运算：hash(key) = key % capacity
   • 注意：扩容/缩容后capacity变化，需重新计算所有键的哈希值

3. 插入操作（put）流程

   • 计算key的哈希值，定位到对应桶
   • 遍历桶内链表：
     • 若key已存在，更新value
     • 若key不存在，在链表末尾添加新键值对，count增加
   • 检查负载因子：若count/capacity > 扩容阈值，执行扩容操作

4. 扩容操作实现

   • 新容量为当前容量2倍，创建新桶数组
   • 遍历所有旧桶中的键值对，重新计算哈希值（使用新容量取模）
   • 将键值对移动到新桶数组的对应位置
   • 用新桶数组替换旧桶数组，更新capacity

5. 删除操作（remove）流程

   • 计算哈希值定位桶，遍历链表找到对应键值对并删除
   • count减少后检查负载因子：若count/capacity < 缩容阈值且当前容量大于初始容量，执行缩容

6. 缩容操作实现

   • 新容量为当前容量一半（但需保证不小于初始容量）
   • 采用与扩容相同的再哈希流程重新分配元素

7. 边界情况处理

   • 缩容时设置最小容量限制（如初始容量8）
   • 空表删除操作需避免负容量
   • 再哈希过程中保持操作原子性（避免并发访问导致数据不一致）

关键点说明：

• 再哈希策略确保元素均匀分布，但扩容/缩容时性能有短暂下降
• 链地址法简单有效，但链表过长时可退化为红黑树优化
• 负载因子阈值需权衡空间效率和操作性能