The Hash Table
Before delving into how a distributed hash table can function, it is imperative that one understands how hashing itself works. In this page, we'll describe hashing at its most basic level.
What is hashing?
Hashing is one of the most fundamental concepts in Computer Science. From data storage, to cryptography and security, to algorithms and much more, pretty much every sector of Computer Science utilizes hashing in some way or another.
At its core, hashing amounts to mapping data from an arbitrarily large space to a fixed size space. In other words, it transforms some input, no matter how small or large, to an input of a specific size and format.
Hash functions
Hashing is performed using hash functions. As described above, hashing is a transformation of an input from some space to another, therefore a function is the tool we're looking for to achieve this.
A hash function accepts data in some format (for instance, strings) and returns what we call a hash digest, or simply hash. A hash can be an integer, a string, or any other data type, but in its most general form, it is data (bytes).
Let's look at an example of a simple hash function. We'd like to provide some string of arbitrary size as an input, but get an integer in the range [0, 7] as an output.
The idea behind this hash function is simple: we'll assign a number to each character in the string, sum up the numbers and get the result of that sum modulo 8. This will result in an integer between 0 and 7.
For the sake of argument, let's assign 1 to the character a and 0 to every other character. Let's call this new hash function H1. We'll now apply our newly created hash function to some inputs:
- H1("Mary") = 1
- H1("John") = 0
- H1("Elise") = 0
- H1("Eleanor") = 1
Notice how multiple inputs can give the same output? We call this a collision and it is a fundamental problem in hashing.
Hash function quality
In fact, when attempting to map inputs from a space of infinite size to outputs from a space of finite size, it's obvious that most often, every output will have infinite inputs mapped to it. This is simply an unavoidable fact.
This, however, does not mean that all hash functions are equal in quality. Since we'd rather not have any collisions, we rank the quality of a hash function based on how many collisions it produces (with relation to our input of interest).
Take a look at our hash function from before. You might think that this isn't a good hash function and, for most inputs, you'd probably be right. But consider your input space being strings which contain an arbitrary number of as. For such input, this hash function is optimal.
In general, however, a hash function like this wouldn't be very useful. A much better one we can use here would assign each character its integer Unicode value. Let's call that function H2. Using this hash function, here are the values for the same names:
- H2("Mary") = 1
- H2("John") = 7
- H2("Elise") = 2
- H2("Eleanor") = 6
Now, every name has its own value. This produces no collisions, which is a significantly better result than that of H1.
Hash tables
A hash table is a data structure that stores data in key-value pairs. It does this by using a hash function to transform the key, then using the transformed key to find the location where the value is saved.
If this sounds complicated, let's take a look at an example. Assume the four names we used above are those of students. Each of them has received a grade in our class, so we want to save their names along with their grades, such that when one of them asks us for their grade, we can quickly tell them what it is.
We'll use our hash function from before, H2. Because H2 can produce 8 possible values, we'll create an array of size 8.
After this, we'll apply H2 to each of the names, which gives us the numbers seen above. We'll use each number as an index to the array, saving both the name and the grade at that position.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Mary: C | Elise: B | Eleanor: A | John: B |
The next time one of these students asks us for their grade, we can simply hash their name, instantly go to the position the resulting hash indicates and get their grade.
This might not seem like it's much of an improvement, but imagine having thousands of students instead of just four. If your hash table was large enough, you could get the grade for one pretty much instantly. The alternative would be looking through a list of thousands of students, which would certainly take longer.
Collisions
We mentioned before that we don't like collisions. Why is that?
The answer to that question depends on your use case. To understand this for hash tables, we'll add another student to our example. Let's assume Jared also took the test and was graded. We want to add him to our hash table, so the first step is hashing his name.
- H2("Jared") = 6
We notice that the value we got for his name is the same as that for Eleanor's. If we go to position 6 of our hash table, we've already saved Eleanor's grade there.
There are multiple different approaches to solve this issue, but we'll use the one called chaining. This entails simply adding his name after hers, in a list, at that same position. The resulting array looks like this:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| Mary: C | Elise: B | Eleanor: A Jared: B |
John: B |
Even though this works, it creates a certain problem. When Jared asks us for his grade, we hash his name and end up in position 6. There, we notice that the first grade is not his, but Eleanor's. We need to keep looking through the list to find his name and give him his grade. This makes it so that the process takes longer than it otherwise would.
This is the reason we want to avoid collisions. Each collision means that two different keys get the same value and, for a hash table, this increases the time it takes to look for a key's value.
How to deal with collisions
The most common approach to dealing with collisions is simply increasing the output space. If, for instance, our hash function returned the sum modulo 128 and our array was size 128, each student in our example would get their own unique position in the hash table.
This approach works, but only if our hash function is decent enough to distribute inputs over the output space evenly. If we used H1 instead, we'd still have multiple collisions, even if we increased the array size significantly.
In general, collisions are unavoidable, especially the more data we add. However, to keep the hash table's search functionality close to linear, we try to have a balance between hash function quality and hash table size.
Why hash tables?
We already saw how a hash table makes searching for a student's grade much faster in our previous example. Let's define the time and space complexity of a hash table more rigorously.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | Θ(1) | O(n) |
| Insert | Θ(1) | O(n) |
| Delete | Θ(1) | O(n) |
Even though the worst case complexity for these operations is the same as linear search in an array, the average case significantly improves this. In practice, this makes hash tables invaluable, with few other data structures being able to perform these functions as efficiently.