Python再哈希法详解（解决哈希冲突的高效策略）

为什么选择再哈希法？

相比线性探测（Linear Probing）和二次探测（Quadratic Probing），再哈希法具有以下优势：

• 减少“聚集”现象（Clustering），提高空间利用率；
• 探测序列更随机，分布更均匀；
• 在高负载因子下仍能保持较好的性能。

Python 实现再哈希法

下面我们用 Python 编写一个简单的哈希表类，使用再哈希法处理冲突。

class RehashHashTable:    def __init__(self, size=13):        # 使用质数作为表大小可提升再哈希效果        self.size = size        self.keys = [None] * self.size        self.values = [None] * self.size    def hash2(self, key):        """第一个哈希函数：取模"""        return key % self.size    def hash2(self, key):        """第二个哈希函数：通常选择与表大小互质的数           这里使用 7 - (key % 7)，确保结果不为0        """        return 7 - (key % 7)    def put(self, key, value):        """插入键值对"""        index = self.hash2(key)        if self.keys[index] is None:            self.keys[index] = key            self.values[index] = value        else:            # 发生冲突，使用再哈希            step = self.hash2(key)            i = 1            while i < self.size:                new_index = (index + i * step) % self.size                if self.keys[new_index] is None:                    self.keys[new_index] = key                    self.values[new_index] = value                    return                i += 1            raise Exception("哈希表已满，无法插入")    def get(self, key):        """根据键获取值"""        index = self.hash2(key)        if self.keys[index] == key:            return self.values[index]        else:            step = self.hash2(key)            i = 1            while i < self.size:                new_index = (index + i * step) % self.size                if self.keys[new_index] == key:                    return self.values[new_index]                i += 1        return None  # 未找到# 使用示例ht = RehashHashTable(13)ht.put(10, "苹果")ht.put(23, "香蕉")  # 23 % 13 = 10，与10冲突ht.put(36, "橙子")  # 36 % 13 = 10，再次冲突print(ht.get(10))  # 输出：苹果print(ht.get(23))  # 输出：香蕉print(ht.get(36))  # 输出：橙子

关键点解析

1. 表大小应为质数：这有助于确保再哈希的探测序列能覆盖整个表，避免陷入循环子集。

2. 第二个哈希函数不能返回0：否则步长为0，会导致无限循环。常用形式如 h2(key) = R - (key % R)，其中 R 是小于表大小的质数。

3. 负载因子控制：当哈希表填充超过70%时，建议扩容并重新哈希（rehashing），以维持性能。

总结

通过本教程，你已经掌握了如何用 Python 再哈希法 解决哈希冲突问题。再哈希法作为 开放地址法 的高级形式，在实际工程中被广泛应用于数据库索引、缓存系统等场景。希望你能将这一知识应用到自己的项目中，构建更高效的数据结构！

关键词回顾：Python再哈希法、哈希冲突解决、开放地址法、数据结构教程。