哈希算法题目：设计一个支持动态扩容和缩容的哈希表（使用再哈希策略）

题目描述
设计一个哈希表，支持以下操作：

• put(key, value)：插入键值对
• get(key)：获取键对应的值，键不存在返回-1
• remove(key)：删除键值对
• 哈希表需要支持动态扩容（当负载因子过高时）和缩容（当负载因子过低时）
• 使用再哈希策略（rehashing）处理扩容/缩容过程
• 使用链地址法解决哈希冲突

解题过程

1. 理解负载因子和动态调整的必要性

• 负载因子 = 元素数量 / 哈希表容量
• 负载因子过高（如>0.75）会导致冲突增加，性能下降
• 负载因子过低（如<0.25）会导致空间浪费
• 动态调整容量可以平衡空间和时间效率

2. 设计哈希表基本结构

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

class DynamicHashTable:
    def __init__(self, capacity=8, load_factor=0.75, shrink_factor=0.25):
        self.capacity = capacity
        self.size = 0
        self.table = [None] * capacity
        self.load_factor = load_factor  # 扩容阈值
        self.shrink_factor = shrink_factor  # 缩容阈值
        self.min_capacity = 8  # 最小容量，避免过度缩容

3. 实现哈希函数

def _hash(self, key):
    # 简单的取模哈希，实际可使用更复杂的哈希函数
    return hash(key) % self.capacity

4. 实现put操作

def put(self, key, value):
    # 检查是否需要扩容
    if self.size / self.capacity >= self.load_factor:
        self._resize(self.capacity * 2)
    
    index = self._hash(key)
    node = self.table[index]
    
    # 遍历链表，检查key是否已存在
    while node:
        if node.key == key:
            node.value = value  # 更新现有键的值
            return
        node = node.next
    
    # 键不存在，创建新节点插入链表头部
    new_node = HashNode(key, value)
    new_node.next = self.table[index]
    self.table[index] = new_node
    self.size += 1

5. 实现get操作

def get(self, key):
    index = self._hash(key)
    node = self.table[index]
    
    while node:
        if node.key == key:
            return node.value
        node = node.next
    
    return -1  # 键不存在

6. 实现remove操作

def remove(self, key):
    # 检查是否需要缩容（在删除后检查）
    will_remove = self.get(key) != -1
    
    index = self._hash(key)
    node = self.table[index]
    prev = None
    
    while node:
        if node.key == key:
            if prev:
                prev.next = node.next  # 删除中间/尾部节点
            else:
                self.table[index] = node.next  # 删除头部节点
            self.size -= 1
            break
        prev = node
        node = node.next
    
    # 删除后检查是否需要缩容
    if will_remove and self.capacity > self.min_capacity:
        if self.size / self.capacity <= self.shrink_factor:
            new_capacity = max(self.min_capacity, self.capacity // 2)
            self._resize(new_capacity)

7. 实现再哈希策略（核心部分）

def _resize(self, new_capacity):
    # 保存旧表
    old_table = self.table
    old_capacity = self.capacity
    
    # 创建新表
    self.capacity = new_capacity
    self.table = [None] * new_capacity
    self.size = 0  # 重置大小，在重新插入时会计数
    
    # 重新插入所有元素
    for i in range(old_capacity):
        node = old_table[i]
        while node:
            # 使用新的哈希函数重新计算位置
            self.put(node.key, node.value)
            node = node.next

8. 处理再哈希中的细节问题

• 在_resize中调用put会导致递归调用问题
• 修改put方法，避免在再哈希过程中重复检查扩容：

def put(self, key, value, is_rehashing=False):
    if not is_rehashing and self.size / self.capacity >= self.load_factor:
        self._resize(self.capacity * 2)
    
    index = self._hash(key)
    # ... 其余代码保持不变

def _resize(self, new_capacity):
    old_table = self.table
    old_capacity = self.capacity
    
    self.capacity = new_capacity
    self.table = [None] * new_capacity
    self.size = 0
    
    for i in range(old_capacity):
        node = old_table[i]
        while node:
            # 使用is_rehashing=True避免递归扩容检查
            self._put_rehash(node.key, node.value)
            node = node.next

def _put_rehash(self, key, value):
    """专用于再哈希的插入方法，不检查扩容"""
    index = self._hash(key)
    node = self.table[index]
    
    while node:
        if node.key == key:
            node.value = value
            return
        node = node.next
    
    new_node = HashNode(key, value)
    new_node.next = self.table[index]
    self.table[index] = new_node
    self.size += 1

9. 时间复杂度分析

• 平均情况：O(1) 对于put、get、remove操作
• 最坏情况：O(n) 当所有元素哈希到同一位置时
• 扩容/缩容：O(n)，但分摊到每次操作仍是O(1)

关键要点

1. 负载因子决定扩容/缩容时机
2. 再哈希需要重新计算所有元素的哈希位置
3. 链地址法简单有效地处理冲突
4. 设置最小容量避免过度缩容
5. 再哈希过程中要避免递归调用问题

这种设计在空间和时间效率之间取得了良好平衡，适用于需要动态调整大小的哈希表场景。