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