0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.