1
$\begingroup$

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)?

Improve this question
$\endgroup$
2
  • $\begingroup$ The size of the array is $m$. The hash ranges between $0$ and $m-1$. $\endgroup$
    – Yuval Filmus
    Oct 17, 2020 at 15:37
  • $\begingroup$ @YuvalFilmus thanks, I made a correction. $\endgroup$
    – Stargarth
    Oct 17, 2020 at 15:48

1 Answer 1

Reset to default
0
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good point on my flawed example. That makes me even more confused as to why primary numbers are superior. There seems to be something to them as authors reiterate on this point multiple times and they provide an array of examples where hashes with m=97 seem to be much more uniform than those with m = 100. $\endgroup$
    – Stargarth
    Oct 17, 2020 at 15:53

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