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

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

• put(key, value): 插入键值对，如果键已存在则更新值
• get(key): 返回键对应的值，如果键不存在返回-1
• remove(key): 删除键值对

要求：

1. 使用数组和链地址法解决哈希冲突
2. 当负载因子超过阈值时自动扩容（通常为0.75）
3. 扩容时使用再哈希策略重新分配所有元素

解题过程

第一步：理解基础哈希表结构
哈希表的核心是通过哈希函数将键映射到数组索引。我们使用链地址法解决冲突：

• 每个数组位置存储一个链表（或数组）
• 哈希冲突的元素存储在同一个位置的链表中

基础结构：

class HashMap:
    def __init__(self, capacity=16, load_factor=0.75):
        self.capacity = capacity  # 初始容量
        self.load_factor = load_factor  # 负载因子阈值
        self.size = 0  # 当前元素数量
        self.buckets = [[] for _ in range(capacity)]  # 桶数组

第二步：实现哈希函数和基本操作
哈希函数将键转换为数组索引：

def _hash(self, key):
    return hash(key) % self.capacity  # 使用Python内置哈希函数取模

实现put操作：

def put(self, key, value):
    index = self._hash(key)
    bucket = self.buckets[index]
    
    # 遍历链表查找是否已存在该键
    for i, (k, v) in enumerate(bucket):
        if k == key:
            bucket[i] = (key, value)  # 更新值
            return
    
    # 键不存在，添加新元素
    bucket.append((key, value))
    self.size += 1
    
    # 检查是否需要扩容
    if self.size / self.capacity > self.load_factor:
        self._resize()

第三步：理解负载因子和扩容时机
负载因子 = 元素数量 / 哈希表容量

• 当负载因子 > 0.75时，冲突概率显著增加
• 需要扩容以减少冲突，提高性能

扩容过程：

1. 创建新的更大容量的桶数组（通常翻倍）
2. 将原有所有元素重新哈希到新数组中
3. 更新容量和桶数组引用

第四步：实现再哈希策略的扩容

def _resize(self):
    # 保存旧数据
    old_buckets = self.buckets
    old_capacity = self.capacity
    
    # 创建新容量的桶数组（容量翻倍）
    self.capacity *= 2
    self.buckets = [[] for _ in range(self.capacity)]
    self.size = 0  # 重置大小，重新计数
    
    # 重新哈希所有元素
    for bucket in old_buckets:
        for key, value in bucket:
            self.put(key, value)  # 使用新的哈希函数重新插入

第五步：完善get和remove操作

def get(self, key):
    index = self._hash(key)
    bucket = self.buckets[index]
    
    for k, v in bucket:
        if k == key:
            return v
    return -1  # 键不存在

def remove(self, key):
    index = self._hash(key)
    bucket = self.buckets[index]
    
    for i, (k, v) in enumerate(bucket):
        if k == key:
            del bucket[i]  # 删除元素
            self.size -= 1
            return

第六步：处理哈希函数的改进
扩容后哈希函数发生变化（因为取模的除数变了）：

def _hash(self, key):
    # 使用位运算替代取模，效率更高
    return hash(key) & (self.capacity - 1)

注意：这要求容量始终是2的幂次，这样才能保证 & (capacity-1) 等价于 % capacity。

完整实现示例

class HashMap:
    def __init__(self, capacity=16, load_factor=0.75):
        self.capacity = capacity
        self.load_factor = load_factor
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]
    
    def _hash(self, key):
        return hash(key) & (self.capacity - 1)
    
    def put(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        
        bucket.append((key, value))
        self.size += 1
        
        if self.size / self.capacity > self.load_factor:
            self._resize()
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        return -1
    
    def remove(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return
    
    def _resize(self):
        old_buckets = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        self.size = 0
        
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)

关键要点总结

1. 动态扩容：当负载因子超过阈值时自动扩容
2. 再哈希策略：扩容时需要重新计算所有元素的哈希值
3. 时间复杂度：平均情况下O(1)，最坏情况下O(n)
4. 空间换时间：通过扩容减少冲突，提高性能

这种设计确保了哈希表在各种使用场景下都能保持较好的性能。