frozendict_hash doesnt match the PEP and might have too many collisions

Bug report

Bug description:

in PEP 814, the provided pseudocode for hash(frozendict) is hash(frozenset(frozendict.items())), which makes sense, but the current implementation severely mismatches it in semantics:

cpython/Objects/dictobject.c

Lines 8246 to 8258 in b6854c5

    
           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); 
        
           }

just xoring the key and value hashes is very different from xoring the proper hashes of (key, value) pairs
the current implementation causes collisions to arise on permutations of keys and values separately rather than treating each entry as a single unit:

cases= [
  {"a": False, "b": True, "c": True},
  {"a": True, "b": False, "c": True},
  {"a": True, "b": True, "c": False},
  {False: "a", "b": True, "c": True},
  {"a": "b", False: True, True: "c"}
]
assert len({hash(frozendict(case)) for case in cases}) == 1

which is definitely not desirable, and potentially even exploitable for DOS attacks like string hashes were before randomization was added.

CPython versions tested on:

3.15

Operating systems tested on:

Linux

Linked PRs

I agree this is a poor-quality implementation, for the reasons you spelled out. But 'the obvious" fix is to build (key, value) 2-tuples and use the tuple hash's native result. That's based on how xxHash creates a hash from a stream, and passed extensive tests of "good behavior" in the presence of duplicate stream elements.

i did think of just reusing tuple hashing at first,
but i dont like the need for creating a tuple object, setting its items in the loop (and clearing the cached hash or recreating teh whole object), and doing 2 rounds of xxhash potentially lots of times, both for code simplicity and performance reasons
i think its worth using the given knowledge that we are only combining 2 hashes, and the hashes of the first elements are usually already different (since they're dict keys) to explore figuring out a solution that might be better than the obvious one

We're working at the C level here. A single tuple object can be created and reused across iterations. "Immutability" is a Python-level guarantee. C code routinely mutates little tuples it has total control over. Get it right first - speed it later if really necessary. A hash of a frozendict is going to be extraordinarily expense no matter how it's done.

i agree that things should be done right first, but i think boost::hash_combine is already "getting it right" and "fast", so i dont want to introduce error-prone tuple mutating code just because "hashing tuples" is the obvious solution
tuple xxhash might have a bit less collisions in some cases, but i dont think thats a priority
im sure some small changes can be made to _combine_hashes that would get it to be as well distributed as tuple xxhash without bringing in the complexity of dealing with mutating a tuple object, if the current solution is poorly distributed

@vstinner

cc @vstinner

Here's a little script that shows over 40,000 distinct "natural" frozendicts that all have the same hash code:

from itertools import permutations
N = 8
allhashes = set()
alldicts = []
for t in permutations(range(N)):
    d = dict(zip(range(N), t))
    assert d not in alldicts, d
    alldicts.append(d)
    allhashes.add(hash(frozenset(d)))
print(len(alldicts), len(allhashes)) # over 40K dicts, but just 1 hash code

And adding this at the end shows that xor'ing the (key, value) hashes instead suffers no collisions:

allhashes.clear()
for d in alldicts:
    h = 0
    for kv in d.items():
        h ^= hash(kv)
    allhashes.add(h)
print(len(allhashes))

In my first frozendict implementation, hash(frozenset(frozendict.items())) was not pseudo-code but the actual implementation of hash(frozendict). The problem of this implementation is that it mentioned set in the error message which is unexpected:

>>> fd=frozendict(x=[1], y=2)
>>> hash(frozenset(fd.items()))
TypeError: cannot use 'tuple' as a set element (unhashable type: 'list')

So when PEP 814 was accepted, I modified the implementation to avoid frozenset(), before merging frozendict implementation. The new error message is less surprising:

>>> hash(frozendict(x=[1], y=2))
TypeError: unhashable type: 'list'

I added // Code copied from frozenset_hash() comment to frozendict_hash(), because most of the code comes from frozenset_hash_impl().

I hesitated to reuse tuple_hash() code to create the hash of a (key, value) tuple.

Well, it seems like my implementation has flaws and the design should be revisited. Maybe we should reuse tuple_hash() code to compute (key, value) hash, to become closer to hash(frozenset(frozendict.items())) code again.

Maybe we should reuse tuple_hash() code to compute (key, value) hash, to become closer to hash(frozenset(frozendict.items())) code again.

I wrote PR gh-149841 to do exactly that. Does it look better?

I was originally reviewing to say "Maybe just repopulate a tuple and hash it to save repeated code", but as I wrote, realized that the copy over of the code enables additional optimizations you missed (specifically, using _PyDict_Next instead of PyDict_Next, with the former letting us skip getting the key entirely in favor of getting its cached hash and halving the hash computation work) that would meaningfully improve on reusing and rehashing a single tuple. So I'll say I like the approach, but I'd want to at least maximize the benefit, and make the tests actually verify the equivalence of hash(frozendict) == hash(frozenset(frozendict.items())), so the PEP guarantee is useful and to ensure no one can go about changing frozenset or tuple's hash algorithm (e.g. to improve on the _shuffle_bits) and miss your comments, leading to the implementations diverging.

gh-149807: Fix hash(frozendict): compute (key, value) pair hash (#149841

[3.15] gh-149807: Fix hash(frozendict): compute (key, value) pair hash (

@lambda-abstraction

Thanks @lambda-abstraction for your bug report. It should now be fixed.

Navigation Menu

Repository navigation

`frozendict_hash` doesnt match the PEP and might have too many collisions #149807

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	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);
	}

frozendict_hash doesnt match the PEP and might have too many collisions #149807

Description

Bug report

Bug description:

CPython versions tested on:

Operating systems tested on:

Linked PRs

Activity

tim-one commented on May 13, 2026

lambda-abstraction commented on May 13, 2026

tim-one commented on May 13, 2026

lambda-abstraction commented on May 13, 2026

picnixz commented on May 13, 2026

tim-one commented on May 14, 2026

vstinner commented on May 14, 2026

vstinner commented on May 14, 2026

MojoVampire commented on May 16, 2026

vstinner commented on May 20, 2026

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

`frozendict_hash` doesnt match the PEP and might have too many collisions #149807