哈希映射设计

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

• MyHashMap() 初始化一个空的哈希映射。
• void put(int key, int value) 向哈希映射插入一个键值对。如果键已经存在，则更新对应的值。
• int get(int key) 返回键所映射的值；如果该键不存在，则返回 -1。
• void remove(int key) 如果键存在，则删除该键值对。

解题过程

1. 核心思路分析
   哈希映射的核心是使用哈希函数将键（key）映射到存储桶（bucket）的索引。由于不同的键可能映射到同一索引（哈希冲突），需要在每个存储桶内管理多个键值对。这里我们使用“数组 + 链表”的链地址法解决冲突。

2. 数据结构设计
   定义链表节点类 Node，包含键（key）、值（value）和下一个节点的指针（next）。哈希映射主结构是一个固定大小的数组（例如大小设为 1000），数组每个位置是一个链表的虚拟头节点（dummy head），方便进行链表操作。

3. 哈希函数设计
   选择简单的取模哈希函数：hash(key) = key % bucket_size。桶的数量（bucket_size）一般取质数以减少冲突，这里为简化起见，先取 1000。

4. 具体操作实现

   • 初始化：创建大小为 1000 的数组，每个元素为带虚拟头节点的空链表。
   • put 操作：
     • 计算键的哈希值，找到对应存储桶的链表。
     • 遍历链表，若找到相同键的节点，更新其值；若未找到，在链表末尾添加新节点。
   • get 操作：
     • 计算哈希值，遍历对应链表查找键。找到则返回值，否则返回 -1。
   • remove 操作：
     • 计算哈希值，遍历链表找到该键的前驱节点，然后标准链表删除操作。

5. 复杂度分析

   • 时间复杂度：平均 O(1)（假设哈希函数分布均匀，链表长度恒定），最坏 O(n)（所有键冲突到一个链表）。
   • 空间复杂度：O(n)（n 为键值对数量）。

6. 优化考虑

   • 动态扩容：当键值对数量超过阈值（如负载因子 > 0.75），可倍增桶的数量并重新哈希所有元素。
   • 链表转红黑树：在链表过长时（如长度 > 8）将链表转为红黑树，保证最坏情况下的性能。