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

[lambda-abstraction]

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

• gh-149807 : frozendict_hash : hash (key, value) pairs rather than keys and values separately #149808
• gh-149807: Fix hash(frozendict): compute (key, value) pair hash #149841

[tim-one]

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.

[lambda-abstraction]

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

[tim-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.

[lambda-abstraction]

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

[picnixz]

cc @vstinner

[tim-one]

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

[vstinner]

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.

[vstinner]

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?