Why a good choice of mods is "just not too close to exact 2",

Question

To create a hash function, move the key k to one of the m slots, taking the remainder k divided by m. That is, the hash function

h (k) = k mod m.

In several places I read that a good choice for m would be

• Simple - I understand that we want to remove common factors, so a prime number is chosen
• not too close to exact power 2 - why?

Answer 1

From introduction to algorithms:

When using the division method, we avoid certain values ​​of m. For example, m should not have degree 2. Since , if m = 2 ^ p, then h (k) is p the least significant bits of k. If it is not known that all the lower p-bit patterns are equally likely ,
it is better to make a hash function dependent on all bits of the key.

As you see the image below, if I chose 2 ^ 3, which means p = 3 and m = 8. The hashed keys depend only on the lower 3 (p) bits, which is bad because when you use the hash, you want to enable as much as possible more data for good dissemination.