设计和实现一个支持键值对存储的微型哈希表（带动态扩容和冲突解决）

题目描述
你需要设计并实现一个简易的哈希表，它应该支持以下操作：

• put(key, value): 插入键值对。如果键已存在，则更新对应的值。
• get(key): 返回键对应的值。如果键不存在，则返回特定的表示不存在的值（例如-1）。
• remove(key): 删除键值对。
  哈希表需要能够动态扩容，以维持高效的性能。同时，你需要选择并实现一种哈希冲突解决方法。
  本题的目标是让你理解哈希表的核心机制，包括哈希函数、冲突解决、负载因子和动态扩容。我们会一步步构建，从最基础的固定大小哈希表开始，逐步加入动态扩容功能。

解题过程循序渐进讲解

第一步：确定基本结构与哈希函数
首先，我们定义一个固定大小的数组（桶数组）作为哈希表的基础存储。每个数组位置（桶）可以存储一个键值对。为了处理冲突，我们使用链地址法（每个桶是一个链表，用于存储哈希到同一位置的键值对）。

1. 选择初始容量（例如，INITIAL_CAPACITY = 4），并创建一个数组，每个元素是一个链表（在Python中可以用列表模拟，但为清晰起见，我们将定义简单的链表节点结构）。
2. 设计一个简单的哈希函数，将任意整数键映射到数组索引范围内。对于整数键，可以直接用键模数组长度：hash(key) = key % capacity。对于非整数键，我们可以先将其转换为整数（例如，用Python的hash()函数），但为简化，本题假设键为整数。

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

class MyHashMapBasic:
    def __init__(self):
        self.capacity = 4
        self.size = 0
        self.buckets = [None] * self.capacity  # 每个桶是一个链表头节点

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

现在，数组self.buckets的每个位置要么是None（空桶），要么指向一个ListNode链表。

第二步：实现基本的put、get、remove（无扩容）

1. put操作：
   • 计算哈希索引index = _hash(key)。
   • 遍历该索引处的链表，查找是否已存在相同键的节点。
     • 如果找到，更新其值。
     • 如果未找到，在链表头部插入新节点（O(1)时间）。
   • 注意：这里暂不处理扩容。

def put(self, key, value):
    index = self._hash(key)
    head = self.buckets[index]
    # 遍历链表查找键
    cur = head
    while cur:
        if cur.key == key:
            cur.value = value  # 更新
            return
        cur = cur.next
    # 键不存在，在头部插入新节点
    new_node = ListNode(key, value)
    new_node.next = head
    self.buckets[index] = new_node
    self.size += 1

2. get操作：
   • 计算哈希索引，遍历链表查找键。找到返回对应值，否则返回-1。

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

3. remove操作：
   • 计算哈希索引，遍历链表删除节点（需要维护前驱节点）。

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

至此，一个基础版哈希表完成，但它在元素增多时性能会下降，因为链表会变长。我们需要引入动态扩容。

第三步：引入负载因子和动态扩容

1. 负载因子定义为元素数量除以容量（size / capacity）。当负载因子超过阈值（例如0.75），说明哈希表过于拥挤，冲突概率增加，需要扩容。
2. 扩容步骤：
   • 创建新的桶数组，容量为旧容量的两倍（或其他倍数，常用2）。
   • 重新哈希所有旧桶中的元素到新桶中（因为哈希函数依赖容量，索引会变化）。
   • 用新数组替换旧数组。

class MyHashMap:
    def __init__(self):
        self.capacity = 4
        self.size = 0
        self.buckets = [None] * self.capacity
        self.load_factor_threshold = 0.75

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

    def _resize(self):
        new_capacity = self.capacity * 2
        new_buckets = [None] * new_capacity
        
        # 重新哈希所有现有元素
        for i in range(self.capacity):
            cur = self.buckets[i]
            while cur:
                index = cur.key % new_capacity
                # 插入到新桶的链表头部
                new_head = new_buckets[index]
                new_node = ListNode(cur.key, cur.value)
                new_node.next = new_head
                new_buckets[index] = new_node
                cur = cur.next
        
        self.capacity = new_capacity
        self.buckets = new_buckets

3. 修改put方法，在插入前检查负载因子，并在需要时扩容：

def put(self, key, value):
    # 检查是否需要扩容
    if self.size / self.capacity >= self.load_factor_threshold:
        self._resize()
    
    index = self._hash(key)
    head = self.buckets[index]
    cur = head
    while cur:
        if cur.key == key:
            cur.value = value
            return
        cur = cur.next
    
    new_node = ListNode(key, value)
    new_node.next = head
    self.buckets[index] = new_node
    self.size += 1

注意：_resize()中重新哈希时，我们为每个节点创建了新节点（简单起见），实际可重用节点。get和remove方法无需修改。

第四步：考虑细节和测试

1. 哈希表容量应为质数以减少哈希碰撞，但为简单，这里用2的幂（扩容时翻倍），这在实践中常用，但需注意哈希函数要能均匀分布。
2. 测试基本操作：

h = MyHashMap()
h.put(1, 10)
h.put(2, 20)
print(h.get(1))  # 10
h.put(1, 100)    # 更新
print(h.get(1))  # 100
h.remove(2)
print(h.get(2))  # -1

3. 测试扩容：添加多个元素，观察容量变化。例如，初始容量4，阈值0.75，当插入第3个元素时（3/4=0.75），触发扩容到8，重新哈希。

总结
你已实现了一个支持动态扩容的哈希表，核心点包括：

• 使用链地址法解决冲突。
• 通过负载因子触发扩容，保持操作的平均时间复杂度为O(1)。
• 扩容时重新哈希所有元素。
  这涵盖了哈希表设计的基本原理。你可以进一步优化，例如在删除元素时缩容，或使用更高效的哈希函数。