What is the best way to cut down a hash to a desired size while retaining the quality of the original hash as much as possible?

Viewed 85

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);
}
0 Answers
Related