Learn to implement your own hash map in Python!

Hash Maps: Python

The necessary ingredient in the hash map recipe is the hashing function. A hashing function takes a key and returns an index into the underlying array. 

Hash functions need to be fast to compute so that access and retrieval can be done fast.

Creating the Hashing Function

Now lets use our open addressing scheme in the setter for our `HashMap`.

Open Addressing in the Setter

A data structure that is unable to contain data is a sad sight indeed. We need to put together all the other steps we’ve taken: plug the key into the hash function, plug the hash code into the compression function, use the array index to find the place in the array, and finally set the value of the array to the value we want.

Defining the Setter

Now we’re going to implement an open addressing system so our hash map can resolve collisions. In open addressing systems, we check the array at the address given by our hashing function. One of three things can happen:
 - The address points to an empty cell.
 - The cell holds a value for the key we are getting/setting 
 - The cell holds a value for a different key.

In the first case, this means that the hash map does not have a value for the key and no collision resolution needs to happen. Notice that this does not work if we want to be able to delete keys in our hash map. There are strategies for deleting pairs from a hash map (see <a href="https://en.wikipedia.org/wiki/Lazy_deletion">Lazy Deletion</a>) but we will not be investigating these.

In the second case, we've found the value for our key-value pair!

In the third case, we need to use our collision addressing strategy to find if our key is somewhere else (it may or may not be) so we should recalculate the index of our array.

Open Addressing

Hashing functions return a wide range of integers. In order to transform these values into useful indices for our array we need a compression function. A compression function uses modular arithmetic to calculate an array index for a hash map when given a hash code.

Creating the Compression Function

There is a natural expectation after placing an item into a bag that we will later be able to remove the item from that bag. Otherwise we have created a hole. Let’s implement retrieval for our hash map.

Defining the Getter

Now that we have all of the functionality of a Hash Map, it's time to review what we've learned!

Review

Hash maps are efficient key-value stores. They are capable of assigning and retrieving data in the fastest way possible for a data structure. This is because the underlying data structure that they use is an array. A value is stored at an array index determined by plugging the key into a hash function.

In Python we don’t have an array data structure that uses a contiguous block of memory. We are going to simulate an array by creating a list and keeping track of the size of the list with an additional integer variable. This will allow us to design something that resembles a hash map. This is somewhat elaborate for the actual storage of a key-value pair, but it helps to remember that the purpose of this lesson is to gain a deeper understanding of the structure as it is constructed. For real-world use cases in which a key-value store is needed, Python offers a built-in hash table implementation with dictionaries.

Creating the Hash Map Class

Our hash and compression functions together can result in collisions. This is when two different keys resolve to the same array index. In our current implementation, all keys that resolve to the same index are treated as if they are the same key.

Our first step in implementing a collision strategy is updating our `.assign()` and `.retrieve()` methods to set the value with the key and check the key before retrieving a value.

Handling Collisions in the Setter

Since we have the basic functionality of a hash map, let’s create a test instance of one for us to make sure everything works as expected.

Creating an Instance

When we retrieve hash map values, we also need to be aware of the fact that two keys could point to the same array index.

Handling Collisions in the Getter

With everything in our setter taken care of, we want to make sure that when we retrieve our value we're retrieving the correct value.