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

我将为您详细讲解如何设计一个支持动态扩容和缩容的哈希表，使用链地址法解决哈希冲突。

题目描述

设计一个哈希表，需要支持以下操作：

• put(key, value)：插入键值对
• get(key)：获取键对应的值
• remove(key)：删除键值对
• 当负载因子超过阈值时自动扩容
• 当负载因子低于阈值时自动缩容
• 使用链地址法解决哈希冲突

解题过程

1. 基本数据结构设计

首先定义哈希表中的基本数据结构：

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.buckets = [None] * capacity  # 桶数组
        self.load_factor = load_factor    # 扩容阈值比例
        self.shrink_factor = shrink_factor  # 缩容阈值比例

2. 哈希函数设计

哈希函数负责将键映射到桶的索引：

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

3. 插入操作 (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.buckets[index]
    
    # 如果桶为空，直接插入
    if node is None:
        self.buckets[index] = HashNode(key, value)
        self.size += 1
        return
    
    # 遍历链表，检查键是否已存在
    prev = None
    while node:
        if node.key == key:
            # 键已存在，更新值
            node.value = value
            return
        prev = node
        node = node.next
    
    # 键不存在，在链表末尾插入新节点
    prev.next = HashNode(key, value)
    self.size += 1

4. 查找操作 (get)

查找操作需要处理哈希冲突：

def get(self, key):
    index = self._hash(key)
    node = self.buckets[index]
    
    while node:
        if node.key == key:
            return node.value
        node = node.next
    
    raise KeyError(f"Key {key} not found")

5. 删除操作 (remove)

删除操作需要考虑链表节点的移除和动态缩容：

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 * self.shrink_factor and 
                self.capacity > 8):  # 保持最小容量
                self._resize(max(8, self.capacity // 2))
            
            return
        prev = node
        node = node.next
    
    raise KeyError(f"Key {key} not found")

6. 动态调整大小 (_resize)

这是实现动态扩容和缩容的核心方法：

def _resize(self, new_capacity):
    # 保存旧的桶数组
    old_buckets = self.buckets
    old_capacity = self.capacity
    
    # 创建新的桶数组
    self.capacity = new_capacity
    self.buckets = [None] * new_capacity
    self.size = 0
    
    # 重新哈希所有元素
    for i in range(old_capacity):
        node = old_buckets[i]
        while node:
            # 重新插入每个元素
            self.put(node.key, node.value)
            node = node.next

7. 完整实现

将以上方法组合起来：

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.buckets = [None] * capacity
        self.load_factor = load_factor
        self.shrink_factor = shrink_factor
    
    def _hash(self, key):
        return hash(key) % self.capacity
    
    def put(self, key, value):
        if self.size >= self.capacity * self.load_factor:
            self._resize(self.capacity * 2)
        
        index = self._hash(key)
        node = self.buckets[index]
        
        if node is None:
            self.buckets[index] = HashNode(key, value)
            self.size += 1
            return
        
        prev = None
        while node:
            if node.key == key:
                node.value = value
                return
            prev = node
            node = node.next
        
        prev.next = HashNode(key, value)
        self.size += 1
    
    def get(self, key):
        index = self._hash(key)
        node = self.buckets[index]
        
        while node:
            if node.key == key:
                return node.value
            node = node.next
        
        raise KeyError(f"Key {key} not found")
    
    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 * self.shrink_factor and 
                    self.capacity > 8):
                    self._resize(max(8, self.capacity // 2))
                
                return
            prev = node
            node = node.next
        
        raise KeyError(f"Key {key} not found")
    
    def _resize(self, new_capacity):
        old_buckets = self.buckets
        old_capacity = self.capacity
        
        self.capacity = new_capacity
        self.buckets = [None] * new_capacity
        self.size = 0
        
        for i in range(old_capacity):
            node = old_buckets[i]
            while node:
                self.put(node.key, node.value)
                node = node.next
    
    def __contains__(self, key):
        try:
            self.get(key)
            return True
        except KeyError:
            return False

关键要点说明

1. 负载因子管理：

   • 当负载因子（size/capacity）超过0.75时扩容
   • 当负载因子低于0.25时缩容（保持最小容量为8）

2. 链地址法：

   • 每个桶使用链表存储冲突的元素
   • 插入时在链表末尾添加
   • 删除时需要维护链表的前后指针

3. 动态调整：

   • 扩容时容量翻倍
   • 缩容时容量减半，但保持最小容量
   • 重新哈希所有元素

4. 时间复杂度：

   • 平均情况：O(1) 对于所有操作
   • 最坏情况：O(n) 当所有元素都哈希到同一个桶时

这个设计确保了哈希表在不同负载情况下都能保持较好的性能。