# Clarification on evenly dispersing modular hashing [duplicate]

I'm going over "Algorithms fourth edition" by Robert Sedgewick and Kevin Wayne.

In the chapter on hash tables I have encountered an easy hashing method called "modular hashing"

hash = k % m


Where k is the key and m - 1 is the size of array (minus 1) that stores the values. Authors suggest to use primary numbers for m because:

If m is not prime, it may be the case that not all of the bits of the key play a role, which amounts to missing an opportunity to disperse the values evenly.

I get why non-primary numbers might be a bad m. If we take a look at m = 10 and k = {17,27,37...}. They will all produce hash equal to 7.

However, I'm not entirely sure as to why primary numbers are superior alternative.

Is it because primary numbers are (due to their definition) never a divisor to the keys that we want to hash (ignoring instances where key=m)?

• The size of the array is $m$. The hash ranges between $0$ and $m-1$. Oct 17, 2020 at 15:37
• @YuvalFilmus thanks, I made a correction. Oct 17, 2020 at 15:48

The remark is quite cryptic. If $$m = 2^r$$, then only $$r$$ bits of the input affect the value of the hash. But it any other circumstance, all input bits affect the value of the hash.
By the way, your example ($$7,17,27,37$$ all get mapped to the same value modulo $$10$$) works for any value of $$m$$. For example, $$7,18,29,50$$ all map to the same value modulo the prime $$11$$.