I'm a little late to the conversation, but I'll explain the reasoning. You don't want the hash and the bucket size to have a common divisor. A prime bucket si

I'm a little late to the conversation, but I'll explain the reasoning. You don't want the hash and the bucket size to have a common divisor. A prime bucket size is the best way to ensure that. For example, let's suppose you have a bucket size of 8 and a flawed hash function that produces multiples of 12 more often than other hashes (it can even be only slightly more common, but will still have an effect). Then the 0 and 4 spots will be used more often than any other. Obviously, if you have a super awesome hash function, then it isn't a problem. Most of the time, making a hash function with good distributive properties is hard and makes the hash function slower. There's also a simple universal hashing solution using prime bucket sizes: http://en.wikipedia.org/wiki/Universal_hashing http://en.wikipedia.org/wiki/Universal_hashing http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/VideoLectures/detail/embed08.htm http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...