设计一个哈希映射，支持操作：put(key, value)、get(key)、remove(key)，并解决哈希冲突

题目描述

你需要设计一个哈希映射（HashMap），它应该支持以下操作：

• put(key, value)：向哈希映射中插入一个键值对。如果键已经存在，则更新对应的值。
• get(key)：返回键对应的值；如果键不存在，则返回 -1。
• remove(key)：如果键存在，则删除这个键值对。

核心挑战：由于不同的键可能被哈希函数映射到同一个位置（称为“哈希冲突”），你需要实现一种策略来解决冲突，确保上述操作的正确性和效率。

解题过程循序渐进讲解

我们将采用链地址法（Separate Chaining）来解决哈希冲突。这是最常见且易于理解的方法之一。其核心思想是：哈希表的每个位置（称为“桶”或“槽”）不直接存储一个键值对，而是存储一个链表（或其他容器）。当多个键被哈希到同一个索引时，我们只需将它们都添加到该索引对应的链表中。

步骤1：确定数据结构与哈希函数

1. 底层数据结构：我们使用一个固定大小的数组，数组的每个元素是一个链表。链表中的每个节点存储键（key）、值（value）和指向下一个节点的指针。
2. 哈希函数：最简单的哈希函数是 key mod capacity，其中 capacity 是数组的大小（即桶的数量）。为了均匀分布键，我们通常选择一个质数作为初始容量，例如 769。
3. 初始设计：

   class MyHashMap:
       def __init__(self):
           # 选择一个质数作为初始容量，有助于键的均匀分布
           self.capacity = 769
           # 初始化一个数组，每个位置是一个空列表（用来模拟链表，便于操作）
           self.table = [[] for _ in range(self.capacity)]
   
       def _hash(self, key: int) -> int:
           # 哈希函数：计算键应放入哪个桶
           return key % self.capacity
   

步骤2：实现 put(key, value) 操作

1. 计算哈希值：使用哈希函数计算键 key 对应的桶索引。

2. 查找键是否存在：在对应桶的链表中，顺序查找是否已存在相同的键。

3. 插入或更新：

   • 如果找到相同键的节点，则更新该节点的值。
   • 如果没找到，则在链表末尾（或开头）添加一个新的节点，存储这个键值对。

   def put(self, key: int, value: int) -> None:
       index = self._hash(key)
       bucket = self.table[index]
       # 遍历链表，查找键是否已存在
       for node in bucket:
           if node[0] == key:
               node[1] = value  # 更新值
               return
       # 键不存在，添加新键值对
       bucket.append([key, value])
   

步骤3：实现 get(key) 操作

1. 计算哈希值：使用哈希函数计算键 key 对应的桶索引。

2. 在链表中查找：在对应桶的链表中，顺序查找键为 key 的节点。

3. 返回结果：

   • 如果找到，返回节点的值。
   • 如果没找到，返回 -1。

   def get(self, key: int) -> int:
       index = self._hash(key)
       bucket = self.table[index]
       for node in bucket:
           if node[0] == key:
               return node[1]  # 找到键，返回值
       return -1  # 键不存在
   

步骤4：实现 remove(key) 操作

1. 计算哈希值：使用哈希函数计算键 key 对应的桶索引。

2. 在链表中查找并删除：在对应桶的链表中，查找键为 key 的节点，并将其从链表中移除。

   • 由于我们使用Python列表模拟链表，可以简单地遍历并删除目标元素。

   def remove(self, key: int) -> None:
       index = self._hash(key)
       bucket = self.table[index]
       # 遍历查找要删除的键
       for i, node in enumerate(bucket):
           if node[0] == key:
               del bucket[i]  # 找到并删除该节点
               return
       # 键不存在，无需操作
   

步骤5：复杂度分析与优化考虑

• 时间复杂度：在平均情况下（假设哈希函数分布均匀，每个桶的链表长度大致相等），put、get、remove 操作的时间复杂度为 O(n/k)，其中 n 是键的总数，k 是桶的数量。当 k 足够大时，可近似为 O(1)。在最坏情况下（所有键都冲突到同一个桶），时间复杂度退化为 O(n)。
• 空间复杂度：O(n + k)，n 是存储的键值对数量，k 是桶的数量。
• 优化方向：
  • 动态扩容/缩容：当键值对数量与桶数量的比例（负载因子）超过某个阈值时，可以创建一个更大的哈希表，并重新哈希所有现有键值对，以保持操作的高效性。这是生产级哈希表（如Python的dict）的标准特性。
  • 链表优化：当链表过长时，可以将其转换为更高效的数据结构，如红黑树（Java HashMap的实现方式），以将最坏情况下的时间复杂度从 O(n) 降低到 O(log n)。

完整代码示例

class MyHashMap:

    def __init__(self):
        self.capacity = 769  # 选择一个质数作为桶的数量
        self.table = [[] for _ in range(self.capacity)]

    def _hash(self, key: int) -> int:
        return key % self.capacity

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        bucket = self.table[index]
        for node in bucket:
            if node[0] == key:
                node[1] = value
                return
        bucket.append([key, value])

    def get(self, key: int) -> int:
        index = self._hash(key)
        bucket = self.table[index]
        for node in bucket:
            if node[0] == key:
                return node[1]
        return -1

    def remove(self, key: int) -> None:
        index = self._hash(key)
        bucket = self.table[index]
        for i, node in enumerate(bucket):
            if node[0] == key:
                del bucket[i]
                return

总结

你已经成功设计了一个基于链地址法的哈希映射。它通过将哈希冲突的键值对存储在同一个桶的链表中，优雅地解决了冲突问题。这个实现提供了平均O(1)时间复杂度的基本操作，是理解哈希表工作原理的绝佳起点。如需用于生产环境，可在此基础上增加动态扩容等高级特性。