c - 什么是散列指针的最快、可移植的方法，我们知道指针与固定大小的 int 对齐？

Question

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

注意事项:

• 示例用例是获取指针数组或内存分配的元素并将其存储在 HashMap 中。注意到这一点是因为这个问题与密码、安全性等所需的加密散列类型无关。

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

• 通过便携，这应该适用于 32 位、64 位、大端和小端。

• (uint32_t)(((intptr_t)p) >> 2) 给出了 32 位大字节序的良好结果，但我想它会丢失 64 位系统的重要位，而且我'我不确定这是否为 little endian 提供了一个可用的分布。

Answer 1

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

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

例如，如果目标类型是 uint32_t , 使用 4294967291u。

具有变体大小的整数类型，如 int , 使用宏来选择预先计算的素数。 Primes just less than a power of two .

#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);