Skip to content

Bad collisions for frozenset hashes #150134

Description

@tim-one

Bug report

Bug description:

This came up long ago when I was working on hardening the tuple hash, but got dropped on the floor.

It recently came up again in the context of frozendict haahing, which just copied much of the frozenset hashing code:

#149841

The problem is that shuffle_bits() only propagates changes from low-order bits to higher. Any function using only left shifts and multiplies suffers from this.

But hash codes may differ only in high-order bits to begin with. Avalanche is horrid in the absence of a stronger bit shuffler, which also propagates higher-to-lower.

It so happens that hash codes of low-precision floats do suffer from this.

>>> len(set(hash(i/256) for i in range(256))
256

So they're all different, but the variation is only in the topmsot bits:

>>> for i in range(10):
...     print(hex(hash(i/256)))
...
0x0
0x20000000000000
0x40000000000000
0x60000000000000
0x80000000000000
0xa0000000000000
0xc0000000000000
0xe0000000000000
0x100000000000000
0x120000000000000
>>>

So frozenset struggles with them. First block of output from the code at the end, which analyzes the hashes of frozensets of all ways of taking 3 elements from those 256 floats (of course it doesn't matter if the same values are spelled as Fraction and/or Decimal instead).

number of possible hash codes: 18_446_744_073_709_551_616

 number of hash codes total: 2_763_520
number of unique hash codes: 2_048
       number of collisions: 2_761_472

mean expected collisions: 0.00
            and its sdev: 0.00
                       z: +6069500754.14

worst pileups:
    2_020
    2_015
    2_005
    2_005
    2_002
    2_001
    1_999
    1_993
    1_988
    1_980

The z score is crazy high, but "pileups" matter much more than that. That's the number of distinct inputs that map to the same hash code. It's the length of collision chains the drive catastrop;ic slowdowns, not really the number of collisions.

The second block of output shows what happens instead if we just xor together the hashes of 1-tuples containing the same values:

number of possible hash codes: 18_446_744_073_709_551_616

 number of hash codes total: 2_763_520
number of unique hash codes: 2_753_525
       number of collisions: 9_995

mean expected collisions: 0.00
            and its sdev: 0.00
                       z: +21968232.90

worst pileups:
    4
    4
    3
    3
    3
    3
    3
    3
    3
    3

The z score is still very high, but max pileup has become quite minor. Move to 4-element subsets and max pileup for frzenset zooms to over 100 thousand, while the xor of 1-tuple hashes peaks at a modest 13.

Tuple hashing doesn't do full-blown xxHash. In the full version, there's a long stretch at the end to work harder at avalanche. The per-element version tuple uses skips that. There's some useful left-to-right propagation via its rotate operation, but for 1-element tuples that's a "one and done" thing. High-order bits can't affect low-order ones further away than the one-tiee rotate count, Its effect in this context is nevertheless dramatic.

So what to do? If the problem is lack of left-to-right propagation, introduce some. Everyone else does ;-)

  • Roll our own. Even one ju8icious right shift could help a lot. Rohate (as in xxHash) even more (rotate propagates in both directions).

  • Look at adopting the tail end of xxHaah.

  • The C++ Boost library's combine_hashes() also propagates in both directions.

  • As does the "tempering" code before the Mersenne Twister delivers a result. The underlying generator is very slow at propagating bit changes across the state space, so they tacked on a "heavy avalanching sequence" to disguise that weakness. But even so it can very famously fall into "zeroland regions" (if most of state space bits happen to become zero, it cah take millions of iterations to break free of that).

As for frozendict, it doesn't appear to need any of this. The current PR uses a much stronger scheme based on copy/pasting two rounds of tuple's xxHash code, one round for the key hash and another to fold in the value hash. That's bound to be stronger than just (as in the attached code) xor'ing the hashes of 1-tuples, and it's almost certainly a complete waste of cycles to go on to call shuffle_bits() now. The propagation it does is weak (and zero of left-to-rght) compared to xxHash's core.

At a higher level, the spread of copy/pasted "mystery code" across modules is concerning. I'm old enough to know where all the bodies are buried, but the next generation isn't. If we have to duplicate code (and typically without enough comments to trace the code back to its original source), let's at least stick it in a new include file? Then there's just one place to look for comprehensive explanations and cautions - and no possibility of getting out of sync by accident. This kind of code is the opposite of "obvious" 😉.

Driving code:

from test import support
from collections import Counter
import math

def fint(n):
    return f"{n:_}"

def analyze(hashcounts, nbins=1<<support.NHASHBITS):
    print("number of possible hash codes:", fint(nbins))
    assert all(hashcounts.values()) # counts of 0 not allowed
    print()
    numtotal = hashcounts.total()
    numseen = len(hashcounts)
    ncollision = numtotal - numseen
    print(" number of hash codes total:", fint(numtotal))
    print("number of unique hash codes:", fint(numseen))
    print("       number of collisions:", fint(ncollision))
    print()
    mean, sdev = support.collision_stats(nbins, numtotal)
    print("mean expected collisions:", format(mean, ".2f"))
    print("            and its sdev:", format(sdev, ".2f"))
    diff = ncollision - mean
    z = diff / sdev
    print("                       z:", format(z, "+.2f"))
    print()
    print("worst pileups:")
    for h, c in hashcounts.most_common(10):
        print("   ", fint(c))

N, K = 8, 3
from itertools import combinations
def create(N=N, K=K):
    c = Counter()
    pow2 = 1 << N
    small = tuple(i / pow2 for i in range(pow2))
    for t in combinations(small, K):
        c[hash(frozenset(t))] += 1
    assert c.total() == math.comb(pow2, K)
    return c

def create2(N=N, K=K):
    c = Counter()
    pow2 = 1 << N
    small = tuple(i / pow2 for i in range(pow2))
    for t in combinations(small, K):
        h = 0
        for e in t:
            h ^= hash(tuple([e]))
        c[h] += 1
    assert c.total() == math.comb(pow2, K)
    return c

analyze(create())
analyze(create2())

CPython versions tested on:

CPython main branch, 3.14, 3.13

Operating systems tested on:

No response

Linked PRs

Activity

  1. added
    type-bugAn unexpected behavior, bug, or error
    performancePerformance or resource usage
    on May 20, 2026
  2. tim-one commented on May 20, 2026

    @tim-one
    MemberAuthor

    Google's Gemini pointed me at these 2 64-bit mixers as "best of general breed" for avalanche quality (every input bit affects every output bit.

    SplitMix64 / MurmurHash3

    #include <stdint.h>
    
    uint64_t mix64(uint64_t x) {
        x ^= x >> 30;
        x *= 0xbf58476d1ce4e5b9ULL;
        x ^= x >> 27;
        x *= 0x94d049bb133111ebULL;
        x ^= x >> 31;
        return x;
    }

    Nasam

    uint64_t fast_mix64(uint64_t x) {
        x ^= x >> 32;
        x *= 0xd6e8feb86659fd93ULL;
        x ^= x >> 32;
        return x;
    }

    The latter is fastest, but of "slightly" lower quality. Two things they have in common:

    1, No left shifts. Only right shifts. That's what gives "left to right" propagation.
    2. "Right to left" is done by multiplication, which is much stronger than left shifting.

    Nasm in fact does worse than than tuple-based approach on the challenging 4-subsets of 256 case in my driver:

    number of possible hash codes: 18_446_744_073_709_551_616
    
     number of hash codes total: 174_792_640
    number of unique hash codes: 168_345_771
           number of collisions: 6_446_869
    
    mean expected collisions: 0.00
                and its sdev: 0.03
                           z: +224027103.54
    
    worst pileups:
        61
        33
        31
        25
        24
        22
        22
        21
        21
        20
    

    Far better than our scramble_bits(), though, and possibly acceptable.

    Murmur does best of all, but appears slightly more expensive than our xxHash-based tuple core (both have two multiplies, but murmur a little more shift-xor action than xxHash's slngle rotate).

    number of possible hash codes: 18_446_744_073_709_551_616
    
     number of hash codes total: 174_792_640
    number of unique hash codes: 174_792_640
           number of collisions: 0
    
    mean expected collisions: 0.00
                and its sdev: 0.03
                           z: -0.03
    
    worst pileups:
        1
        1
        1
        1
        1
        1
        1
        1
        1
        1
    

    In fact, it's perfect! No collisions, and max pileup of 1 (the smallest possible). @rhettinger,, what do you think? Nasam may be even faster than what we have now, but Murmur is in a whole different universe of avalanche quality.

    Here's the murmur code I used:

    def murmur(x, mask=2**64-1):
        x &= mask # emulate unsigned; not needed in C
        x ^= x >> 30
        x *= 0xbf58476d1ce4e5b9
        x &= mask # retain only low 64 bits; not needed in C
        x ^= x >> 27
        x *= 0x94d049bb133111eb
        x &= mask # retain only low 64 bits; not needed in C
        x ^= x >> 31
        return x
    
    def create4(N=N, K=K):
        c = Counter()
        pow2 = 1 << N
        small = tuple(i / pow2 for i in range(pow2))
        for t in combinations(small, K):
            h = 0
            for e in t:
                h ^= murmur(hash(e))
            c[h] += 1
        assert c.total() == math.comb(pow2, K)
        return c
    
    analyze(create4())
  3. tim-one commented on May 21, 2026

    @tim-one
    MemberAuthor

    I wrote code to test "avalanche" on random 64-bit inputs. Ideally, a 1-bit change in an input should change around 32 bits in the output. And for all bit position pairs, flipping bit i in the input should flip bit j in the output about half the time.

    murmur does very well on that, with actual (i, j) counts differing from the expected ideal mean by at worst 3 standard deviations. (using a normal distribution approximation to a p=0..5 binomial distribution) Since there are 4096 position pairs, seeing some $\pm 3$ deviations is expected.

    Nasam does very well on average number of bits changed (very close to 32), but has extremely out-of-whack (i, j) counts at times, hundreds of sdevs from the expecte4 mean. ( think Gemini hallucinated that Nasam was only "slightly" weaker than murmur.

    Our shuffle_bits() didn't really aim at avalanche, just a bit of right-to-left propagation - and it shows ;-) For almost all i , flipping bit i affects bit j sometimes never, sometimes always, across 100 thousand trials, leading to z scores in the hundreds.. An extreme is flipping bit position 63,. which doesn't change any output bit other than 63 (no left-to-right propagation at all). The average number of bits changed was 16.7, about half the idea;l.

    Unless I transcribed the C code to Python incorrectly, but I don't think that's it. Here's what I used

    def shuffle_bits(h, mask=2**64-1):
        x = h ^ 89869747
        y = h << 16
        y &= mask
        h = (x ^ y) * 3644798167
        h &= mask
        assert h.bit_length() <= 64
        return h

    If that's wrong, let me know! Several things suggest it would do poorly at avalanche:

    • No left-to-right propagation.
    • Only one "strong" right-to-left step (the multiply).
    • Using a multiplier with only 32 bits.

    murmur stands alone, but it's not perfect. It's not "crypto strength" avalanche, and seemingly can't be with so few operations. While in my comb(256,, 4) subsets "bad case", it gives unique 64-bit hash cades, a set with 2**n slots only looks at the last n bits for the first probe, and murmur's results are not ideal in the lower order bits., Some collisions are inevitable (pigeonhole) then, and murmur's is about 10z higher then. But worst pileup is just 8, which is thoroughly acceptable.

    The hash probe sequence does its own "left-to-right" propagation, by folding in higher-order bits as it goes along,. and the more it does fold in, the smaller the z scores deviate from "really random" inputs. By the time it folds in 39 bits, the collision z score was only +0.75, and at 49 bits they're unique again. So the initial pileups will resolve as the probe sequence goes along.

  4. tim-one commented on May 22, 2026

    @tim-one
    MemberAuthor

    I was mistaken to call this "mumur". It's actually SplitMix64, which is structurally the same as one member of the MurMur family, but uses different constants, derived from deep analysis and mountains of statistical testing.

    Cute: by design it gets much closer to 50% probability of flipping each output bit (given a 1-bit input change) than a "truly random" mixer would. Took me by surprise! I ran chi-square tests on a matrix recording how often a change in input bit i caused a change in output bit j, and the chi-square statistic for each row was almost always "impossibly low".

    So lots of double- and triple-checking, then more searches. It all makes sense now 😃 .

    It can also be used a decent 64-bit PRNG with very small state (64 bits):

    |https://prng.di.unimi.it/splitmix64.c

  5. pinned this issue on May 22, 2026
  6. tim-one commented on May 22, 2026

    @tim-one
    MemberAuthor

    Recapping, SplitMix64 is best-of-breed, and does spectacularly well on the sets-of-floats problem case here. It's industry-standard,, very widely deployed,. and is well-grounded in academic theory, with people working on it from Guy Steele to Sebastian Vigna and Melissa O'Neil (of PCG fame,). There's every reason to expect it will defeat all patterns that show up in real life.

    Bite the bulled. I don't really care that it may take 12 cycles (on a box with 3-cycle 64x64->64 IMUL, which is no longer cutting edge). In this case, we'd get better protection against catastrophic slowdowns than we'd pay for. It's much better at spreading out input differences than one round of xxHash's core too (which is expected - you get no more than you pay for 😉:, and xxHash's core has 5 fewer bit-fiddling ops).

  7. tim-one commented on May 23, 2026

    @tim-one
    MemberAuthor

    Move to 4-element subsets and max pileup for frozenset zooms to over 100 thousand,

    Let's make that very clear - it's not just unlucky, it's certain to be extremely bad.

    All the hash codes for these floats have at least 53 trailing zero bits. All the variation is in their top 11 bits. Regardless of how many are xoir'ed together (from 0 through 256), the same is true of their xor reduction: because shuffle_bits() does no left-to-right propagation, all xor's of a subset's shuffled hashes will also have at least 53 trailing zero bits. So only 2**11 = 2048 final hash codes are possible. In the case of 4-subsets,.

    >>> import math
    >>> math.comb(256, 4)
    174792640
    >>> _/2**11
    85347.96875

    So, by a pigeonhole argument, there must be at least 85348 subsets with the same 64-bit hash code. That's already a disaster - 100K is only a little bit unluckier than the ideal theoretical lower bound.

    It's remarkable that splitmix64 manages to deliver a unique hash code for each 4-siubset.

  8. unpinned this issue on May 23, 2026
  9. zware commented on May 23, 2026

    @zware
  10. pinned this issue on May 23, 2026
  11. unpinned this issue on May 23, 2026
  12. gvanrossum commented on Nov 11, 2026

    @gvanrossum
    Member

    This Issue was Tim's last contribution ever.

  13. added a commit that references this issue on Nov 12, 2026
  14. skyvegetable666 commented on Nov 12, 2026

    @skyvegetable666

    I have a patch for this that follows the SplitMix64 approach analysed in this
    issue (fmix32 on 32-bit builds). One deviation from the mix64 snippet above:
    I add SplitMix64's additive "golden gamma" before mixing so that a zero hash
    does not map to zero; I'm happy to drop it if preferred.

    The new mixer gives unique hashes for the {i/256} subsets (64-bit) and
    near-random ones on 32-bit; large frozensets hash about 1.6-1.8x slower
    (pyperf numbers will be in the PR), while the pathological case is about 2x
    faster. Please let me know if someone is already working on this; otherwise
    I'll open a PR shortly.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usagetype-bugAn unexpected behavior, bug, or error

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions