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。如果您为 N 位哈希选择 N MSB，则哈希函数将继续正常工作，每增加一位，就会有效地使存储桶计数翻倍。

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

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

下一篇： 我尝试了这里回答的其他两个哈希值。它们都具有相似的性能。看起来像：只需选择最快的一个;)

Answer 3

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

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

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