Data Structures - Hash Tables For Beginners

This tutorial will use Python 3.6 to convey the concepts covered.

So, in this tutorial, we are going to be looking at Hash Tables and how they can be used within our applications for fame and fortune. By the end of this tutorial, you should have a solid grasp of these Hash Tables and how they work under the covers.

An Introduction

So, the first place we should start with is, what are hash tables? Hash Tables in Computer Science are a data structure that allow you to store key value pairs in such a way that allows for very quick look-up.

By knowing how hashmaps work fundamentally, we can drastically improve the performance of certain parts of our applications by leveraging this knowledge.

An Example

Let’s take for example a hypothetical example in which we filter a stream of incoming tweets. Every time we receive a tweet, we need to check if we care about the author of that particular tweet.

Now, we could use an array to store a list of authors we care about and then enumerate through this list every time we get a new tweet in.

tweet_author = "realpython"
authors = ["elliot_f", "golangweekly", "realpython"]

for author in authors:
  if author == tweet_author:
    print("We care about this tweet")

This would certainly work. However, what happens when we increase the number of authors we want to keep track of?

For each new author, we’ll essentially be doing 1 more comparison per tweet. If we are tracking 100 authors, and we get a tweet from someone we don’t follow, then we have done 100 unnecessary comparisons. Scale this up for the hundreds of millions of tweets that go out every day and we’ve done a tonne of unnecessary work.

Using Hashmaps

We can improve the performance of our code above through the use of a hashmap.

Every time a new tweet comes in, we can take the tweet_author string and compute a hash. We can then almost instantly check to see if this hash matches something within our hashmap in O(1) time complexity and then decide what to do with that tweet if it is from one of the authors we are following:

tweet_author = "golangweekly"
authors = {"elliot_f":True, "realpython":True, "golangweekly":True}

if authors[tweet_author]:
  print("We care about this tweet")

With this implementation, if we receive a tweet from an author that we don’t follow, we are only performing one simple hashing computation and a lookup to check. This will drastically improve the speed at which our code can execute at scale.

Performance

Good Hash Tables with minimal collisions allow you to perform inserts, finds and deletes in a constant amount of time, this can be expressed as O(1) in big-O notation.

This constant timing makes them incredibly valuable data-structures when compared to the likes of Arrays for instance. If we were tasked with the job of finding an element in array, we would typically have to iterate through all elements of that array before we found what we were looking for. Depending on the size of our array, this could be a fairly time-consuming task.

Fill Factor

When we talk about hash tables and their implementation, we have to consider the Fill Factor of that particular hash table.

Hash tables with a high Fill Factor will tend to have a high number of collisions and as the Fill Factor of your hash table increases, the performance of said hash table starts to degrade.

Hashing Algorithms

When designing a hash table, we need to come up with a good hashing algorithm that meets the following basic requirements:

• It must be efficient.
• It must compute the same hash value for equal objects.
• It should uniformly distribute our Hashes so that we don’t have clusters of hashes.
• It should have a low hash collision factor.

Typically, in languages like Python, these Hashing algorithms are provided for you and differ depending on the type of data you are hashing. However, they tend to give you the ability to come up with your own hashing algorithms should you wish.

A Simple Example in Python

Now that we have covered some of the basic theory underlying Hash Tables, let’s have a look at how we would use Hash Tables within our Python applications.

We’ll be using a Python dict data type in this example as the dict is an implementation of a hash table.

## we can initialize an empty dict using curly braces like so
hash_table = {}
## next, we append an key which will be hashed, and a value
hash_table["random"] = "string"
## we can then retrieve the value of our hashed string like so
## the hashing of "random" takes O(1) time
print(hash_table["random"])

Conclusion

I hope you found this tutorial useful! If you require further assistance then please let me know in the comments section below or by tweeting me @Elliot_F.