c-我们所知道的将指针对齐到固定大小int的哈希指针的最快、可移植的方法是什么

Question

如果我们有一组已知的指针与sizeof(void *)对齐，那么散列它们的最快方法是什么？

注：

• 示例用例是获取指针数组或内存分配的元素并存储在哈希映射中。注意到这一点，因为这个问题不是关于密码、安全等所需的加密哈希。

• 对于固定大小的int，我的意思是我们知道int的确切大小，并且它不会变化(也许这很重要，因为一些哈希库使用intptr_t或size_t作为其哈希返回值，这可能会对这个问题给出不同的答案(

• 通过便携式，这应该适用于32，64位，大&小endian。

• (uint32_t)(((intptr_t)p) >> 2)对32位大端序给出了很好的结果，但我认为它对64位系统失去了有效位，我不确定这是否为小端序提供了可用的分布。

Answer 1

当mod数学很快时，快速哈希是通过prime <= TARGET_TYPE_MAX进行mod。mod将使用p的所有比特来形成散列。

通过使用最大素数，只会损失几个桶，但速度是目标。

例如，如果目标tpye是uint32_t，则使用4294967291u。

对于像int这样的可变大小整数类型，使用宏来选择预计算的素数。素数不到二次方。

#define LARGEST_PRIME8 251u
#define LARGEST_PRIME15 32749u
#define LARGEST_PRIME16 65521u
#define LARGEST_PRIME31 2147483647u
#define LARGEST_PRIME32 4294967291u
#define LARGEST_PRIME63 9223372036854775783u
#define LARGEST_PRIME64 18446744073709551557u
uint32_t hash = (uint32_t) ((uintptr_t)(void *)p) % LARGEST_PRIME32);

Answer 2

如果您可以创建64位输入->64位输出限制，那么mumur3哈希终结器函数具有非常好的属性。

这是64位的(来自这里的讨论：http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)

UInt64 MurmurHash3Mixer( UInt64 key )
{
key ^= (key >> 33);
key *= 0xff51afd7ed558ccd;
key ^= (key >> 33);
key *= 0xc4ceb9fe1a85ec53;
key ^= (key >> 33);
return key;
}

关于发现此类函数的一些额外讨论，包括32位->32位变体。https://nullprogram.com/blog/2018/07/31/

在谷歌上搜索"全面雪崩"或"mumur3混合vs.…"等术语，会让你读到似乎无限多的东西。

还有一个链接：如何创建自定义Murmur雪崩混音器？