Scalable Hash Functions

You’ve now seen how important it is that a hash function aligns with the size of a hash table’s underlying array. Now, determining the size of the array depends primarily on the number of values you expect to insert. In Volume 1, Chapter 8, I discussed the recommendation that a hash table should have 10 slots for every 7 pieces of data. (There are other recommendations out there, as well as other factors to consider when making this decision, but I won’t get into the nitty-gritty details here.)

Once you determine the array size, you need to carefully choose a hash function that will distribute values uniformly across the array.

If, for instance, we decided that our underlying array should have 500 slots, the hash function we used earlier would be downright terrible. After all, that function can only possibly insert values into indexes 0 through 9! Our remaining 490 array slots would never be used.

In truth, even if a hash function distributed values across the length of the array but couldn’t—for whatever reason—hash a value into the number 79, this hash function is considered to be deficient. In computer science jargon, we’d say that such a hash function lacks uniformity. The ideal hash function should be designed so that each slot in the array will likely contain the same number of items, or at least close to it.

So, how do you come up with a hash function that caters to the size of the array and ensures uniformity?