Search code examples
c++algorithmhashuint32

Commutative hash function for uint32_t value pairs

I need a fast, simple hash function that creates a unique identifier for a pair of uint32_t values - so the same hash value for (2,7) and (7,2).

Any idea?

Solution

  • To answer my own question, the solution is:

    uint64_t hash(uint32_t x, uint32_t y)
{
    const uint64_t a = static_cast<uint64_t>(x);
    const uint64_t b = static_cast<uint64_t>(y);

    if (x < y) return (b << 32) | a;
    else return (a << 32) | b;
}

    Which can be improved to the branchless version

    uint64_t hash(uint32_t x, uint32_t y)
{
    const uint64_t a = static_cast<uint64_t>(x);
    const uint64_t b = static_cast<uint64_t>(y);

    const uint64_t h0 = (b << 32) | a;
    const uint64_t h1 = (a << 32) | b;

    return (x < y) ? h0 : h1; // conditional move (CMOV) instruction
}

    These methods are perfect hash functions - they guarantee zero collisions. However, they have the disadvantage that you cannot hash values above 2^32 - 1.