# Choosing the right function

I'm trying to hash integers n = 4k(0,4,8,12,16...) into an array of linked lists of size 4 (chaining). What is a good hasing function that guarantees a good distribution of the keys? that means to use all indexes of the array from 0 to 3.

No hash function can guarantee a good distribution. All you can do is finding a hash function that will usually create a good distribution.

The table size is quite important for this: If the table size is a prime p, then just using n modulo p as the hash value is usually quite good. Note that in your case, 4 is not a prime. Actually all your values are multiples of the table size. And if you has pointers for example, then it is quite possible that all pointers are multiples of 8 or 16, so having a table size of 4, 8 or 16 is not clever.

Obviously if your integers are multiples of 4, but with all four possible values modulo 16 being equally minded, then (n / 4) modulo 4 would work quite well. But in general, you should avoid an unfortunate table size like the one you have.