` 如何正确计算每个 (key, value) 对的哈希)
frozendict 哈希修复hash(frozendict)如何正确计算每个 (key, value) 对的哈希【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython导读本文围绕 CPython 提交Misc/NEWS.d/next/Core_and_Builtins/2026-05-14-19-41-03.gh-issue-149807.IwGaCo.rst记录的变更Fix hash(frozendict)由 Victor Stinner 提交展开深入剖析frozendict不可变字典哈希计算的核心实现frozendict_pair_hash()如何基于(key, value)对哈希以及最终聚合算法如何在哈希值上确保键值对独立参与计算。读者将掌握hash(frozendict)的实现原理、其与tuple/frozenset哈希的关系、内部缓存的并发安全设计以及配套的测试验证方式。背景什么是frozendict为什么需要它可哈希frozendict是 CPython 内置于builtins中的不可变字典类型注册于 Python/bltinmodule.c 的SETBUILTIN(frozendict, PyFrozenDict_Type)。它的核心特征是构造完成后不允许任何形式的赋值d[k] v、删除del d[k]等修改操作源码中通过frozendict_does_not_support()统一抛出TypeError: frozendict object does not support item assignment/deletion见 Objects/dictobject.c。由于具备不可变性frozendict与frozenset、tuple一样具备成为哈希键的前提。而这一能力正是本次 NEWS 条目修复的核心让hash(frozendict)能够正确计算。在修复之前hash(frozendict)的实现存在缺陷——未能正确地把每个(key, value)对纳入哈希计算从而导致哈希值不正确例如可能退化为仅基于部分数据、或与其他对象产生错误的哈希冲突。修复的核心frozendict_pair_hash()与frozendict_hash()本次修复落在 Objects/dictobject.c 的frozendict专属哈希实现上。修复后frozendict的哈希由两个函数协作完成1.frozendict_pair_hash(key_hash, value)计算单个 (key, value) 对的哈希// 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; }这段代码的注释明确写道Code copied from tuple_hash()——它复用了tuple的 XXHASH 风格哈希算法即 Include/internal/pycore_tuple.h 中定义的_PyTuple_HASH_XXPRIME_1/_PyTuple_HASH_XXPRIME_2/_PyTuple_HASH_XXPRIME_5与_PyTuple_HASH_XXROTATE旋转宏把键的哈希与值的哈希按序混合等价于计算hash((key, value))。几个关键实现细节键的哈希key_hash由调用方_PyDict_Next()直接提供遍历字典时键哈希已被缓存因此无需重复调用PyObject_Hash(key)而值的哈希必须现场调用PyObject_Hash(value)。若某个值不可哈希PyObject_Hash(value)返回-1函数随即返回-1作为错误信号。这正是hash(frozendict(x[1]))抛出TypeError: unhashable type: list的根源。算法刻意保留-1作为错误码当计算结果碰巧为(Py_uhash_t)-1时会替换为固定值1546275796避免与错误码混淆。2.frozendict_hash()聚合所有 (key, value) 对的哈希// 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_hash()的注释是Code copied from frozenset_hash()聚合策略与frozenset完全同构遍历通过_PyDict_Next()遍历所有条目同时拿到每个键的缓存哈希key_hash和值value。逐对哈希对每个条目调用frozendict_pair_hash()即hash((key, value))。XOR 聚合每个pair_hash先经过_shuffle_bits()位扰乱((h ^ 89869747UL) ^ (h 16)) * 3644798167UL见 Objects/dictobject.c再与累计值hash做异或——这与frozenset对元素哈希的处理完全一致。混合与修正乘以条目数相关的因子、右移异或扩散hash ^ (hash 11) ^ (hash 25)、再经hash * 69069U 907133923UL线性混合用于分散嵌套frozendict中可能出现的规律性哈希模式。错误码保护最终结果若为-1则替换为590923713UL。正是这种“每个 (key, value) 对分别哈希后异或聚合”的设计让hash(frozendict)与hash(frozenset(fd.items()))数学上等价——这一点由测试显式锁定见下文测试章节。顺序无关性为什么hash(fd)与插入顺序无关由于聚合采用 XOR且每个pair_hash仅与键值内容有关而与遍历顺序无关hash(frozendict(x1, y2))恒等于hash(frozendict(y2, x1))。这在 Lib/test/test_dict.py 中有直接断言def test_hash(self): # hash() doesnt rely on the items order self.assertEqual(hash(frozendict(x1, y2)), hash(frozendict(y2, x1)))这与字典比较的语义frozendict(x1, y2) frozendict(y2, x1)为真保持一致保证了可哈希对象的基本契约相等的对象必须具有相等的哈希值。不可哈希值的传播错误处理路径哈希函数必须能如实反映“值不可哈希”这一事实。测试 Lib/test/test_dict.py 验证了错误传播fd frozendict(x[1], y[2]) with self.assertRaisesRegex(TypeError, unhashable type: list): hash(fd)在源码层面这一行为由frozendict_pair_hash()中的PyObject_Hash(value)返回-1后立即return -1实现Objects/dictobject.cfrozendict_hash()再将-1原样上抛最终由tp_hash槽位机制转换为TypeError: unhashable type: list。结果缓存与并发安全frozendict不可变因此其哈希结果在首次计算后保持不变可以安全缓存。PyFrozenDictObject中通过ma_hash字段保存首次调用时ma_hash -1触发完整计算计算完成后用FT_ATOMIC_STORE_SSIZE_RELAXED(self-ma_hash, ...)原子写入Objects/dictobject.c后续调用通过FT_ATOMIC_LOAD_SSIZE_RELAXED(self-ma_hash)直接返回缓存值Objects/dictobject.c。这套“先原子读、计算后原子写”的懒加载模式与frozenset的frozenset_hash()一致保证多线程环境下即使两个线程同时触发首次计算也不存在数据竞争最终写入的都是同一个确定值。这种模式之所以安全根本前提是frozendict的不可变性——若字典可变缓存必然失效。测试验证锁定正确行为本次修复配套的回归测试集中在 Lib/test/test_dict.py 的FrozenDictTests中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())))测试覆盖了四个维度顺序无关性hash(frozendict(x1, y2)) hash(frozendict(y2, x1))区分度一组仅键值组合不同的frozendict各自哈希互不相同len(hashes) len(cases)直接验证“每个 (key, value) 对都参与计算”——若修复前的实现漏算某些条目这一断言必然失败错误传播含列表值的frozendict求哈希抛出TypeError: unhashable type: list等价性CPython 专属hash(fd) hash(frozenset(fd.items()))从行为上精确锁定“逐 (key, value) 对哈希后聚合”的实现语义。小结本次gh-issue-149807修复的本质是让frozendict的哈希实现真正做到“compute the hash of each (key, value) pair correctly”微观层面frozendict_pair_hash()借用tuple_hash()的算法将键哈希与值哈希混合为hash((key, value))宏观层面frozendict_hash()借用frozenset_hash()的 XOR 聚合与位扩散最终与hash(frozenset(fd.items()))行为一致配合ma_hash的原子懒加载缓存使得这个不可变容器可以安全、高效地用作字典键或集合元素。对于需要把“不可变映射”当作哈希键的场景如记忆化缓存、配置去重、嵌套映射作为键修复后的frozendict是现成的正确选择而其测试用例test_hash/test_hash_cpython也值得作为理解 CPython 哈希约定顺序无关、错误传播、等价性的范本阅读。【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 frozendict 哈希修复：`hash(frozendict)` 如何正确计算每个 (key, value) 对的哈希
frozendict 哈希修复hash(frozendict)如何正确计算每个 (key, value) 对的哈希【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython导读本文围绕 CPython 提交Misc/NEWS.d/next/Core_and_Builtins/2026-05-14-19-41-03.gh-issue-149807.IwGaCo.rst记录的变更Fix hash(frozendict)由 Victor Stinner 提交展开深入剖析frozendict不可变字典哈希计算的核心实现frozendict_pair_hash()如何基于(key, value)对哈希以及最终聚合算法如何在哈希值上确保键值对独立参与计算。读者将掌握hash(frozendict)的实现原理、其与tuple/frozenset哈希的关系、内部缓存的并发安全设计以及配套的测试验证方式。背景什么是frozendict为什么需要它可哈希frozendict是 CPython 内置于builtins中的不可变字典类型注册于 Python/bltinmodule.c 的SETBUILTIN(frozendict, PyFrozenDict_Type)。它的核心特征是构造完成后不允许任何形式的赋值d[k] v、删除del d[k]等修改操作源码中通过frozendict_does_not_support()统一抛出TypeError: frozendict object does not support item assignment/deletion见 Objects/dictobject.c。由于具备不可变性frozendict与frozenset、tuple一样具备成为哈希键的前提。而这一能力正是本次 NEWS 条目修复的核心让hash(frozendict)能够正确计算。在修复之前hash(frozendict)的实现存在缺陷——未能正确地把每个(key, value)对纳入哈希计算从而导致哈希值不正确例如可能退化为仅基于部分数据、或与其他对象产生错误的哈希冲突。修复的核心frozendict_pair_hash()与frozendict_hash()本次修复落在 Objects/dictobject.c 的frozendict专属哈希实现上。修复后frozendict的哈希由两个函数协作完成1.frozendict_pair_hash(key_hash, value)计算单个 (key, value) 对的哈希// 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; }这段代码的注释明确写道Code copied from tuple_hash()——它复用了tuple的 XXHASH 风格哈希算法即 Include/internal/pycore_tuple.h 中定义的_PyTuple_HASH_XXPRIME_1/_PyTuple_HASH_XXPRIME_2/_PyTuple_HASH_XXPRIME_5与_PyTuple_HASH_XXROTATE旋转宏把键的哈希与值的哈希按序混合等价于计算hash((key, value))。几个关键实现细节键的哈希key_hash由调用方_PyDict_Next()直接提供遍历字典时键哈希已被缓存因此无需重复调用PyObject_Hash(key)而值的哈希必须现场调用PyObject_Hash(value)。若某个值不可哈希PyObject_Hash(value)返回-1函数随即返回-1作为错误信号。这正是hash(frozendict(x[1]))抛出TypeError: unhashable type: list的根源。算法刻意保留-1作为错误码当计算结果碰巧为(Py_uhash_t)-1时会替换为固定值1546275796避免与错误码混淆。2.frozendict_hash()聚合所有 (key, value) 对的哈希// 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_hash()的注释是Code copied from frozenset_hash()聚合策略与frozenset完全同构遍历通过_PyDict_Next()遍历所有条目同时拿到每个键的缓存哈希key_hash和值value。逐对哈希对每个条目调用frozendict_pair_hash()即hash((key, value))。XOR 聚合每个pair_hash先经过_shuffle_bits()位扰乱((h ^ 89869747UL) ^ (h 16)) * 3644798167UL见 Objects/dictobject.c再与累计值hash做异或——这与frozenset对元素哈希的处理完全一致。混合与修正乘以条目数相关的因子、右移异或扩散hash ^ (hash 11) ^ (hash 25)、再经hash * 69069U 907133923UL线性混合用于分散嵌套frozendict中可能出现的规律性哈希模式。错误码保护最终结果若为-1则替换为590923713UL。正是这种“每个 (key, value) 对分别哈希后异或聚合”的设计让hash(frozendict)与hash(frozenset(fd.items()))数学上等价——这一点由测试显式锁定见下文测试章节。顺序无关性为什么hash(fd)与插入顺序无关由于聚合采用 XOR且每个pair_hash仅与键值内容有关而与遍历顺序无关hash(frozendict(x1, y2))恒等于hash(frozendict(y2, x1))。这在 Lib/test/test_dict.py 中有直接断言def test_hash(self): # hash() doesnt rely on the items order self.assertEqual(hash(frozendict(x1, y2)), hash(frozendict(y2, x1)))这与字典比较的语义frozendict(x1, y2) frozendict(y2, x1)为真保持一致保证了可哈希对象的基本契约相等的对象必须具有相等的哈希值。不可哈希值的传播错误处理路径哈希函数必须能如实反映“值不可哈希”这一事实。测试 Lib/test/test_dict.py 验证了错误传播fd frozendict(x[1], y[2]) with self.assertRaisesRegex(TypeError, unhashable type: list): hash(fd)在源码层面这一行为由frozendict_pair_hash()中的PyObject_Hash(value)返回-1后立即return -1实现Objects/dictobject.cfrozendict_hash()再将-1原样上抛最终由tp_hash槽位机制转换为TypeError: unhashable type: list。结果缓存与并发安全frozendict不可变因此其哈希结果在首次计算后保持不变可以安全缓存。PyFrozenDictObject中通过ma_hash字段保存首次调用时ma_hash -1触发完整计算计算完成后用FT_ATOMIC_STORE_SSIZE_RELAXED(self-ma_hash, ...)原子写入Objects/dictobject.c后续调用通过FT_ATOMIC_LOAD_SSIZE_RELAXED(self-ma_hash)直接返回缓存值Objects/dictobject.c。这套“先原子读、计算后原子写”的懒加载模式与frozenset的frozenset_hash()一致保证多线程环境下即使两个线程同时触发首次计算也不存在数据竞争最终写入的都是同一个确定值。这种模式之所以安全根本前提是frozendict的不可变性——若字典可变缓存必然失效。测试验证锁定正确行为本次修复配套的回归测试集中在 Lib/test/test_dict.py 的FrozenDictTests中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())))测试覆盖了四个维度顺序无关性hash(frozendict(x1, y2)) hash(frozendict(y2, x1))区分度一组仅键值组合不同的frozendict各自哈希互不相同len(hashes) len(cases)直接验证“每个 (key, value) 对都参与计算”——若修复前的实现漏算某些条目这一断言必然失败错误传播含列表值的frozendict求哈希抛出TypeError: unhashable type: list等价性CPython 专属hash(fd) hash(frozenset(fd.items()))从行为上精确锁定“逐 (key, value) 对哈希后聚合”的实现语义。小结本次gh-issue-149807修复的本质是让frozendict的哈希实现真正做到“compute the hash of each (key, value) pair correctly”微观层面frozendict_pair_hash()借用tuple_hash()的算法将键哈希与值哈希混合为hash((key, value))宏观层面frozendict_hash()借用frozenset_hash()的 XOR 聚合与位扩散最终与hash(frozenset(fd.items()))行为一致配合ma_hash的原子懒加载缓存使得这个不可变容器可以安全、高效地用作字典键或集合元素。对于需要把“不可变映射”当作哈希键的场景如记忆化缓存、配置去重、嵌套映射作为键修复后的frozendict是现成的正确选择而其测试用例test_hash/test_hash_cpython也值得作为理解 CPython 哈希约定顺序无关、错误传播、等价性的范本阅读。【免费下载链接】cpythonThe Python programming language项目地址: https://gitcode.com/GitHub_Trending/cp/cpython创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考