Welcome to Programming and Data Structures

Now that we have explored hashing, we can focus on using it to build a hash table.

A hash table is a data structure built on top of an array. Given a key, we will compute the hash value of the key and then modulo that hash value by the size of the array to determine where the item belongs. If we are inserting the value, we will store it in that cell. If we are looking for a value, we will look in that cell to see if the value is there.

Our table only has 8 cells. If you try inserting other values, it will not take long to find a collision, which is when two different keys hash to the same location. For example, if you insert 12, it will hash to the same location as 20 because 12 % 8 == 4 and 20 % 8 == 4. We need a way to store both of these values even though they want to be in the same cell.

There are two main strategies for handling collisions—closed and open hashing. The first general strategy we will examine is closed hashing (also confusingly known as open addressing). In closed hashing, if we are inserting a value and there is a collision, we move to a different cell in the array to store the value. If that next location is also occupied, we will continue visiting different cells until we find an open cell.

The most straightforward way to implement this is to use linear probing. In linear probing, we simply add 1 to the index each time we need to move to another cell because the current one is full. If we reach the end of the array, we will wrap around to the beginning and continue looking for an open cell. (We are moving in a straight line through the array, probing for an opening.)

For example, imagine we are inserting the value "Jessica Ng" into a hash table of size 7. The hash function and mapping tell us that the record should go in cell 4. If we see that cell is already occupied, we will move to cell 5 and check if it is available. If not, we would move to cell 6, and so on.

This also means that when we go to check if we have a value in the table, and find a different value in the location the hash function produced, we need to probe to see if the value was inserted in an alternate location. A value that was supposed to be placed at index 6 may have had to probe through several cells before finding an open location. Thus, to find a value, we need to continue probing until we either find it, or we reach an open location before deciding that the key is not present.

Try using Find to search for 16 in the animation above (after the insertion is done). The value is not present, but we can’t be sure until we have probed through a few cells to reach an empty cell.

You may also have noted that our hash table has built up a contiguous group of occupied cells. This is known as a cluster. Clusters are problematic because they can lead to long probe sequences. Even worse, any value that hashes to a cell in the cluster will end up being added to the end of the cluster, which makes that cluster even bigger.

To avoid clustering, we can modify the probing sequence or use other collision resolution techniques. Instead of linear probing where our distance from the original location increases like 1, 2, 3, 4, 5, ..., we can do quadratic probing, where we square the probe number to get the distance: 1, 4, 9, 16, 25, .... Alternatively, we can use double hashing, where we use a second hash function to determine the step size for probing. This way different items that hash to the same original location will have different probe sequences, reducing clustering.

The animation below demonstrates quadratic probing in action.

Notice that even when we have a sequence of collisions, quadratic probing helps to reduce clustering by spreading out the probe sequence. If you like, you can also experiment with double hashing.

int hashValue = hash(key)
---
int index = hashValue % tableSize
---
while (table[index] is filled) {
---
while (table[index] is empty) { #distractor
---
    index = (index + 1) % tableSize
---
    index = (index + 1) #distractor
---
}
---
table[index] = value