什么是最快的，可移植的方式来哈希指针，我们知道是指针对准固定大小的整型？

Question

If we have a set of pointers we know are aligned to sizeof(void *) whats that fastest way to hash them?

Notes:

• Example use case is taking elements of a pointer array or memory allocations and storing in a hash-map. Noting this because this question isn't about the kind of cryptographic hashing needed for passwords, security etc.

• By fixed size int, I mean we know the exact size of the int and it wont vary (perhaps this is important since some hashing libraries use intptr_t or size_t for their hashing return values which might give a different answer to this question).

• By portable, this should work for 32, 64 bit, big & little endian.

• (uint32_t)(((intptr_t)p) >> 2) gives good results for 32bit, big endian, however I imagine it looses significant bits for 64bit systems, and I'm not sure if this gives a usable distribution for little endian.

转载于:https://stackoverflow.com/questions/53110781/whats-the-fastest-portable-way-to-hash-pointers-we-know-are-pointer-aligned-to

Answer 1

When mod math is fast, a quick hash is to mod by a prime <= TARGET_TYPE_MAX. The mod will use all the bits of the p to form the hash.

By using the largest prime, only a few buckets are lost, but speed is the goal.

Example, if the target tpye is uint32_t, use 4294967291u.

With variant sized integer types like int, use macros to select the precomputed prime. 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);