哈希算法题目：设计一个支持动态扩容的哈希表（使用链地址法） 题目描述 设计一个哈希表，支持以下操作： put(key, value) ：插入键值对。若键已存在，则更新对应的值。 get(key) ：返回键对应的值。若键不存在，返回 -1 。 remove(key) ：删除键值对。 要求： 使用 链地址法 （每个哈希桶用链表存储冲突的键值对）解决哈希冲突。 支持 动态扩容 ：当哈希表负载因子（元素数量/桶数量）超过阈值时，自动扩容至原来的2倍，并重新哈希所有元素。 确保所有操作的平均时间复杂度为 O(1) 。 解题步骤详解 步骤1：定义哈希表基本结构 使用一个数组 buckets 存储桶，每个桶是一个链表（或列表），用于存放键值对。 定义初始桶数量 initialCapacity （如4）和负载因子阈值 loadFactor （如0.75）。 维护当前元素数量 size ，用于判断是否需要扩容。 步骤2：设计哈希函数 使用简单的取模运算： hash(key) = key % bucketCount 。 注意：对负数键需先取绝对值再取模（或使用 Math.abs(key) % bucketCount ）。 步骤3：实现put操作 计算桶索引 index = hash(key) 。 遍历对应桶的链表： 若找到相同键，更新其值并返回。 若未找到，在链表末尾添加新键值对，并增加 size 。 检查负载因子：若 size / bucketCount > loadFactor ，触发扩容。 步骤4：实现扩容机制 创建新桶数组，大小为原来的2倍。 遍历旧桶的所有键值对，重新计算其在新数组中的索引（因桶数量变化，索引可能改变）。 将键值对插入新桶的链表。 用新桶数组替换旧数组。 步骤5：实现get和remove操作 get ：根据 hash(key) 找到桶，遍历链表查找键。 remove ：类似 get ，找到后删除链表节点，并减少 size 。 关键细节 链表操作优化 ： 插入新节点时可直接添加到链表头部（ O(1) ），避免遍历整个链表。 负数键处理 ： 使用 (key & 0x7FFFFFFF) % bucketCount 确保索引非负。 扩容时机 ： 在 put 操作中增加元素后判断扩容，避免扩容后仍超阈值。 示例流程 初始化：桶数量=4，阈值=0.75。 插入(1, "A")：索引=1%4=1，桶1链表添加节点。 插入(5, "B")：索引=5%4=1，与键1冲突，桶1链表变为 1→5 。 插入(9, "C")：负载因子=3/4=0.75（触发扩容）。 新桶数量=8，重新哈希： 键1：1%8=1 → 新桶1 键5：5%8=5 → 新桶5 键9：9%8=1 → 新桶1链表变为 1→9 。 总结 通过链地址法处理冲突，结合动态扩容，可在高负载下维持 O(1) 操作效率。重点在于扩容时重新哈希的均匀分布和链表操作的高效性。