Randomized Hashing

Despite our best efforts, it’s still possible to have a data set in which a given hash function will not distribute the data with ideal uniformity. Let’s look at some examples.

Example 1: If M is 11, and our data is [55, 22, 99, 88, 11, 66, 44, 77, 33], all the data will end up at the array’s index 0 since all these integers of our data set are divisible by 11. We’ve mentioned that uniformity gets messed up when the data set and M are both divisible by a common third number. However, it’s also problematic if all the data is divisible by M itself.

Example 2: Let’s keep M at 11, but use the data set of [56, 23, 100, 89, 12, 67, 45, 78, 34]. This data set is the data set from Example 1, except that each integer has been increased by 1. When we divide each of these numbers by 11, we get a common remainder of 1.

Example 3: Even if the data were a mix of Examples 1 and 2, all of the data will hash into either 0 or 1. This is pretty bad, as we’ll be using just 2 out of the 11 available slots in the array. That is, all data would end up at index 0 or index 1 and not anywhere else.

One might brush this off by claiming that the odds of having these types of data sets are slim. Indeed, that may be true if the data were picked randomly. However, as I pointed out earlier, it’s not unreasonable to have exam scores that are all divisible by the same number.

Furthermore, there are security issues to consider. If we have a high-volume web application that depends on a hash table to allow for lookup speeds of O(1), a nefarious hacker may be able to pull the rug out from under us. If the hacker knows precisely what hash function we’re using, the hacker can purposely feed our app data where all the data ends up in the same slot of the underlying array. This could slow down our app to the point where we can only search in O(N) time, and our app might conk out due to the heavy load.

In short, computer scientists are horrified by the possibility of a data set on which a given hash function performs poorly.

Fortunately, there’s a solution to this problem. And once again, randomization comes to the rescue.

The concept of randomized hashing says that when we create an instance of a hash table, we randomly pick the hash function that the hash table will use for the remainder of the hash table’s existence.

I mentioned earlier that there are many different hash functions out there. Now, each hash function has a weak spot, which is the particular data set for which the hash function will not distribute the data uniformly. The idea behind randomized hashing, though, is that each hash function has a different weak spot. So, even if we have a data set that won’t work well with Hash Function #1, it’ll work out fine if we instead use Hash Function #2.

If we have, say, 100 hash functions to choose from, even if our particular data set won’t work well with Hash Function #48, that may be okay. Since we’re going to pick a hash function randomly out of a hat, the odds of us picking Hash Function #48 for our hash table are only 1 out of 100.

So, with randomized hashing, when we instantiate a new hash table, the hash table will randomly pick the hash function it’ll use. And once it decides on a hash function, it must use that hash function forever. If we hashed each key using a different hash function, we’d never be able to find those keys ever again unless we knew what hash function we used for each key. And that’s certainly not something we want to keep track of.

When we write code that uses multiple hash tables, it’s likely that each hash table is using a different hash function. But again, each hash table will stick with its unique hash function forever.

Hash Function Families

For a hash table to pick a random hash function, we need to first create a pool of potential hash functions to choose from. One way we could do this is to create a list of many of the different known hash functions out there. The Division Method is one viable hash function, but there are plenty of others, some of which have rather interesting names like MurmurHash, CityHash, FarmHash, and SpookyHash.

However, there’s a simpler way to create a pool of hash functions. That is to create what is called a hash function family. A hash function family is a group of hash functions that all use the same general hashing method, except that they differ with regard to some other detail. This will make more sense with an example, so let’s go ahead and create a hash function family out of division hashing.

Our approach will be to have lots of different hash functions that all use the Division Method, but each hash function will divide values by different numbers.

Let’s go back to our earlier example where M was 89. If K is 412341439, we’ve learned that we’d compute K % M like so:

Now, we can’t create other hash functions that have a different M. Remember, M corresponds to the size of our hash table’s underlying array. If the underlying array has 89 slots, we’re stuck dividing all of our values by 89.

However, we can modify our division formula slightly so that we’re going to perform not one, but two modulo operations. To do this, we’re going to choose a second prime number, which we’ll call P, and run the following formula:

For our example, we’ll say that P is 10061, which is a prime number. This gives us:

Thus, the hash code comes out to be 80.

This new variable, P, becomes the key to creating a hash function family. Specifically, we can create multiple hash functions where each hash function uses a different value for P. While they must all use the same value for M, there’s no reason why they can’t have different Ps. Let’s see how this allows us to create a hash function family and eventually solve our problem of division hashing working poorly for a particularly unlucky data set.

Continuing with our example of M being 89, let’s create five different hash functions. Each hash function will have one of the following possible P’s: 10037, 10039, 10061, 10067, or 10069. When each of these hash functions hashes the same K of 412341439, we end up with five different hash codes:

At the same time, since each hash function also divides the results by the same M of 89, we ensure that each hash code will all be within the range of 0 through 88. Again, this is exactly what we want if our hash table is to distribute values into indexes 0 through 88.

And so, we’ve successfully created an effective hash function family. In sum, this family consists of the following five hash functions:

Naturally, we can create hundreds of hash functions along these lines. We need to find hundreds of prime numbers that can fill in for P. And indeed, those prime numbers exist; there are plenty of prime numbers to go around.

With all this in mind, it’s pretty straightforward for the computer to select a hash function at random. All it needs to do is choose a random value for P. By picking a random P, we’ve effectively picked a random hash function. This is true even though it’s already fixed that the hash function’s general strategy will be to employ division hashing.

Let me bring this all back and spell out how we’ve solved our problem. Again, our concern was that there might be a data set out there that simply doesn’t get distributed uniformly by our chosen method of hash function, such as division hashing, for example. Imagine, for example, that M was 89 and all the integers in our data set were divisible by 89. If we decide to use the Division Method for our hashing approach, all the integers would get shoved into index 0!

By having our hash table pick a P at random, there are high odds that the Division Method will indeed distribute a given data set uniformly. We’d only get messed over if the items in our data set were all divisible in the same way by both M and P. Besides being extremely unlikely, it can in any case no longer be said that there might be a data set that doesn’t distribute well with the Division Method. The Division Method would indeed work well for almost any P that we end up selecting.

And that makes one big, happy, hash function family.

Code Implementation: Randomized Hash Functions

It turns out that it takes relatively minimal code to implement random hashing, at least at a basic level:

Let’s take a stroll through the code.

We’ve created a DivisionHasher class that acts as a “machine” that hashes a value (which in our code is referred to as key) into a hash code. The DivisionHasher class accepts an array_length variable that represents what we’ve been calling M—that is, the length of a hash table’s underlying array. To make things a little easier on us, we rely on the user to tell us what they want their hash table size to be.

The next bit of code implements the randomization part of random hashing. As we did earlier, our approach to random hashing is to pick a random prime P that will be used for the computation of K % P % M. This P effectively defines which hash function from our family we’ll be using. Here, we randomly pick P and assign it to the variable self.prime:

Here’s how we pick a random prime. We choose a random integer between 1000 and 10000. For this basic proof-of-concept example, we’re assuming that the integers being hashed are all greater than 1000. For other types of integers, this range would have to be adjusted.

We then ensure that the integer is prime by continuously picking integer after integer until we find one that’s prime. This uses a helper method called is_prime.

Now, here’s the fun part: how does the is_prime method work? Well, it uses Fermat’s Primality Test, which we looked at in the previous chapter! Cool beans.

The real action of our code, though, is the hash method. This method accepts a key and returns a hash code using the snippet:

This should look pretty familiar. It’s our formula of K % P % M!

It should also be noted that this hash method only works on a key that’s an integer. If you wanted to hash a string, for example, you’d first perform some computation to convert the string to an integer. You could, theoretically, do this by converting each character to its corresponding ASCII code and then multiplying or summing all the ASCII codes together. We’ll explore this more in the next chapter.

I’ll emphasize that this entire implementation is bare-bones, and there are many optimizations that can—and should—be made. My goal here, though, is to simply present code that conveys the main ideas of this chapter.

Code Implementation: Bare-Bones Hash Table

Now that we’ve gotten this far, we may as well have fun by building our own hash table from scratch. Again, you are way better off using Python’s built-in dictionary, but this code implementation is here to help concretize the concepts you’ve learned so far.

We’ll create our own hash table in two passes. First, we’ll implement a hash table that is extremely basic but demonstrates how it makes use of the DivisionHasher class. Then, we’ll add a couple more features (but the result will admittedly still be pretty bare-bones).

First Pass

Here’s the first basic hash table implementation:

Like the DivisionHasher class, this HashTable relies on the user to decide the size of the hash table’s underlying array. This is the argument array_length.

Here’s the constructor:

First, we create the underlying array, which we call self.array. We give it the size of array_length and fill each slot with None for now.

Next, we save array_length as the instance variable self.array_length since we’ll need to access it later.

Then, we choose which hash function our hash table will use. Here, we’re using the DivisionHasher class we implemented earlier, which represents the division hash function family. However, we could easily swap this out for some other hash function family as long as we use a class that implements a hash function. In any case, our hash function gets stored in a variable called self.hasher.

Next, we have the insert method. We allow a user to insert a key-value pair into the hash table using code like this:

That is, we’ll insert a key of 55 which has a corresponding value of 17. Although throughout our discussion in this chapter, we’ve assumed that the key and value are identical, in real life, the key and value are usually different, as is the case here.

Here, again, is the insert method:

First, we use self.hasher to hash the key into a hashcode.

Then, we place the value into the self.array at the index which is the hashcode. So, if the hashcode for 55 is 9, then the value of 17 will be placed at index 9.

We also implement a search method, which allows a user to look up a value by its key, such as:

This will return 17.

In this first pass, the code for the search method is short and is similar to the insert method:

Here, we hash the key and get a hashcode. This hashcode represents the index in self.array where our desired value will be found, so we go find it there.

Second Pass

Here’s a slightly better HashTable, but again, I’ll emphasize that it’s still not nearly as robust as the real deal.

This version adds two important features. One is a delete method since it’s pretty common to delete keys from a hash table. The other is that we now handle collisions of keys, a problem I discussed in Volume 1, Chapter 8. In short, the issue of collisions is that it’s possible for two different keys to be hashed into the same hash code. This means that we have to somehow fit both values into one array slot.

One approach for handling this is called separate chaining, which stores multiple values in each array slot using another array (or linked list), which I’ll call a “subarray.”

Here’s the specific way we’ll do this. If our hash table has five slots, each slot will itself start out holding an empty array, like so:

Furthermore, we’ll need to store not just the values but also the keys so that we can identify which value goes to which key.

So, let’s say that we insert the following key-value pairs:

If both keys 3 and 9 hash into the same hash code, say 0, here’s what the hash table’s underlying array will look like:

That is, in each subarray we’ll add a key-value pair in the form of yet another array (a sub-subarray, I guess), where index 0 is the key and index 1 is the value.

Here’s the code:

As you can see, a significant change in this version is that in the constructor, instead of filling each slot of self.array with None, we fill it with a blank subarray. This way, we can hold multiple key-value pairs in each slot of self.array.

This has ramifications for all the methods of our class. In the insert method, we now don’t simply insert a value but append to the subarray another array that contains the key and value. Hence, the code: self.array[hashcode].append([key, value]).

To improve the insert method further, I also provided the ability to overwrite a key and give it a new value:

For example, we may decide that the value associated with the key 3 should now be "z" instead of "a".

Separate chaining also changes the way we search for values. In the updated search method, you’ll note the newly added code that peers inside the proper slot of self.array and performs a linear search to find the correct key-value pair.

Lastly, I added a delete method. For example, if we want to delete the key of 3, we’d call the delete method like this:

The delete method hashes the key into a hashcode and then searches for the key inside the appropriate slot of self.array. If we find the key, we delete the entire key-value pair from self.array.

And so, we’ve created our own hash table from scratch. While it’s not nearly as good as a Python dictionary, and you don’t want to use it in real life, going through the process can help you better understand how hash tables work under the hood.