布谷鸟哈希详解（Python语言布谷鸟哈希实现教程）-平芜编程栈

在计算机科学中，布谷鸟哈希（Cuckoo Hashing）是一种高效的哈希冲突解决策略，它能保证查找、插入和删除操作的最坏情况时间复杂度为 O(1)。本教程将带你从零开始，用Python语言一步步实现一个完整的布谷鸟哈希表，即使你是编程小白也能轻松上手！

什么是布谷鸟哈希？

布谷鸟哈希得名于布谷鸟的寄生习性——它会把自己的蛋放进其他鸟的巢里。类似地，在布谷鸟哈希中，当发生冲突时，新元素会“踢走”旧元素，迫使旧元素寻找另一个位置。这种机制通过使用两个（或多个）哈希函数和两个哈希表来实现。

布谷鸟哈希的核心思想

使用两个独立的哈希函数 h2 和 h2
维护两个哈希表 table1 和 table2
每个元素最多只能存在于其中一个表中
插入时若目标位置已被占用，则“踢走”原元素，并递归处理被踢走的元素
为防止无限循环，设置最大重试次数，超过则重建哈希表（rehash）

Python 实现布谷鸟哈希

下面我们用 Python 编写一个完整的布谷鸟哈希类。我们将实现插入（insert）、查找（lookup）和删除（delete）三个基本操作。

Python

import randomclass CuckooHash: def __init__(self, size=10): self.size = size self.table1 = [None] * size self.table2 = [None] * size self.max_kicks = 500 # 最大踢出次数，防止无限循环 def _hash2(self, key): """第一个哈希函数""" return hash(key) % self.size def _hash2(self, key): """第二个哈希函数""" return (hash(key) // self.size) % self.size def lookup(self, key): """查找键是否存在""" h2 = self._hash2(key) if self.table1[h2] == key: return True h2 = self._hash2(key) if self.table2[h2] == key: return True return False def insert(self, key): """插入键""" if self.lookup(key): return True # 已存在，无需重复插入 current_key = key for _ in range(self.max_kicks): # 尝试插入到 table1 h2 = self._hash2(current_key) if self.table1[h2] is None: self.table1[h2] = current_key return True else: # 踢走 table1 中的元素 self.table1[h2], current_key = current_key, self.table1[h2] # 尝试插入到 table2 h2 = self._hash2(current_key) if self.table2[h2] is None: self.table2[h2] = current_key return True else: # 踢走 table2 中的元素 self.table2[h2], current_key = current_key, self.table2[h2] # 超过最大踢出次数，重建哈希表 self._rehash() return self.insert(key) # 递归重新插入 def _rehash(self): """重建哈希表：扩大容量并重新插入所有元素""" old_table1 = self.table1[:] old_table2 = self.table2[:] self.size *= 2 self.table1 = [None] * self.size self.table2 = [None] * self.size # 重新插入所有非空元素 for key in old_table1 + old_table2: if key is not None: self.insert(key) def delete(self, key): """删除键""" h2 = self._hash2(key) if self.table1[h2] == key: self.table1[h2] = None return True h2 = self._hash2(key) if self.table2[h2] == key: self.table2[h2] = None return True return False# 使用示例if __name__ == "__main__": cuckoo = CuckooHash(size=5) keys = [10, 20, 30, 40, 50, 60] for k in keys: cuckoo.insert(k) print(f"插入 {k} 成功") print("查找 30:", cuckoo.lookup(30)) # True print("查找 99:", cuckoo.lookup(99)) # False cuckoo.delete(30) print("删除 30 后查找:", cuckoo.lookup(30)) # False