哈希算法题目：设计一个支持动态扩容的哈希表（使用再哈希策略） 题目描述 设计一个哈希表，支持以下操作： put(key, value) ：插入键值对。若键已存在，则更新值。 get(key) ：返回键对应的值，若键不存在则返回-1。 remove(key) ：删除键值对。 要求哈希表支持动态扩容：当负载因子（元素数量/桶数量）超过阈值时，自动扩容至原大小的2倍，并重新哈希所有元素。冲突解决采用链地址法（每个桶使用链表存储元素）。扩容时需使用再哈希策略（rehashing）将旧表数据迁移到新表。 解题步骤详解 1. 基础结构设计 定义哈希表的初始容量（如4）和最大负载因子（如0.75）。 每个桶是一个链表，存储键值对节点（包含key、value和next指针）。 维护当前元素数量 size 和桶数组 buckets 。 2. 哈希函数 使用 key.hashCode() 获取哈希值，再通过取模运算定位桶索引： index = key.hashCode() % buckets.length 。 注意：取模时需处理负数（ Math.abs(index) 或使用 & (length-1) ，但后者要求容量为2的幂）。 3. put操作流程 计算key的桶索引。 遍历对应链表的节点： 若节点key与目标key相同（用 equals 判断），更新值并返回。 若未找到相同key，在链表头部插入新节点。 更新 size ，检查负载因子：若 size / buckets.length > 负载因子阈值 ，触发扩容。 4. 动态扩容与再哈希 创建新桶数组，大小为原数组的2倍。 遍历旧表每个桶的链表，对每个节点重新计算其在新表中的索引（ newIndex = key.hashCode() % newCapacity ）。 将节点插入新桶的链表头部。 注意：再哈希时需重新分配所有元素，因为桶数量变化可能导致索引改变。 5. get和remove操作 get ：计算索引后遍历链表，找到key相等的节点返回值。 remove ：类似get，但需删除节点并更新链表指针。 6. 关键细节 扩容后新阈值按新容量重新计算。 再哈希时，旧链表节点迁移到新链表后顺序会反转（因头部插入），但不影响功能。 处理空键或特殊哈希值（如负数）确保索引合法。 示例演示 假设初始容量=4，阈值=0.75，插入键值对： 插入(1, "A")：桶索引=1，负载因子=1/4=0.25。 插入(5, "B")：桶索引=1（冲突），链表变为5→1。 插入(9, "C")：桶索引=1，链表变为9→5→1，负载因子=3/4=0.75，触发扩容。 扩容至容量=8，再哈希： 键1的新索引=1%8=1，键5的新索引=5%8=5，键9的新索引=9%8=1。 新表桶1的链表变为9→1，桶5存入键5。 通过再哈希，数据均匀分布到新桶，降低未来冲突概率。