HashMaps and primality — when & why?

Recently I was posed an interesting question during an interview for a graduate software engineering position. It would be unfair to say which company this was and so I will cryptic-crossword-clue-ify the name by saying finished novel before resounding characteristic of my stride. Anyway(!), I thought I’d share my thoughts on a particular (perhaps bogus) question from that experience.

So we got talking about the inner guts of how a HashMap might work. We talked about a (deliberately) naïve approach to the hash function which would take the reference of the object—an integer, r—and put it in bucket number n where n = abs(r) (mod N) where N is the number of buckets in the implementation. The question posed was:

What would be a suitable choice for N, the number of buckets in the Map?

We talked about it a bit and didn’t get very far until I was led to the answer that choosing N such that it is prime would be the best choice. At this point the other interviewer pipes up and exclaims that this isn’t useful or correct which got me thinking about whether choosing N prime makes any difference in minimising the number of collisions produced by our hash function. My gut was that I agreed with the objection to the question.

I went home and put my thinking hat on and came to a conclusion.

Read More