https://github.com/python/cpython/commit/8e211b1ca93401d46009b556d648d12c679a132b
commit: 8e211b1ca93401d46009b556d648d12c679a132b
branch: main
author: Victor Stinner <[email protected]>
committer: vstinner <[email protected]>
date: 2026-02-17T18:39:33+01:00
summary:
gh-141510: Optimize hash(frozendict) (#144919)
hash(frozendict) no longer creates a temporary items view and a
temporary frozenset object.
Copy frozenset_hash() code to frozendict_hash().
files:
M Lib/test/test_dict.py
M Objects/dictobject.c
M Objects/setobject.c
diff --git a/Lib/test/test_dict.py b/Lib/test/test_dict.py
index 1db3559a012fd3..2a106a8a4e8739 100644
--- a/Lib/test/test_dict.py
+++ b/Lib/test/test_dict.py
@@ -1775,6 +1775,15 @@ class MyFrozenDict(frozendict):
d = MyFrozenDict(x=1, y=2)
self.assertEqual(repr(d), "MyFrozenDict({'x': 1, 'y': 2})")
+ def test_hash(self):
+ # hash() doesn't rely on the items order
+ self.assertEqual(hash(frozendict(x=1, y=2)),
+ hash(frozendict(y=2, x=1)))
+
+ fd = frozendict(x=[1], y=[2])
+ with self.assertRaisesRegex(TypeError, "unhashable type: 'list'"):
+ hash(fd)
+
if __name__ == "__main__":
unittest.main()
diff --git a/Objects/dictobject.c b/Objects/dictobject.c
index 62abb793d002e0..f7a359e4a1a40d 100644
--- a/Objects/dictobject.c
+++ b/Objects/dictobject.c
@@ -7881,33 +7881,55 @@ frozendict_repr(PyObject *self)
return res;
}
+static Py_uhash_t
+_shuffle_bits(Py_uhash_t h)
+{
+ return ((h ^ 89869747UL) ^ (h << 16)) * 3644798167UL;
+}
+
+// Code copied from frozenset_hash()
static Py_hash_t
frozendict_hash(PyObject *op)
{
PyFrozenDictObject *self = _PyFrozenDictObject_CAST(op);
- Py_hash_t hash = FT_ATOMIC_LOAD_SSIZE_RELAXED(self->ma_hash);
- if (hash != -1) {
- return hash;
+ Py_hash_t shash = FT_ATOMIC_LOAD_SSIZE_RELAXED(self->ma_hash);
+ if (shash != -1) {
+ return shash;
}
- PyObject *items = _PyDictView_New(op, &PyDictItems_Type);
- if (items == NULL) {
- return -1;
- }
- PyObject *frozenset = PyFrozenSet_New(items);
- Py_DECREF(items);
- if (frozenset == NULL) {
- return -1;
+ PyDictObject *mp = _PyAnyDict_CAST(op);
+ Py_uhash_t hash = 0;
+
+ PyObject *key, *value; // borrowed refs
+ Py_ssize_t pos = 0;
+ while (PyDict_Next(op, &pos, &key, &value)) {
+ Py_hash_t key_hash = PyObject_Hash(key);
+ if (key_hash == -1) {
+ return -1;
+ }
+ hash ^= _shuffle_bits(key_hash);
+
+ Py_hash_t value_hash = PyObject_Hash(value);
+ if (value_hash == -1) {
+ return -1;
+ }
+ hash ^= _shuffle_bits(value_hash);
}
- hash = PyObject_Hash(frozenset);
- Py_DECREF(frozenset);
- if (hash == -1) {
- return -1;
+ /* 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, hash);
- return hash;
+ FT_ATOMIC_STORE_SSIZE_RELAXED(self->ma_hash, (Py_hash_t)hash);
+ return (Py_hash_t)hash;
}
diff --git a/Objects/setobject.c b/Objects/setobject.c
index 5d4d1812282eed..f8713bf3d1a432 100644
--- a/Objects/setobject.c
+++ b/Objects/setobject.c
@@ -964,7 +964,10 @@ _shuffle_bits(Py_uhash_t h)
This hash algorithm can be used on either a frozenset or a set.
When it is used on a set, it computes the hash value of the equivalent
- frozenset without creating a new frozenset object. */
+ frozenset without creating a new frozenset object.
+
+ If you update this code, update also frozendict_hash() which copied this
+ code. */
static Py_hash_t
frozenset_hash_impl(PyObject *self)
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
