The Division Method

There are many hash functions out there that are considered effective. In this chapter, we’ll focus on one particular hash function design. It’s simpler than most of the alternative approaches, but still effective.

The hash function I’ll demonstrate doesn’t have a fancy name, but is often called Division Hashing or the Division Method. There are several variants and optimizations of this method, but I’ll present it in its most basic form.

Before we start, let’s define a couple of variables. We’ll use the variable K to refer to the integer we’re hashing, and M will refer to the size of the array. Although I personally would have chosen other alphabet letters, these are the variables that are often used in the literature.

Division hashing takes K and applies the following formula:

In other words, we divide the integer we’re hashing by the size of our array. Yes, that’s it.

Let’s see how this plays out with some examples. Say that M is 89. If K (the integer we’re hashing) is 1632, we get:

That is, when we divide 1632 by 89, we get a remainder of 30. So, 30 is our hash code.

This is an effective hash function, as it caters to the size of the array and is uniform. Let me explain.

When we divide a number by 89, the resulting remainder is guaranteed to be some integer from 0 up through 88, inclusive. Now, this is perfect for our underlying array, which has that same range of indexes, namely, 0 through 88. So, it makes a lot of sense to hash K by simply dividing it by the array size (M) since the remainder will match one of our array’s indexes.

Also, the distribution is uniform, and here’s why. In our example, K was 1632, and we got a hash code of 30. Let’s see what happens when we keep increasing K by 1:

Let’s skip a few steps to where K is 1688:

Once K is 1691, we get a remainder of 0, and then start the cycle again. So, if we were to insert all the integers from 0 to 1690, they’d be uniformly distributed across indexes 0 through 88. The same applies to all values greater than 1690 as well.

M Should Be Prime

One commonly recommended optimization to the Division Method is that we should make sure that M is a prime number. Even if we’ve determined that the size of our array needs only to be 10, it is usually worth it to increase M to 11 since 11 is prime.

Without getting too much into number theory, the basic reason for this is a concern that if M is not prime, our data may follow a nonuniform pattern. This happens in particular if all instances of K (that is, all the items in our data set) and M are both divisible by some other number, such as 12 and 9 being both divisible by 3.

Here’s an example that highlights this concern. Say that our data consists exclusively of even integers. This isn’t so hard to imagine; perhaps we have a list of test scores where it was only possible to get an even-numbered score.

If each test score is even, this means that each score is divisible by 2. And if M is, say, 10, then M is also divisible by 2.

Now, let’s also say that our test scores are [2, 4, 6, 8, 10, 12, 14, 16]. Here’s what happens when we hash them when M is 10:

It turns out that we’ll only place values in even-numbered indexes of the array. The odd slots of the array will never be used. As we’ve learned, this hinders the effectiveness of a hash function.

Let’s look at one more example. Say that our test scores are all divisible by 3, such as [12, 15, 18, 21, 24, 27, 30]. If M is 9, which is also divisible by 3, our hash codes end up being:

Yikes! We’ll only be storing values in the array’s 0, 3, and 6 indexes. Most of the array will never be used.

We can solve much of this issue by making M a prime number. If M is prime, we can never have the issue where the data and M are both divisible by the same third number, for a prime number isn’t divisible by any other number!

And so, if we make M prime, such as 11, we’ll see that our integer distribution becomes uniform:

Every single hash code from 0 through 10 is computed once.

The same holds true for other data patterns, such as with the earlier example of even-numbered test scores:

It emerges that making M prime helps distribute data uniformly even when the data follows certain patterns. Now, don’t forget that M represents the size of the array. So, this means that we’re making sure that the array size itself is prime.

However, this trick of making M prime doesn’t solve the uniformity issue for all patterns.