c++ - uint32_t 値ペアの可換ハッシュ関数

Question

値のペアの一意の識別子を作成する高速で単純なハッシュ関数が必要です。つまり、とuint32_tの同じハッシュ値です。(2,7)(7,2)

何か案が？

Answer 1

私自身の質問に答えるには、解決策は次のとおりです。

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

ブランチレスバージョンに改善できるもの

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
}

これらのメソッドは完全なハッシュ関数であり、衝突がゼロであることを保証します。ただし、 を超える値をハッシュできないという欠点があります2^32 - 1。