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

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

• put(key, value)：插入键值对
• get(key)：获取键对应的值
• remove(key)：删除键值对
  要求哈希表能够根据负载因子自动扩容和缩容，使用链地址法解决哈希冲突。

解题过程

1. 基础结构设计
首先定义哈希表的基本结构：

• 使用固定大小的数组作为哈希桶
• 每个桶使用链表存储键值对
• 定义负载因子阈值（如0.75）

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):
        self.capacity = capacity
        self.size = 0
        self.load_factor = load_factor
        self.buckets = [None] * capacity

2. 哈希函数设计
使用简单的取模运算作为哈希函数：

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

3. 基本操作实现

put操作步骤：

1. 计算key的哈希值确定桶索引
2. 遍历对应链表：
   • 如果找到相同key，更新value
   • 如果未找到，在链表头部插入新节点
3. 更新size并检查是否需要扩容

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

get操作步骤：

1. 计算key的哈希值
2. 遍历对应链表查找key
3. 找到返回value，未找到返回None

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

remove操作步骤：

1. 计算key的哈希值
2. 遍历链表找到目标节点
3. 删除节点（需要处理头节点特殊情况）
4. 更新size并检查是否需要缩容

def remove(self, key):
    index = self._hash(key)
    node = self.buckets[index]
    prev = None
    
    while node:
        if node.key == key:
            if prev:
                prev.next = node.next
            else:
                self.buckets[index] = node.next
            self.size -= 1
            
            # 检查缩容
            if self.size <= self.capacity * 0.25 and self.capacity > 8:
                self._resize(self.capacity // 2)
            return
        prev = node
        node = node.next

4. 动态扩容缩容实现

resize操作步骤：

1. 创建新容量的桶数组
2. 遍历所有现有节点，重新计算哈希值
3. 将节点插入到新桶中
4. 更新桶数组引用和容量

def _resize(self, new_capacity):
    old_buckets = self.buckets
    self.capacity = new_capacity
    self.buckets = [None] * new_capacity
    self.size = 0  # 重置size，重新插入时会更新
    
    # 重新插入所有现有节点
    for head in old_buckets:
        node = head
        while node:
            self.put(node.key, node.value)
            node = node.next

5. 性能优化考虑

链表优化：

• 当链表过长时（如长度>8），可转换为红黑树
• 插入新节点时可以考虑尾插法保持顺序

扩容优化：

• 渐进式扩容：分批迁移数据，避免单次操作耗时过长
• 容量选择为2的幂次，可以用位运算替代取模

完整实现示例：

class OptimizedDynamicHashTable:
    def __init__(self, capacity=16, load_factor=0.75):
        self.capacity = capacity
        self.size = 0
        self.load_factor = load_factor
        self.buckets = [None] * capacity
    
    def _hash(self, key):
        return hash(key) & (self.capacity - 1)  # 位运算优化
    
    def put(self, key, value):
        # 实现同上，使用位运算优化哈希计算
        pass

这个设计确保了哈希表在各种操作下都能保持较好的性能，通过动态调整容量来平衡空间和时间效率。