why a good choice of mod is "a prime not too close to an exact of 2"

1.1k views Asked by At

To generate a hash function, Map a key k into one of m slots by taking the remainder of k divided by m. That is, the hash function is

h(k) = k mod m.

I have read at several places that a good choice of m will be

  1. A prime - I understand that we want to remove common factors, hence a prime number is chosen
  2. not too close to an exact power of 2 - why is that?
1

There are 1 answers

2
Salih Erikci On

From Introduction to algorithms :

When using the division method we avoid certain values of m. For example m should not be power of 2. Since if m=2^p then h(k) is p lowest-order bits of k. Unless it is known that all low-order p-bit patterns are equally likely,
it is better to make a hash function depend on all bits of the key.

As you se from the below image if i chose 2^3 which mean p=3 and m=8. The hashed keys are only dependent to lowest 3(p) bits which is bad because when you hash you want to include as much data as possible for a good distribution.

enter image description here