efficient 16 bit hash [closed]

Question

I'm looking for a way to make a 16bit ID out of approx 100 bits of data. The solution should be easy to implement, or should already be implemented in c++, should be quick to evaluate, and most importantly the values of the ID should be uniformly distributed, which is to say that one value should not have a higher chance to be taken than another.

Answer 1

As mentioned in the question Rook linked, 16bits is very very weak, reducing 100bits to 16 leads to ~6 possible collisions per hash.

Are you sure you need a hash for that ? 16bits is enough to be stored in an integer and could simply be incremented if you just need a way to identify an object (limited to 65536).

If nevertheless you want to use an hash function, you could try to use something very simple such as Pearson hashing that will produce a 8bit hash.

h := 0
for each c in C loop
  index := h xor c
  h := T[index]
end loop
return h

I quote Wikipedia, the advantages of this function are :

• It is extremely simple.
• It executes quickly on resource-limited processors.
• There is no simple class of inputs for which collisions (identical outputs) are especially likely.
• Given a small, privileged set of inputs (e.g., reserved words for a compiler), the permutation table can be adjusted so that those inputs yield distinct hash values, producing what is called a perfect hash function.

The adaptation to 16bits shouldn't be too hard. For example, this page gives an example of adaptation but I think the author forget to change the size of the table to 65535, the code would be :

static unsigned short T[] = {
    // The values 0..65535 shuffled into random order.
};

static inline unsigned hashOf(unsigned h,const char* s) {
    for (int c = *s++; c; c = *s++) {
        h = T[h ^ (65535 & c)];
    }
    return h;
}