Why should hash functions use a prime number modulus?
Asked 07 September, 2021
Viewed 2.4K times
  • 60
Votes

A long time ago, I bought a data structures book off the bargain table for $1.25. In it, the explanation for a hashing function said that it should ultimately mod by a prime number because of "the nature of math".

What do you expect from a $1.25 book?

Anyway, I've had years to think about the nature of math, and still can't figure it out.

Is the distribution of numbers truly more even when there are a prime number of buckets?

Or is this an old programmer's tale that everyone accepts because everybody else accepts it?

16 Answer