Python爬虫入门教程：从零开始抓取网页数据 - 程序员客栈

如何从CPython源码理解字典的键必须可哈希的底层原因

访客 源码剖析 1

从CPython源码看透：为什么字典键必须可哈希？底层原理深度解析

📚 目录导读

  1. 哈希表：Python字典的底层骨架
  2. CPython源码中dict的哈希机制
  3. 键必须可哈希的三大底层原因
  4. 可变对象为何不能作为键？源码级揭秘
  5. 自定义对象：如何安全实现hash
  6. 常见问题与深度问答

哈希表：Python字典的底层骨架

在深入CPython源码之前，我们需要先理解字典的核心数据结构——哈希表（Hash Table），Python字典是一种高度优化的哈希表实现，其设计目标是在O(1)平均时间内完成查找、插入和删除操作。

哈希表的工作原理：

  • 每个键通过哈希函数计算出一个整数（哈希值）
  • 这个哈希值决定了键值对在内存数组中的存储位置（索引）
  • 不同键可能计算得到相同的哈希值（哈希冲突），需要通过开放寻址法解决

打开CPython源码（以Python 3.11为例），你会发现字典的核心结构定义在Objects/dictobject.c和Include/cpython/dictobject.h中。PyDictKeysObject结构体维护了一个哈希条目数组（PyDictKeyEntry），每个条目包含哈希值、键对象（PyObject *key）和值对象（PyObject *value）。

typedef struct {
    PyObject *key;
    PyObject *value;
    Py_hash_t hash;  // 缓存键的哈希值
} PyDictKeyEntry;

关键观察：每个条目都缓存了hash字段！这意味着CPython会预先计算并存储键的哈希值，避免重复计算，但这也隐含了一个前提：键的哈希值必须在整个字典生命周期内保持不变。

CPython源码中dict的哈希机制

让我们从源码层面追踪字典插入和查找时如何处理哈希值。

1 插入流程（PyDict_SetItem）

在Objects/dictobject.c的insertdict_clean函数中,核心逻辑是：

static Py_ssize_t
insertdict_clean(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value)
{
    PyDictKeysObject *k = mp->ma_keys;
    size_t i = hash & (k->dk_size - 1);  // 取模运算确定初始索引
    // 开放寻址法处理冲突
    for (size_t perturb = hash; k->dk_entries[i].key != NULL; i = (i * 5 + 1 + perturb)) {
        py_hash_t h = k->dk_entries[i].hash;
        // 比较哈希值，如果找到空槽或相同键则停止
    }
    // 插入新条目，缓存哈希值
    k->dk_entries[i].hash = hash;
    k->dk_entries[i].key = key;
    ...
}

这里hash & (dk_size - 1)是关键：它利用位运算快速计算索引，要求dk_size必须是2的幂次方,哈希值的质量直接影响索引分布的均匀性。

2 查找流程（_PyDict_Lookup）

查找时，CPython会先比较哈希值,只有哈希值匹配后才进行键对象相等性比较：

Py_ssize_t
_PyDict_Lookup(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject **value_addr)
{
    PyDictKeysObject *k = mp->ma_keys;
    size_t i = hash & (k->dk_size - 1);
    for (size_t perturb = hash; k->dk_entries[i].key != NULL; i = (i * 5 + 1 + perturb)) {
        PyObject *ek = k->dk_entries[i].key;
        if (ek == key || (k->dk_entries[i].hash == hash && ek->ob_type->tp_richcompare(ek, key, Py_EQ))) {
            // 找到匹配的键
            *value_addr = k->dk_entries[i].value;
            return i;
        }
    }
    return DKIX_EMPTY;  // 未找到
}

哈希值在查找中起双重作用：

  1. 确定搜索的初始位置（索引）
  2. 快速过滤不相等的键（先比哈希,再比对象相等性）

键必须可哈希的三大底层原因

从源码角度看，强制键可哈希（即实现__hash__方法并返回整数）源于以下三个根本原因：

🔑 原因一：索引计算需要确定性哈希值

字典使用hash & (size - 1)计算存储位置，如果键不可哈希（即无法调用__hash__），则无法获得这个整数,字典就无法确定键值对应该存放在哪里。

源码证据：在PyDict_SetItem的入口处,CPython会强制计算哈希：

if (!Py_HashPointer(key)) {
    PyErr_SetString(PyExc_TypeError, "unhashable type: 'xxx'");
    return NULL;
}

🔑 原因二：哈希值必须保持稳定（不变性）

这一点最容易被忽视，在insertdict_clean中，哈希值被缓存到PyDictKeyEntry.hash字段,字典在其生命周期中依赖这个缓存值进行快速查找和重新哈希。

如果键的哈希值在插入后发生变化，会发生什么？

  • 查找时，使用新哈希值计算的索引与原存储位置不一致
  • 字典会遍历所有条目但永远找不到该键（即使键对象本身没变）
  • 导致键“不可访问”或逻辑上的数据丢失

这正是Python要求键对象必须不可变（immutable）的根本原因——可变对象通常意味着哈希值也会变化。

🔑 原因三：哈希冲突解决依赖哈希值的稳定性

开放寻址法（Open Addressing）中处理冲突的探测序列完全基于哈希值：

i = (i * 5 + 1 + perturb)  // perturb = hash >> 5

探测序列是哈希值的确定性函数，一旦哈希值改变，探测序列也会改变,导致已插入的条目在查找时可能无法被访问。

C语言原理解释：CPython使用“二次探测”（quadratic probing）的变体，其探测步长依赖于原始哈希值，如果键的哈希值改变，字典会从一个错误的初始索引开始探测,永远无法找到该条目。

可变对象为何不能作为键？源码级揭秘

让我们用实际代码验证上述理论：

class MutableKey:
    def __init__(self, x):
        self.x = x
    def __hash__(self):
        return id(self)  # 基于对象标识的哈希，看似稳定
    def __eq__(self, other):
        return self.x == other.x
obj = MutableKey(10)
d = {obj: "value"}
obj.x = 20  # 修改对象状态
print(d.get(MutableKey(10)))  # 返回None！因为新对象的id不同

但更危险的场景是哈希值依赖于可变属性：

class DangerousKey:
    def __init__(self, x):
        self.x = x
    def __hash__(self):
        return hash(self.x)  # 哈希值随x变化
    def __eq__(self, other):
        return self.x == other.x
dk = DangerousKey(5)
d = {dk: "secret"}
dk.x = 10  # 哈希值改变！
# 此时字典内部缓存的是旧哈希值，但查找时使用新哈希值
# → 键将永远无法通过常规查找找到

CPython对此的严格限制：

  • 内置可变类型（list、set、dict）的__hash__都定义为None
  • 当尝试对它们调用hash()时，会直接抛出TypeError
  • 源码位置：Objects/object.c中的PyObject_Hash()函数检查tp_hash是否为PyObject_HashNotImplemented

自定义对象：如何安全实现hash

从源码中我们可以总结出实现__hash__必须遵守的原则：

  1. 一致性：如果a == b，则hash(a) == hash(b)
  2. 稳定性：对象的哈希值在其生命周期内必须保持不变（建议基于不可变属性计算）
  3. 性能：哈希值的计算应该高效，但这不是强制要求

最佳实践：对于不可变对象，使用tuple打包键属性：

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __hash__(self):
        return hash((self.x, self.y))  # 基于元组的哈希
    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

注意：如果Point后来被修改为可变的（如setattr(p, 'x', 10)），这会破坏字典的稳定性，唯一安全的做法是：对象一旦用于字典键，其所有参与哈希和等值比较的属性都应视为不可变的。

常见问题与深度问答

❓ 问：为什么Python不自动为每个对象分配一个固定哈希值（如对象ID）？

答：这确实能解决稳定性问题，但Python的设计哲学是“相等性由值决定”，而不仅仅是对象标识，如果你希望用对象标识作为哈希,可以这样定义：

class IdHash:
    def __hash__(self):
        return id(self)
    def __eq__(self, other):
        return self is other

但这样会导致两个值相等但不同的对象无法作为同一个字典键——例如1 == True但它们的哈希值不同（hash(1)=1, hash(True)=1，这里恰好相同，但一般情况不同）。

❓ 问：哈希冲突对性能影响有多大？

答：CPython的开放寻址法在处理冲突时，会线性探测直至找到空槽，当负载因子（used / size）超过2/3时，字典会进行resize（扩容约4倍），源码中dictresize函数负责重新计算所有键的索引，一个设计良好的哈希函数应尽量让键均匀分布,减少冲突。

❓ 问：字符串键的哈希值是如何计算的？

答：CPython对字符串使用SipHash算法（Python 3.4+），并在字符串创建时预计算并缓存哈希值，字符串对象内部有一个ob_shash字段：

typedef struct {
    PyObject_VAR_HEAD
    Py_hash_t ob_shash;    // 缓存的哈希值，-1表示未计算
    char ob_sval[1];       // 字符串数据
} PyASCIIObject;

这解释了为什么字符串作为字典键非常高效——哈希计算只进行一次。

❓ 问：如果自定义类忘记实现hash会怎样？

答：默认情况下，自定义类从object继承__hash__（基于对象ID）和__eq__（基于对象标识），如果你重写了__eq__但没有重写__hash__，CPython会自动将__hash__设为None（在type.__new__中检测），查看源码Objects/typeobject.c中的type_setattro逻辑。

总结与最佳实践

从CPython源码中我们可以清晰地看到：字典要求键可哈希的本质是要求键提供一个稳定、高效的哈希函数，用于索引计算、快速查找和冲突解决，这个要求并非Python独有，所有基于哈希表的数据结构（如Java的HashMap、Go的map）都有相似约束。

给开发者的建议：

  1. 永远不要使用可变对象（list、dict、set）作为字典键
  2. 自定义类作为键时，确保__hash__和__eq__方法一起定义
  3. 如果类允许修改属性，避免将其放入字典作为键
  4. 对于性能敏感的字典操作，优先选择内置不可变类型（字符串、元组、frozenset）

通过理解这些底层机制，你不仅能避免常见的Python陷阱，还能写出更高效、更健壮的代码。

标签： 哈希冲突

文章来源： 访客
版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。

上一篇你是否需要一个关于Python的property装饰器底层实现的源码剖析案例

下一篇你能否用源码分析的方式证明Python的字符串拼接为什么推荐用join

相关文章

抱歉，评论功能暂时关闭!