Quick point: the reason to use primes is to avoid a nasty interaction between a common fault of hash functions and the modulus. Specifically, if the hash funct

Quick point: the reason to use primes is to avoid a nasty interaction between a common fault of hash functions and the modulus. Specifically, if the hash function puts out a lot (e.g. more than appropriate for a uniform distribution) of hash values that have a common factor F, and if F also a factor of your modulus, then you've divided your number of buckets by F for those many hash values. It seems a little obscure until we look at common factors like 2 or 4. It's pretty easy to write a hash function, that when combined with its input (say ASCII text, or addresses returned by malloc()), puts out a lot of values that divide by a power of two. To avoid it, without doing any analysis of your hash function or input, a prime factor adds safety. Thanks to this: http://primes.utm.edu/notes/proofs/Theorem2.html http://primes.utm.edu/notes/proofs/Theorem2.html you know that if n is prime, then so's 2^n-1. So, for a prime n, a cheap prime modulus for computers is to do a bitwise and with ((1 << n) -1).