CodeWalk

Python性能陷阱：字典冲突与哈希碰撞

作者：古法程序员 · 2026-05-30 12:55

请解释Python字典（dict）的底层实现（哈希表）、哈希碰撞的处理方式（开放地址法/二次探测）、以及为什么字典冲突会导致性能下降。如何通过__hash__和__eq__正确实现自定义哈希？

回答

古法程序员

Python字典底层实现

Python字典使用哈希表（hash table）：

  1. 调用键的__hash__()计算哈希值
  2. 通过hash & mask定位到表项的索引
  3. 如果表项为空，插入；否则解决冲突

哈希碰撞处理 — 开放地址法 + 二次探测

# 近似实现
def _find_index(dict, key):
    hash_value = hash(key)
    mask = dict._mask  # size - 1
    i = hash_value & mask

    # 二次探测
    perturb = hash_value
    while dict._entries[i].filled:
        if dict._entries[i].hash == hash_value and dict._entries[i].key == key:
            return i  # 找到已有键
        # 二次探测公式
        i = (i * 5 + perturb + 1) & mask
        perturb >>= 5  # PERTURB_SHIFT
    return i  # 找到空位

性能下降原因

  1. 探测链增长：冲突时需沿探测链查找，O(1)退化为O(n)
  2. 缓存失效：探测链跳跃访问导致CPU缓存未命中
  3. 哈希洪水攻击（HashDoS）：恶意构造大量哈希值相同的键

Python 3.3+ 安全机制： 启动时随机化哈希种子（PYTHONHASHSEED），防止哈希洪水攻击。

自定义哈希实现

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __hash__(self):
        return hash((self.name, self.age))

    def __eq__(self, other):
        if not isinstance(other, Person):
            return NotImplemented
        return self.name == other.name and self.age == other.age

规则：

  1. __hash__和__eq__必须一起实现
  2. 相等的对象必须有相同的哈希值
  3. 可变对象不应是可哈希的
  4. 哈希函数应均匀分布，减少碰撞

优化建议：

  • 使用整数键（哈希计算快）
  • 避免使用自定义类作为键（除非必须）
  • 大数据量时考虑__slots__减少内存