CPython frozendict 哈希修复解读frozendict | frozendict合并结果的 hash 一致性【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpythonCPython 在 gh-issue-149676 中修复了frozendict | frozendict合并结果无法参与哈希的问题此前两个不可变字典通过|运算符合并后新对象缺失哈希能力无法作为字典键或放入集合修复后hash(a | b)与hash(frozendict({**a, **b}))完全一致。本文基于 CPython 源码深入解读frozendict的类型设计、|合并的底层调用链frozendict_or→_PyDict_Or→ 哈希缓存字段ma_hash并结合回归测试Lib/test/test_dict.py说明该修复的验证方式与哈希实现细节帮助读者理解不可变映射在 CPython 中的完整实现机制。修复背景一条 NEWS 条目背后的缺陷本次分析的关联文档位于Misc/NEWS.d/next/Core_and_Builtins/2026-05-11-14-48-56.gh-issue-149676.6aTrw1.rst内容仅一句话Fixfrozendict | frozendicthash.这是 CPython 采用的 NEWS fragment 机制每个待合入的变更在Misc/NEWS.d/next/Core_and_Builtins/目录下生成一个以日期、issue 编号和随机后缀命名的.rst文件合并时统一汇总进Misc/NEWS。它对应 gh-issue-149676frozendict | frozendict的结果哈希行为有缺陷需要修复。frozendict是 CPython 3.14 引入的不可变字典类型tp_name为frozendict见Objects/dictobject.c中的PyFrozenDict_Type定义。不可变字典天然适合作为哈希容器使用然而合并运算符|返回的新对象在特定场景下丢失了正确的哈希语义导致hash()抛错或结果不稳定。frozendict 的类型基础可哈希的不可变映射在深入修复之前先建立frozendict的类型背景。其类型对象定义于 Objects/dictobject.c 的PyFrozenDict_TypePyTypeObject PyFrozenDict_Type { PyVarObject_HEAD_INIT(PyType_Type, 0) .tp_name frozendict, .tp_basicsize sizeof(PyFrozenDictObject), .tp_dealloc dict_dealloc, .tp_repr frozendict_repr, .tp_as_number frozendict_as_number, .tp_as_sequence dict_as_sequence, .tp_as_mapping frozendict_as_mapping, .tp_hash frozendict_hash, .tp_flags Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC | Py_TPFLAGS_BASETYPE | _Py_TPFLAGS_MATCH_SELF | Py_TPFLAGS_MAPPING, .tp_doc frozendict_doc, .tp_traverse dict_traverse, .tp_clear dict_tp_clear, .tp_richcompare dict_richcompare, .tp_iter dict_iter, .tp_methods frozendict_methods, .tp_alloc _PyType_AllocNoTrack, .tp_new frozendict_new, .tp_free PyObject_GC_Del, .tp_vectorcall frozendict_vectorcall, .tp_version_tag _Py_TYPE_VERSION_FROZENDICT, };关键点tp_hash frozendict_hash与可变dicttp_hash为空即不可哈希不同frozendict显式注册了哈希函数因此可作为字典键、放入set/frozenset。tp_flags包含Py_TPFLAGS_MAPPING从类型系统层面声明其映射语义。_Py_TPFLAGS_MATCH_SELF配合frozendict_vectorcall实现构造优化例如frozendict(frozendict)直接返回原对象见 Objects/dictobject.c 中frozendict_vectorcall的注释 frozendict(frozendict) returns the same object unmodified。继承 dict 的大部分槽位tp_dealloc、tp_repr、tp_iter、tp_traverse等直接复用dict的实现说明frozendict与dict共享同一套底层存储结构。从文档字符串frozendict_doc可以确认其构造方式frozendict() - new empty immutable dictionary frozendict(mapping) - new immutable dictionary initialized from a mapping objects (key, value) pairs frozendict(iterable) - new immutable dictionary initialized as if via: d {} for k, v in iterable: d[k] v d frozendict(d) frozendict(**kwargs) - new immutable dictionary initialized with the namevalue pairs in the keyword argument list. For example: frozendict(one1, two2)即frozendict()、frozendict(mapping)、frozendict(iterable)、frozendict(**kwargs)四种构造形式均受支持。缺陷根源|合并结果丢失哈希能力frozendict通过数字协议tp_as_number实现了|运算符入口为 Objects/dictobject.c 中的frozendict_orstatic PyObject * frozendict_or(PyObject *self, PyObject *other) { if (PyFrozenDict_CheckExact(self)) { // frozendict() | frozendict(...) frozendict(...) if (GET_USED((PyDictObject *)self) 0 PyFrozenDict_CheckExact(other)) { return Py_NewRef(other); } // frozendict(...) | frozendict() frozendict(...) if (PyAnyDict_CheckExact(other) GET_USED((PyDictObject *)other) 0) { return Py_NewRef(self); } } return _PyDict_Or(self, other); }该函数包含两层逻辑空字典短路优化当左侧frozendict为空且右侧是精确的frozendict时直接返回右侧对象当右侧dict或frozendict为空时直接返回左侧对象。这避免了无意义的复制——注意这里返回的是原对象本身其哈希缓存完好不存在问题。一般路径调用_PyDict_Or创建一个新对象PyObject * _PyDict_Or(PyObject *self, PyObject *other) { if (!PyAnyDict_Check(self) || !PyAnyDict_Check(other)) { Py_RETURN_NOTIMPLEMENTED; } PyObject *new anydict_copy_untracked(self); if (new NULL) { return NULL; } if (dict_update_arg(new, other)) { Py_DECREF(new); return NULL; } _PyObject_GC_TRACK(new); return new; }_PyDict_Or先复制self生成新字典再通过dict_update_arg把other的键值对合并进去最后 GC 追踪并返回。缺陷就在这里anydict_copy_untracked在复制时并不保证为目标对象正确初始化frozendict特有的哈希缓存字段。从 Objects/dictobject.c 中copy_lock_held_untracked的实现可以看到复制路径对 as_frozendict 与非 frozendict 分支的处理是不同的static PyObject * copy_lock_held_untracked(PyObject *o, int as_frozendict) { // frozendict is immutable and so doesnt need critical section ... if (as_frozendict) { ... d frozendict_new_untracked(PyFrozenDict_Type); ... } ... }而new_dict_impl所有 dict/frozendict 新建对象的统一入口中哈希缓存字段的初始化严格依赖frozendict标志static inline PyObject * new_dict_impl(PyDictObject *mp, PyDictKeysObject *keys, PyDictValues *values, Py_ssize_t used, int free_values_on_failure, int frozendict, int gc_track) { ... mp-ma_keys keys; mp-ma_values values; mp-ma_used used; mp-_ma_watcher_tag 0; if (frozendict) { ((PyFrozenDictObject *)mp)-ma_hash -1; } ASSERT_CONSISTENT(mp); if (gc_track) { _PyObject_GC_TRACK(mp); } return (PyObject *)mp; }也就是说只有显式走frozendict_new_untracked/frozendict_new路径的对象ma_hash才会被初始化为 -1-1 表示尚未计算。若|合并走的复制路径创建出的对象没有初始化该字段其tp_hashfrozendict_hash在读取ma_hash时就会读到未定义值表现为合并结果hash()行为异常——这正是 gh-issue-149676 修复的核心。哈希实现与 frozenset(items) 等价的缓存式哈希修复后frozendict | frozendict的结果与直接构造的frozendict拥有完全一致的哈希。理解这一点需要先读懂 Objects/dictobject.c 中frozendict_hash的完整实现// Code copied from frozenset_hash() static Py_hash_t frozendict_hash(PyObject *op) { PyFrozenDictObject *self _PyFrozenDictObject_CAST(op); Py_hash_t shash FT_ATOMIC_LOAD_SSIZE_RELAXED(self-ma_hash); if (shash ! -1) { return shash; } PyDictObject *mp _PyAnyDict_CAST(op); Py_uhash_t hash 0; PyObject *value; // borrowed ref Py_ssize_t pos 0; Py_hash_t key_hash; while (_PyDict_Next(op, pos, NULL, value, key_hash)) { Py_hash_t pair_hash frozendict_pair_hash(key_hash, value); if (pair_hash -1) { return -1; } hash ^ _shuffle_bits(pair_hash); } /* Factor in the number of active entries */ hash ^ ((Py_uhash_t)mp-ma_used 1) * 1927868237UL; /* Disperse patterns arising in nested frozendicts */ hash ^ (hash 11) ^ (hash 25); hash hash * 69069U 907133923UL; /* -1 is reserved as an error code */ if (hash (Py_uhash_t)-1) { hash 590923713UL; } FT_ATOMIC_STORE_SSIZE_RELAXED(self-ma_hash, (Py_hash_t)hash); return (Py_hash_t)hash; }核心设计要点缓存机制frozendict对象头部PyFrozenDictObject包含ma_hash字段首次调用hash()后计算结果会被原子缓存FT_ATOMIC_STORE_SSIZE_RELAXED后续调用直接返回缓存值。由于frozendict不可变缓存永远有效。这也解释了为什么构造路径必须把ma_hash初始化为 -1否则缓存字段携带垃圾值哈希结果不可信。逐项异或XOR组合遍历每个(key, value)对用frozendict_pair_hash计算键值对哈希再通过_shuffle_bits打散后异或进累加器。顺序无关异或运算满足交换律因此hash(frozendict(x1, y2)) hash(frozendict(y2, x1))。元素个数参与哈希hash ^ (ma_used 1) * 1927868237UL把活跃条目数计入避免{1: 2}与{2: 1}这类异或碰撞。防碰撞二次分散后续的位移异或与乘法hash * 69069U 907133923UL用于打散嵌套 frozendict 产生的规律性模式。-1 保留为错误码PyObject_Hash以 -1 表示失败因此计算结果若为 -1 会替换为固定回退值。与 frozenset(fd.items()) 等价测试注释明确说明实现意图是让hash(fd) hash(frozenset(fd.items()))见下文测试。键值对哈希frozendict_pair_hash则完全复刻了元组哈希算法源码注释 Code copied from tuple_hash()把(key, value)当作二元组用 XXHASH 风格素数混合// Compute hash((key, value)). // Code copied from tuple_hash(). static Py_hash_t frozendict_pair_hash(Py_hash_t key_hash, PyObject *value) { assert(key_hash ! -1); const Py_ssize_t len 2; Py_uhash_t acc _PyTuple_HASH_XXPRIME_5; Py_uhash_t lane key_hash; acc lane * _PyTuple_HASH_XXPRIME_2; acc _PyTuple_HASH_XXROTATE(acc); acc * _PyTuple_HASH_XXPRIME_1; lane PyObject_Hash(value); if (lane (Py_uhash_t)-1) { return -1; } acc lane * _PyTuple_HASH_XXPRIME_2; acc _PyTuple_HASH_XXROTATE(acc); acc * _PyTuple_HASH_XXPRIME_1; /* Add input length, mangled to keep the historical value of hash(()). */ acc len ^ (_PyTuple_HASH_XXPRIME_5 ^ 3527539UL); if (acc (Py_uhash_t)-1) { acc 1546275796; } return acc; }注意这里复用了已缓存的键哈希key_hash来自_PyDict_Next的输出参数而值则通过PyObject_Hash(value)现场计算——因此若frozendict的值不可哈希如值为listhash(fd)会抛出TypeError: unhashable type: list这是由哈希契约决定的设计行为而非缺陷。修复的本质保证合并路径正确初始化哈希缓存综合上面两节可以看出本次修复的落点在于让|合并路径创建的新对象走与普通构造完全一致的对象初始化流程确保新对象的ma_hash被初始化为 -1未缓存状态后续首次hash()调用按frozendict_hash计算并缓存正确值最终结果满足hash(a | b) hash(frozendict({**a, **b}))。修复后的frozendict_or中非短路的一般路径经由_PyDict_Or→anydict_copy_untracked正确识别目标类型为 frozendict并走new_frozendict_untracked内部调用new_dict_impl(..., frozendict1, ...)完成ma_hash -1初始化创建副本对象从而恢复哈希语义。从调用链上看frozendict_new_untracked还会为每个新建对象显式设置ma_hash -1static PyObject * frozendict_new_untracked(PyTypeObject *type) { assert(PyObject_IsSubclass((PyObject*)type, (PyObject*)PyFrozenDict_Type)); PyObject *d anydict_new_untracked(type); if (d NULL) { return NULL; } assert(can_modify_dict(_PyAnyDict_CAST(d))); _PyFrozenDictObject_CAST(d)-ma_hash -1; return d; }这一双重保障new_dict_impl内初始化 构造后显式赋值确保无论走哪条创建路径ma_hash都以 -1 起步。回归测试验证gh-149676 的测试锚点修复伴随的回归测试位于 Lib/test/test_dict.py 的test_or中直接引用 issue 编号# gh-149676: Test hash(frozendict | frozendict) a frozendict({a: 1}) b frozendict({b: 2}) self.assertEqual(hash(a | b), hash(frozendict({a: 1, b: 2})))该断言验证合并结果的哈希必须等价于直接构造的等价 frozendict 的哈希。修复前该断言会失败hash(a | b)行为异常修复后通过。同文件还覆盖了frozendict哈希的其他关键性质可作为理解本修复的补充测试证据def test_hash(self): # hash() doesnt rely on the items order self.assertEqual(hash(frozendict(x1, y2)), hash(frozendict(y2, x1))) # Check that hash() computes the hash of (key, value) pairs cases [ frozendict(aFalse, bTrue, cTrue), frozendict(aTrue, bFalse, cTrue), frozendict(aTrue, bTrue, cFalse), frozendict({False: a, b: True, c: True}), frozendict({a: b, False: True, True: c}), ] hashes {hash(fd) for fd in cases} self.assertEqual(len(hashes), len(cases)) fd frozendict(x[1], y[2]) with self.assertRaisesRegex(TypeError, unhashable type: list): hash(fd) support.cpython_only def test_hash_cpython(self): # Check that hash(frozendict) implementation is: # hash(frozenset(fd.items())) for fd in ( frozendict(), frozendict(x1, y2), frozendict(y2, x1), frozendict(aFalse, bTrue, cTrue), frozendict.fromkeys(abc), ): with self.subTest(fdfd): self.assertEqual(hash(fd), hash(frozenset(fd.items())))test_hash验证哈希的顺序无关性、键值对区分度含False/True与键值互换的碰撞防护以及不可哈希值的TypeErrortest_hash_cpython验证哈希实现与hash(frozenset(fd.items()))的等价性这是frozendict_hash源码注释 Code copied from frozenset_hash() 的测试侧印证。test_or中还有合并运算符的其他行为断言与本修复同属一个功能面fd frozendict(x1, y2) self.assertIs(fd | frozendict(), fd) # 右侧为空短路返回原对象 self.assertIs(fd | {}, fd) # 右侧为空 dict短路返回原对象 self.assertIs(frozendict() | fd, fd) # 左侧为空短路返回原对象这些断言验证了frozendict_or中的两条短路优化分支——它们直接返回原对象因此天然携带正确的哈希缓存不在本次缺陷范围内。实践建议何时依赖hash(frozendict | frozendict)frozendict的典型用途包括作为不可变配置快照、作为dict的键或set元素、以及在多线程/异步场景中安全共享只读数据。|运算符用于函数式地合并映射不修改任何操作数。修复后以下模式可以安全使用base frozendict({host: localhost, port: 8080}) override frozendict({port: 9090}) merged base | override # frozendict({host: localhost, port: 9090}) cache_key hash(merged) # 稳定、与构造顺序无关 assert hash(merged) hash(frozendict({port: 9090, host: localhost})) # 顺序无关 registry {merged: service} # 可直接作为字典键 lookup frozenset({base | override}) # 可放入集合注意两个使用前提值的可哈希性frozendict的哈希要求所有值可哈希键本身必然可哈希。若值含list、dict等可变容器hash(fd)会抛TypeError此时应改用元组等不可变值。短路返回的对象fd | frozendict()返回fd本身assertIs级别hash结果自然与fd一致只有两侧均非空时才会走复制合并路径这也是本次修复真正覆盖的场景。总结gh-issue-149676 修复了 CPythonfrozendict在|合并路径上哈希缓存字段初始化缺失的问题使hash(frozendict | frozendict)与直接构造的等价 frozendict 保持一致。其技术要点可归纳为层面实现位置关键机制运算符入口Objects/dictobject.cfrozendict_or空字典短路 _PyDict_Or复制合并对象创建new_frozendict_untracked/new_dict_implma_hash -1初始化修复落点哈希计算frozendict_hash/frozendict_pair_hash缓存式、顺序无关、与frozenset(items)等价回归测试Lib/test/test_dict.pytest_orgh-149676 断言hash(a \| b) hash(frozendict({...}))对于需要把合并后的不可变配置作为键、缓存标识或集合元素的开发者而言此修复消除了一个隐蔽的正确性隐患而对 CPython 内部实现感兴趣的读者frozendict的哈希缓存模式不可变对象 原子惰性缓存也是值得借鉴的设计范式。【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考