哈希算法题目：设计哈希集合（布谷鸟哈希实现）

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

• add(key): 向集合中插入元素 key
• remove(key): 从集合中删除元素 key
• contains(key): 判断集合中是否包含元素 key

要求使用布谷鸟哈希（Cuckoo Hashing）解决哈希冲突，并分析其时间复杂度。

解题过程

1. 理解布谷鸟哈希的基本原理
布谷鸟哈希使用两个哈希表和两个哈希函数。当插入新元素时：

• 先用第一个哈希函数计算位置，如果该位置为空则直接插入
• 如果位置被占用，将原有元素踢出，插入新元素
• 被踢出的元素用另一个哈希函数计算新位置，重复上述过程
• 如果循环次数超过阈值，需要重新哈希

2. 设计数据结构

class CuckooHashSet:
    def __init__(self, capacity=10):
        self.capacity = capacity
        self.table1 = [None] * capacity  # 第一个哈希表
        self.table2 = [None] * capacity  # 第二个哈希表
        self.max_loop = 10  # 最大循环次数
        self.size = 0

3. 实现哈希函数
使用两个不同的哈希函数来减少冲突：

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

def hash2(self, key):
    # 使用不同的哈希计算方式
    return (hash(key) * 2654435761) % self.capacity

4. 实现contains方法
检查元素是否在两个表中的对应位置：

def contains(self, key):
    pos1 = self.hash1(key)
    pos2 = self.hash2(key)
    return (self.table1[pos1] == key or 
            self.table2[pos2] == key)

5. 实现add方法的核心逻辑
这是布谷鸟哈希最复杂的部分：

def add(self, key):
    if self.contains(key):
        return  # 已存在则不插入
    
    # 尝试插入，最多循环max_loop次
    current_key = key
    for _ in range(self.max_loop):
        # 尝试插入第一个表
        pos1 = self.hash1(current_key)
        if self.table1[pos1] is None:
            self.table1[pos1] = current_key
            self.size += 1
            return
        
        # 踢出现有元素，插入新元素
        self.table1[pos1], current_key = current_key, self.table1[pos1]
        
        # 尝试插入第二个表
        pos2 = self.hash2(current_key)
        if self.table2[pos2] is None:
            self.table2[pos2] = current_key
            self.size += 1
            return
            
        # 继续踢出
        self.table2[pos2], current_key = current_key, self.table2[pos2]
    
    # 超过循环次数，需要重新哈希
    self.rehash()
    self.add(current_key)

6. 实现rehash方法
当插入过程中循环次数过多时，需要扩展容量并重新插入所有元素：

def rehash(self):
    old_table1 = self.table1
    old_table2 = self.table2
    
    self.capacity *= 2  # 容量翻倍
    self.table1 = [None] * self.capacity
    self.table2 = [None] * self.capacity
    self.size = 0
    
    # 重新插入所有元素
    for key in old_table1:
        if key is not None:
            self.add(key)
    for key in old_table2:
        if key is not None:
            self.add(key)

7. 实现remove方法
从两个表中都可能删除元素：

def remove(self, key):
    pos1 = self.hash1(key)
    pos2 = self.hash2(key)
    
    if self.table1[pos1] == key:
        self.table1[pos1] = None
        self.size -= 1
        return True
    elif self.table2[pos2] == key:
        self.table2[pos2] = None
        self.size -= 1
        return True
    return False

8. 时间复杂度分析

• contains(): O(1) - 只需要检查两个固定位置
• remove(): O(1) - 同样检查两个位置
• add(): 平均O(1)，最坏情况O(n)需要重新哈希

9. 布谷鸟哈希的优势

• 查找性能稳定，最多只需要检查两个位置
• 装载因子可以较高（通常可达50%）
• 避免链表过长导致的性能下降

10. 实际应用考虑

• 选择合适的哈希函数减少冲突
• 设置合理的最大循环次数
• 考虑动态扩容策略
• 处理哈希函数计算的开销

布谷鸟哈希通过交替使用两个哈希表，在保持简单性的同时提供了较好的冲突解决机制。