Why large prime numbers are used in hash tables
Hash tables store objects in buckets. Which bucket an object ends up in depends on the hash value for the object.
To transform a hash value to a valid bucket index you typically just compute modulo
numBuckets represents the number of buckets in the hash table.
Hash tables perform best when objects are spread evenly among the buckets. A hash function should therefore strive for this goal.
Large hash values
A hash function that only returns small values, say between 0 and 10, does not achieve a good spread if
numBuckets becomes greater than 10.
To maintain a good spread when there’s a large number of buckets, hash functions typically scale up the values by multiplying with a large prime number.
Why prime numbers?
If we scaled up the values by a composite number (non-prime), say 1000, there would be many values for
numBuckets where the scale would be “cancelled out” in the mod operation. 1000 %
numBuckets = 0 for
numBuckets = 2, 4, 5, 8, 10, … In other words, similar objects would get similar bucket indexes. This reduces the spread and makes for a poor hash function.
By choosing a large prime number, we avoid this problem, since a prime number is not divisible by
numBuckets happens to be a multiple of that particular prime number.