How To Break Arithmetic Symmetry With Subtraction

Why Your Hash Collisions Keep Happening

I spent three days tracking down a collision bug in a particle simulation system last year. The code was combining position coordinates using simple integer addition to produce bucket indices. Two particles at positions (3, 7) and (7, 3) landed in the exact same bucket every time. It wasn't even a subtle edge case — it happened constantly because the hash function had perfect arithmetic symmetry baked into it. The fix wasn't adding more complex math. It was swapping addition for subtraction in the mixing step. Arithmetic symmetry in hashing or checksum calculations happens when the result of an operation is invariant under reordering of its inputs. Addition is commutative. So is XOR. Both are deeply problematic when you're trying to produce a distribution that scatters similar inputs across different buckets. Subtracting one value from another instead of adding them introduces order-dependence and directional bias that destroys that symmetry. Here's the mechanics. When you combine two integers a and b with addition, you get a + b. Swap them, you get the same result. With subtraction, a - b and b - a produce opposite values. That single property breaks the symmetry that causes collisions in spatial partitioning, hash tables, and even procedural generation seeds.

The practical implementation looks like this. Instead of writing a hash combine function that does result = result + value, you write result = result - value. Or more usefully, you alternate between subtraction and other operations so the final result depends on the order of inputs.

// Symmetric — bad for hashing
uint32_t hash_symmetric(uint32_t a, uint32_t b) {
    return a + b;
}

// Asymmetric — breaks symmetry
uint32_t hash_asymmetric(uint32_t a, uint32_t b) {
    return a - b;
}

The second version will give you different results when you swap a and b. That's the whole point. In a hash table with a million entries, that difference is the gap between distribution and a cluster of collisions around specific input patterns. I encountered a more painful version of this in a physics engine I was debugging. The broad-phase collision system used an AABB grid where the grid cell was computed as floor(position / cell_size). Multiple objects with coordinates that summed to the same value but in different orders would map to the same cell. The naive fix was to add a multiplication step, but that introduced its own problem — large products overflowed and created new collision clusters. The actual fix was to use a subtraction-based mixing function before the modulo operation:

uint32_t mix(uint32_t x) {
    x = (x ^ 61) ^ (x >> 16);
    x = x + (x << 3);
    x = x ^ (x >> 4);
    x = x * 0x27d4eb2d;
    x = x ^ (x >> 15);
    return x;
}

uint32_t hash_coord(float x, float y, float z) {
    uint32_t hx = mix(reinterpret<uint32_t&>(x));
    uint32_t hy = mix(reinterpret<uint32_t&>(y));
    uint32_t hz = mix(reinterpret<uint32_t&>(z));
    // Subtraction breaks the symmetry between (x,y,z) and permutations
    return hx - hy - hz;
}

This was based on the MurmurHash3 finalizer approach, which explicitly uses subtraction and XOR to diffuse bits rather than just adding them together. The subtraction step is what prevents the input permutations from collapsing into identical hash values. There are trade-offs you need to be aware of. Subtraction alone doesn't provide full diffusion. If your inputs are highly correlated — like consecutive frame numbers or regularly spaced grid coordinates — subtraction can still produce patterns. I found this out the hard way when switching from addition to subtraction in a timeline system where event IDs were sequential integers. The hash distribution looked fine visually but had a periodic clustering every 256 entries because subtraction preserves certain linear relationships that a proper mixing function would destroy. The solution was to combine subtraction with a bitwise rotation and a constant multiplier. Here's the pattern I ended up using consistently:

uint32_t combine(uint32_t a, uint32_t b) {
    return (a - b) ^ (b <11) ^ (a * 0x85ebca6b);
}

This single function breaks arithmetic symmetry through subtraction, introduces non-linearity through multiplication, and adds bit diffusion through the XOR and shift. It's compact enough to use in tight loops and fast enough that the CPU branch predictor doesn't complain. If you're working in a language without unsigned integer wraparound guarantees, subtraction behaves differently. In C and C++, unsigned integer subtraction is well-defined and wraps around modulo 2^N. In languages like Python or JavaScript, you need to mask the result manually to get the same behavior. I've seen people skip this masking step and then wonder why their hash distributions degrade on 64-bit platforms compared to 32-bit. The real test for whether you've successfully broken arithmetic symmetry is simple. Take two input sets that differ only in the order of their elements. If they produce the same hash, you haven't broken the symmetry. If they produce different hashes, you've succeeded. Run this test on your specific use case — it's faster than debugging collisions after deployment.

I also recommend checking your hash output against a known-good distribution metric. The chi-squared test for uniformity will tell you in seconds whether your asymmetric hash function is actually producing uniform output or just random-looking garbage. A well-designed subtraction-based hasher should hit the expected bin counts within 5% on any reasonable dataset.