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

Question

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?

Thermopylae

Answer 1

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.

Hurleigh

You describe the case that m is exactly 2^p, not the case when m is close to 2^p, as asked. – Handicraftsman

But it is still (almost) true. Computing a mod 2^n-1 is same as grouping the number in chunks of n-bits and adding those groups. – Tavares