设计一个支持增量操作的哈希映射

题目描述
设计一个哈希映射（HashMap），它支持以下操作：

1. put(key, value)：插入键值对，如果键已存在，则更新对应的值。
2. get(key)：返回键对应的值，如果键不存在，则返回 -1。
3. remove(key)：如果键存在，则删除对应的键值对。
4. inc(key, delta)：如果键存在，将键对应的值增加 delta（整数，可正可负）；如果键不存在，则先将键插入，其值设为 delta。

要求所有操作的平均时间复杂度为 O(1)。
注意：你需要自己处理哈希冲突，并且不直接使用内置的哈希映射库。

解题过程

步骤 1：理解需求与核心挑战
这是一个哈希映射的变种，增加了 inc 操作。关键点是：

• 需要实现一个基础哈希映射，支持快速插入、查询、删除。
• inc 操作需要在 O(1) 时间内完成，即直接修改已存在的值，或插入新键。
• 必须自己处理哈希冲突，因此需要选择一种冲突解决策略（比如链地址法或开放寻址法）。
  这里我们使用链地址法，因为它实现简单，且能有效处理冲突。

步骤 2：选择数据结构

• 定义一个固定大小的数组（桶数组），每个桶是一个链表，链表的每个节点存储 (key, value) 对。
• 数组大小先取一个质数（例如 2069），以减少哈希冲突。
• 为了支持动态扩容（当元素过多时，可提高效率，但题目未强制要求），这里先实现固定大小版本，但保留扩容接口。

步骤 3：设计哈希函数

• 将键（整数）映射到数组索引。
• 简单方法：hash(key) = key % bucket_count，其中 bucket_count 是桶的数量。
• 注意：实际中键可能是任意类型（如字符串），但题目未明确，这里假设键为整数简化实现。
• 如果键是字符串，则需要用字符串哈希函数（如多项式滚动哈希）。

步骤 4：实现基本操作

1. 定义节点结构：

   class Node:
       def __init__(self, key, value):
           self.key = key
           self.value = value
           self.next = None
   

2. 初始化哈希映射：

   class MyHashMap:
       def __init__(self, capacity=2069):
           self.capacity = capacity
           self.buckets = [None] * capacity
   

3. 辅助方法：获取桶索引：

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

4. put 操作：

   • 计算哈希索引，找到对应桶。
   • 遍历桶链表，如果找到相同 key，更新 value；否则，在链表头部插入新节点。

   def put(self, key, value):
       idx = self._hash(key)
       if not self.buckets[idx]:
           self.buckets[idx] = Node(key, value)
       else:
           cur = self.buckets[idx]
           while cur:
               if cur.key == key:
                   cur.value = value
                   return
               if not cur.next:
                   break
               cur = cur.next
           cur.next = Node(key, value)
   

5. get 操作：

   • 计算哈希索引，遍历链表查找 key，找到返回 value，否则返回 -1。

   def get(self, key):
       idx = self._hash(key)
       cur = self.buckets[idx]
       while cur:
           if cur.key == key:
               return cur.value
           cur = cur.next
       return -1
   

6. remove 操作：

   • 同样找到桶，遍历链表，删除节点（注意处理头节点删除）。

   def remove(self, key):
       idx = self._hash(key)
       cur = self.buckets[idx]
       prev = None
       while cur:
           if cur.key == key:
               if prev:
                   prev.next = cur.next
               else:
                   self.buckets[idx] = cur.next
               return
           prev, cur = cur, cur.next
   

步骤 5：实现增量操作 inc

• 先检查 key 是否存在：用 get(key) 获取当前值。
• 如果返回值不为 -1，说明 key 存在，则新值 = 旧值 + delta。
• 如果返回 -1，说明 key 不存在，则新值 = delta。
• 调用 put(key, 新值) 插入或更新。

  def inc(self, key, delta):
      current = self.get(key)
      if current == -1:
          new_value = delta
      else:
          new_value = current + delta
      self.put(key, new_value)
  

• 注意：get 操作是 O(1) 平均时间，put 也是 O(1)，因此 inc 也是 O(1) 平均时间复杂度。

步骤 6：考虑边界情况

• 当 delta 为负数时，inc 相当于减少值。
• 如果值减少后为 0 或负数，根据题目要求，保留该值（题目未要求删除）。
• 如果键是字符串，则哈希函数需修改为字符串哈希，例如：

  def _hash_str(self, key):
      h = 0
      for c in key:
          h = (h * 31 + ord(c)) % self.capacity
      return h
  

步骤 7：优化与扩展

• 可以加入动态扩容：当元素数量超过容量的一定比例（如 70%），创建新的更大桶数组，并将所有键值对重新哈希到新数组。
• 可使用更高效的冲突解决策略，如开放寻址法，但需注意处理删除标记。

总结
本题的核心是在基本哈希映射的基础上增加一个增量操作。我们通过链地址法处理冲突，保证 put、get、remove 平均 O(1) 时间，然后利用它们实现 inc 操作。重点是理解哈希映射的内部结构，并注意键的类型处理。