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.