Guide to Hash Tables in Python

While Python doesn't have a built-in data structure explicitly called a "hash table", it provides the dictionary, which is a form of a hash table. Python dictionaries are unordered collections of key-value pairs, where the key is unique and holds a corresponding value. Thanks to a process known as "hashing"

Guide to Hash Tables in Python

Dimitrije Stamenic

While Python doesn't have a built-in data structure explicitly called a "hash table", it provides the dictionary, which is a form of a hash table. Python dictionaries are unordered collections of key-value pairs, where the key is unique and holds a corresponding value. Thanks to a process known as "hashing", dictionaries enable efficient retrieval, addition, and removal of entries.

Note: If you're a Python programmer and have ever used a dictionary to store data as key-value pairs, you've already benefited from hash table technology without necessarily knowing it! Python dictionaries are implemented using hash tables!

Link: You can read more about dictionaries in Python in our "Guide to Dictionaries in Python".

In this guide, we'll delve into the world of hash tables. We'll start with the basics, explaining what hash tables are and how they work. We'll also explore Python's implementation of hash tables via dictionaries, provide a step-by-step guide to creating a hash table in Python, and even touch on how to handle hash collisions. Along the way, we'll demonstrate the utility and efficiency of hash tables with real-world examples and handy Python snippets.

Defining Hash Tables: Key-Value Pair Data Structure

Since dictionaries in Python are essentially an implementation of hash tables, let's first focus on what hash tables actually are, and dive into Python implementation afterward.

Hash tables are a type of data structure that provides a mechanism to store data in an associative manner. In a hash table, data is stored in an array format, but each data value has its own unique key, which is used to identify the data. This mechanism is based on key-value pairs, making the retrieval of data a swift process.

The analogy often used to explain this concept is a real-world dictionary. In a dictionary, you use a known word (the "key") to find its meaning (the "value"). If you know the word, you can quickly find its definition. Similarly, in a hash table, if you know the key, you can quickly retrieve its value.

Essentially, we are trying to store key-value pairs in the most efficient way possible.

For example, say we want to create a hash table that stores the birth month of various people. The people's names are our keys and their birth months are the values:

+-----------------------+
|   Key   |   Value     |
+-----------------------+
| Alice   | January     |
| Bob     | May         |
| Charlie | January     |
| David   | August      |
| Eve     | December    |
| Brian   | May         |
+-----------------------+

To store these key-value pairs in a hash table, we'll first need a way to convert the value of keys to the appropriate indexes of the array that represents a hash table. That's where a hash function comes into play! Being the backbone of a hash table implementation, this function processes the key and returns the corresponding index in the data storage array - just as we need.

The goal of a good hash function is to distribute the keys evenly across the array, minimizing the chance of collisions (where two keys produce the same index).

In reality, hash functions are much more complex, but for simplicity, let's use a hash function that maps each name to an index by taking the ASCII value of the first letter of the name modulo the size of the table:

def simple_hash(key, array_size):
return ord(key[0]) % array_size

This hash function is simple, but it could lead to collisions because different keys might start with the same letter and hence the resulting indices will be the same. For example, say our array has the size of 10, running the simple_hash(key, 10) for each of our keys will give us:

Alternatively, we can reshape this data in a more concise way:

+---------------------+
|   Key   |   Index   |
+---------------------+
| Alice   |     5     |
| Bob     |     6     |
| Charlie |     7     |
| David   |     8     |
| Eve     |     9     |
| Brian   |     6     |
+---------------------+

Here, Bob and Brian have the same index in the resulting array, which results in a collision. We'll talk more about collisions in the latter sections - both in terms of creating hash functions that minimize the chance of collisions and resolving collisions when they occur.

Designing robust hash functions is one of the most important aspects of hash table efficiency!

Note: In Python, dictionaries are an implementation of a hash table, where the keys are hashed, and the resulting hash value determines where in the dictionary's underlying data storage the corresponding value is placed.

In the following sections, we'll dive deeper into the inner workings of hash tables, discussing their operations, potential issues (like collisions), and solutions to these problems.

Demystifying the Role of Hash Functions in Hash Tables

Hash functions are the heart and soul of hash tables. They serve as a bridge between the keys and their associated values, providing a means of efficiently storing and retrieving data. Understanding the role of hash functions in hash tables is crucial to grasp how this powerful data structure operates.

What is a Hash Function?

In the context of hash tables, a hash function is a special function that takes a key as input and returns an index which the corresponding value should be stored or retrieved from. It transforms the key into a hash - a number that corresponds to an index in the array that forms the underlying structure of the hash table.

The hash function needs to be deterministic, meaning that it should always produce the same hash for the same key. This way, whenever you want to retrieve a value, you can use the hash function on the key to find out where the value is stored.

The Role of Hash Functions in Hash Tables

The main objective of a hash function in a hash table is to distribute the keys as uniformly as possible across the array. This is important because the uniform distribution of keys allows for a constant time complexity of O(1) for data operations such as insertions, deletions, and retrievals on average.

Link: You can read more about the Big-O notation in our article "Big O Notation and Algorithm Analysis with Python Examples".

To illustrate how a hash function works in a hash table, let's again take a look at the example from the previous section:

+-----------------------+
|   Key   |   Value     |
+-----------------------+
| Alice   | January     |
| Bob     | May         |
| Charlie | January     |
| David   | August      |
| Eve     | December    |
| Brian   | May         |
+-----------------------+

As before, assume we have a hash function, simple_hash(key), and a hash table of size 10.

As we've seen before, running, say, "Alice" through the simple_hash() function returns the index 5. That means we can find the element with the key "Alice" and the value "January" in the array representing the hash table, on the index 5 (6th element of that array):

And that applies to each key of our original data. Running each key through the hash function will give us the integer value - an index in the hash table array where that element is stored:

+---------------------+
|   Key   |   Index   |
+---------------------+
| Alice   |     5     |
| Bob     |     6     |
| Charlie |     7     |
| David   |     8     |
| Eve     |     9     |
| Brian   |     6     |
+---------------------+

This can easily translate to the array representing a hash table - an element with the key "Alice" will be stored under index 5, "Bob" under index 6, and so on:

[...]

Original source