深入理解Python哈希函数设计（从零开始掌握哈希算法与数据结构）

Python中的内置哈希函数

Python 提供了内置的 hash() 函数，可以对不可变对象（如字符串、数字、元组）进行哈希计算：

# 示例：使用内置 hash() 函数print(hash("hello"))        # 输出一个整数print(hash(42))             # 输出 42print(hash((1, 2, 3)))      # 元组也可以被哈希

注意：可变对象（如列表、字典）不能被哈希，因为它们的内容可能改变，导致哈希值不稳定。

设计一个简单的自定义哈希函数

为了更好地理解哈希算法设计，我们可以自己实现一个简单的字符串哈希函数。常用的方法包括“多项式滚动哈希”（Polynomial Rolling Hash）：

def simple_hash(s: str, base=31, mod=10**9 + 7) -> int:    """    对字符串 s 进行简单哈希计算    :param s: 输入字符串    :param base: 基数（通常为质数）    :param mod: 取模值（防止整数溢出）    :return: 哈希值    """    hash_value = 0    for char in s:        hash_value = (hash_value * base + ord(char)) % mod    return hash_value# 测试print(simple_hash("apple"))   # 输出一个整数print(simple_hash("banana"))  # 输出另一个整数

这个函数通过将每个字符的 ASCII 值乘以基数（base）并累加，最终对一个大质数取模，从而生成一个分布较均匀的哈希值。

处理哈希冲突

即使设计得再好，哈希函数也无法完全避免冲突（即两个不同输入产生相同哈希值）。常见的解决方法有：

• 链地址法（Chaining）：每个哈希桶存储一个链表，冲突的元素放在同一个链表中。
• 开放寻址法（Open Addressing）：当发生冲突时，在哈希表中寻找下一个空闲位置。

构建一个简易哈希表

结合前面的知识，我们可以用 Python 实现一个支持插入和查找的简易哈希表，这有助于理解Python数据结构中 dict 的底层原理：

class SimpleHashTable:    def __init__(self, size=10):        self.size = size        self.table = [[] for _ in range(size)]  # 使用链地址法    def _hash(self, key):        return simple_hash(str(key)) % self.size    def put(self, key, value):        index = self._hash(key)        bucket = self.table[index]        for i, (k, v) in enumerate(bucket):            if k == key:                bucket[i] = (key, value)  # 更新已有键                return        bucket.append((key, value))  # 新增键值对    def get(self, key):        index = self._hash(key)        bucket = self.table[index]        for k, v in bucket:            if k == key:                return v        raise KeyError(f"Key '{key}' not found")# 使用示例ht = SimpleHashTable()ht.put("name", "Alice")ht.put("age", 30)print(ht.get("name"))  # 输出: Alice

总结

通过本教程，你已经掌握了Python哈希函数的基本概念、自定义设计方法以及如何用它构建简单的哈希表。理解这些内容不仅有助于提升你对哈希表实现的认识，还能帮助你在实际项目中更高效地使用 Python 内置的数据结构。

提示：在生产环境中，建议优先使用 Python 内置的 dict 和 set，它们经过高度优化，性能远超手写实现。