c - 64 位到 10 位的散列函数

Question

我想要一个哈希函数，它需要一个长数（64 位）并产生 10 位的结果。用于此目的的最佳哈希函数是什么。输入基本上是变量的地址（地址在 Linux 上是 64 位或 8 字节），所以我的哈希函数应该为此目的进行优化。

Answer 1

我会这样说：

uint32_t hash(uint64_t x)
{
    x >>= 3;
    return (x ^ (x>>10) ^ (x>>20)) & 0x3FF;
}

最不重要的 3 位不是很有用，因为大多数变量都是 4 字节或 8 字节对齐的，所以我们将它们删除。然后我们取接下来的 30 位并将它们混合在一起 (XOR)，每个块有 10 位。

当然，您也可以使用，(x>>30)^(x>>40)^(x>>50)但我不确定它们是否会在实践中产生任何影响。

Answer 2

我编写了一个玩具程序来查看堆栈、数据区和堆上的一些真实地址。基本上我声明了 4 个全局变量，4 个本地变量并做了 2 个mallocs。我在打印地址时丢掉了最后两位。这是其中一次运行的输出：

 20125e8
 20125e6
 20125e7
 20125e4
3fef2131
3fef2130
3fef212f
3fef212c
 25e4802
 25e4806

这告诉我什么：

1. 此输出中的 LSB（地址的第 3 位）经常处于“开”和“关”状态。所以在计算哈希时我不会放弃它。删除 2 个 LSB 似乎就足够了。
2. 我们还看到低 8-10 位有更多的熵。我们必须在计算哈希时使用它。
3. 我们知道，在 64 位机器上，虚拟地址永远不会超过 48 位宽。

我接下来会做什么：

/* Drop two LSBs.  */
a >>= 2;

/* Get rid of the MSBs. Keep 46 bits. */
a &= 0x3fffffffffff;

/* Get the 14 MSBs and fold them in to get a 32 bit integer.
The MSBs are mostly 0s anyway, so we don't lose much entropy.  */
msbs = (a >> 32) << 18;
a ^= msbs;

现在我们通过一个体面的“半雪崩”哈希函数传递它，而不是滚动我们自己的。“半雪崩”意味着输入的每一位都有机会影响相同位置或更高位置的位：

uint32_t half_avalanche( uint32_t a)
{
    a = (a+0x479ab41d) + (a<<8);
    a = (a^0xe4aa10ce) ^ (a>>5);
    a = (a+0x9942f0a6) - (a<<14);
    a = (a^0x5aedd67d) ^ (a>>3);
    a = (a+0x17bea992) + (a<<7);
    return a;
}

对于 10 位散列，使用uint32_t返回的 10 个 MSB。如果您为位散列选择 MSB，散列函数将继续正常工作，每增加一个位有效地将桶计数加倍。NN

我有点无聊，所以我为此写了一个玩具基准。没什么特别的，它在堆上分配了一堆内存并尝试了我上面描述的哈希。来源可以从这里得到。一个示例结果：

1024 个桶，生成 256 个值，29 个碰撞
1024 个桶，生成 512 个值，103 个碰撞
1024 个桶，生成 1024 个值，370 个碰撞

下一步：我尝试了这里回答的其他两个哈希值。他们都有相似的表现。看起来像：只选择最快的;）

Answer 3

最适合大多数发行版的是素数模数，1021 是最大的 10 位素数。无需剥离低位。

static inline int hashaddress(void *v)
{
        return (uintptr_t)v % 1021;
}

如果您认为性能可能是一个问题，请准备一些替代品并在您的实际程序中与他们比赛。微基准是浪费；几个周期的差异几乎肯定会被缓存效应淹没，并且大小很重要。