I read in several books and online pages that hash tables should use a prime number for the size. Nobody really justified this statement properly. Here’s my attempt!
I believe that it just has to do with the fact that computers work with in base 2. Just think at how the same thing works for base 10:
- 8 % 10 = 8
- 18 % 10 = 8
- 87865378 % 10 = 8
- 2387762348 % 10 = 8
It doesn’t matter what the number is: as long as it ends with 8, its modulo 10 will be 8. You could pick a huge power of 10 as modulo operator, such as 10^k (with k > 10, let’s say), but
- you would need a huge table to store the values
- the hash function is still pretty stupid: it just trims the number retaining only the first k digits starting from the right.
However, if you pick a different number as modulo operator, such as 12, then things are different:
- 8 % 12 = 8
- 18 % 12 = 6
- 87865378 % 12 = 10
- 2387762348 % 12 = 8
We still have a collision, but the pattern becomes more complicated, and the collision is just due to the fact that 12 is still a small number.
Picking a big enough, non-power-of-two number will make sure the hash function really is a function of all the input bits, rather than a subset of them.
Continue reading “Why hash tables should use a prime-number size”