哈希算法题目：设计哈希映射

题目描述
设计一个哈希映射（HashMap），不使用任何内置哈希表库。需要实现以下功能：

• MyHashMap() 初始化映射对象
• void put(int key, int value) 向 HashMap 插入键值对。如果键已存在，则更新对应的值
• int get(int key) 返回键对应的值，如果键不存在则返回 -1
• void remove(int key) 如果键存在，则删除对应的键值对

解题过程

1. 设计基础方案

   • 哈希映射需要将键映射到存储位置，使用取模运算确定桶索引：index = key % capacity
   • 选择初始容量（如1009，质数可减少哈希冲突），每个桶存储链表处理冲突

2. 数据结构定义

   class Node:
       def __init__(self, key, value):
           self.key = key
           self.value = value
           self.next = None
   
   class MyHashMap:
       def __init__(self):
           self.capacity = 1009  # 质数容量
           self.buckets = [None] * self.capacity
   

3. put操作实现

   • 计算键的桶索引，遍历对应链表：
     • 若找到相同键，更新值
     • 若未找到，在链表头部插入新节点

   def put(self, key: int, value: int) -> None:
       index = key % self.capacity
       cur = self.buckets[index]
       while cur:
           if cur.key == key:
               cur.value = value  # 更新现有键
               return
           cur = cur.next
       new_node = Node(key, value)  # 头插法新增
       new_node.next = self.buckets[index]
       self.buckets[index] = new_node
   

4. get操作实现

   • 计算桶索引后遍历链表，找到键则返回值，否则返回-1

   def get(self, key: int) -> int:
       index = key % self.capacity
       cur = self.buckets[index]
       while cur:
           if cur.key == key:
               return cur.value
           cur = cur.next
       return -1
   

5. remove操作实现

   • 需要记录前驱节点处理链表删除：
     • 若节点是头节点，直接指向next
     • 若节点在中间，前驱节点跳过当前节点

   def remove(self, key: int) -> None:
       index = key % self.capacity
       cur = prev = self.buckets[index]
       if not cur:
           return
       if cur.key == key:  # 头节点匹配
           self.buckets[index] = cur.next
           return
       cur = cur.next
       while cur:
           if cur.key == key:
               prev.next = cur.next
               return
           prev, cur = cur, cur.next
   

6. 复杂度分析

   • 时间复杂度：平均O(1)用于插入、查找、删除，最坏O(n)当所有键哈希到同一桶
   • 空间复杂度：O(n)用于存储所有键值对

关键点总结

• 链地址法解决哈希冲突
• 质数容量提升哈希分布均匀性
• 链表操作注意头节点特殊处理