Hash 32bit int to 16bit int?

Question

What are some simple ways to hash a 32-bit integer (e.g. IP address, e.g. Unix time_t, etc.) down to a 16-bit integer?

E.g. hash_32b_to_16b(0x12345678) might return 0xABCD.

Let's start with this as a horrible but functional example solution:

function hash_32b_to_16b(val32b) {
    return val32b % 0xffff;
}

Question is specifically about JavaScript, but feel free to add any language-neutral solutions, preferably without using library functions.

The context for this question is generating unique IDs (e.g. a 64-bit ID might be composed of several 16-bit hashes of various 32-bit values). Avoiding collisions is important.

Simple = good. Wacky+obfuscated = amusing.

Answer 1

I think this is the best you're going to get. You could compress the code to a single line but the var's are there for now as documentation:

function hash_32b_to_16b(val32b) {
    var rightBits = val32b & 0xffff; // Left-most 16 bits
    var leftBits = val32b & 0xffff0000; // Right-most 16 bits

    leftBits = leftBits >>> 16; // Shift the left-most 16 bits to a 16-bit value

    return rightBits ^ leftBits; // XOR the left-most and right-most bits
}

Given the parameters of the problem, the best solution would have each 16-bit hash correspond to exactly 2^16 32-bit numbers. It would also IMO hash sequential 32-bit numbers differently. Unless I'm missing something, I believe this solution does those two things.

I would argue that security cannot be a consideration in this problem, as the hashed value is just too few bits. I believe that the solution I gave provides even distribution of 32-bit numbers to 16-bit hashes

Answer 2

Something simple like this....

function hash_32b_to_16b(val32b) {    
    var h = hmac(secretKey, sha512);
    var v = val32b;
    for(var i = 0; i < 4096; ++i)
        v = h(v);
    return v % 0xffff;
}

Answer 3

I would say just apply a standard hash like sha1 or md5 and then grab the last 16 bits of that.

Answer 4

Assuming that you expect the least significant bits to 'vary' the most, I think you're probably going to get a good enough distribution by just using the lower 16-bits of the value as a hash.

If the numbers you're going to hash won't have that kind of distribution, then the additional step of xor-ing in the upper 16 bits might be helpful.

Of course this suggestion is if you're intending to use the hash merely for some sort of lookup/storage scheme and aren't looking for the crypto-related properties of non-guessability and non-reversability (which the xor-ing suggestions don't really buy you either).

Answer 5

This depends on the nature of the integers. If they can contain some bit-masks, or can differ by powers of two, then simple XORs will have high probability of collisions. You can try something like (i>>16) ^ ((i&0xffff) * p) with p being a prime number.

Security-hashes like MD5 are all good, but they are obviously an overkill here. Anything more complex than CRC16 is overkill.