哈希算法题目：设计哈希映射（链地址法实现）

题目描述
设计一个哈希映射（HashMap），使用链地址法解决哈希冲突。需要实现以下操作：

• put(key, value): 插入键值对，如果键已存在则更新值
• get(key): 返回键对应的值，键不存在时返回-1
• remove(key): 删除键值对

解题过程

1. 数据结构设计
哈希映射的基础结构是一个固定大小的数组（桶数组），每个数组位置存储一个链表头节点，用于处理哈希冲突（链地址法）。

• 数组大小设为质数（如769），减少哈希聚集
• 链表节点包含三个字段：key（整型）、value（整型）、next（指向下一节点）

2. 哈希函数设计
使用简单的取模哈希函数：hash(key) = key % BASE，其中BASE是桶数组大小（769）。该函数将键均匀分布到各个桶中。

3. put操作实现步骤

• 计算键的哈希值：index = key % BASE
• 遍历该桶对应的链表：
  • 若找到相同key的节点，更新其value
  • 若未找到，在链表头部插入新节点（时间复杂度O(1)）
• 示例：插入(1, 10)到大小为3的哈希表：
  1. 计算哈希值：1 % 3 = 1
  2. 在桶1的链表插入节点(1,10)

4. get操作实现步骤

• 计算哈希值确定桶位置
• 遍历链表查找key，找到返回value，否则返回-1
• 示例：查找key=1：
  1. 哈希值1 % 3 = 1
  2. 遍历桶1链表找到节点(1,10)，返回值10

5. remove操作实现步骤

• 计算哈希值定位桶
• 使用双指针遍历链表（prev和curr）：
  • 找到key时，将prev.next指向curr.next
  • 注意处理头节点删除的特殊情况
• 示例：删除key=1后，桶1链表变为空

6. 复杂度分析

• 空间复杂度：O(BASE + N)，N为键值对数量
• 时间复杂度：平均O(1)（假设哈希函数分布均匀），最坏O(N)（所有键哈希冲突）

关键细节

• 链表插入选择头插法保证O(1)时间
• 删除操作需处理头节点和非头节点两种情况
• 桶大小取质数可提升哈希分布均匀性