I have a hash function that takes 64-bit input and outputs 64-bit integer. The hash table's size is 2 ^ 16 = 0x10000, so I can't use the whole 64-bit hash. I have to cut down to 16-bits, but I want to keep the quality of the original hash as much as possible, so that it's randomly and equally distributed.
With a hash function,
uint64_t hash64(uint64_t);
I can use the lower bits,
uint16_t hash16_low(uint64_t a) {
return hash64(a) & 0xffff;
}
or maybe using higher bits is better,
uint16_t hash16_high(uint64_t a) {
return hash64(a) >> 0x30;
}
or I can split the hash and merge with xor. At least no information is lost completely this way,
uint16_t hash16_splitXor(uint64_t a) {
uint16_t b[4];
memcpy(b, &a, sizeof(uint64_t));
return *b ^ b[1] ^ b[2] ^ b[3];
}
or there is a better way. What is the best way to achieve this?
As a reply to a comment by @dratenik, this is the hash function I'm using, which is a specialization of fast-hash for 64-bit input with a seed of 0x5555555555555555. I'm not sure about its cryptographic qualities, and it's not meant for such use, but at least it's statistically well-tested. Will it be enough to take either higher or lower bits?
static inline uint64_t xorShift64_(uint64_t a, int sh) {
return a ^ a >> sh;
}
static inline uint64_t hash64_mix_(uint64_t a) {
return xorShift64_(xorShift64_(a, 23) * 0x2127599bf4325c37u, 47);
}
static inline uint64_t hash64_(uint64_t a) {
const uint64_t m = 0x880355f21e6d1965u;
return hash64_mix_((hash64_mix_(a) ^ m * 8 ^ 0x5555555555555555u) * m);
}