Get startedGet started for free

Hash tables

1. Hash tables

In this video, we will learn about hash tables.

2. Definition

A hash table is a data structure that stores a collection of items in key-value pairs. In this example, lasagna would be the key, and the price would be the value. Almost every programming language has a built-in hash table known as hashes, hash maps, dictionaries, or associative arrays. In Python, hash tables are implemented with dictionaries.

3. Structure

Let's study hash tables behind the scenes. In a hash table, each position is called a slot or bucket. When we create a new hash table, every slot will be empty.

4. Hash functions

When we add a new element to a hash table, there will be a mapping between the key and the slot where the value will be stored. In this example, the lasagna key will be mapped to number five. This mapping will be performed

5. Hash functions

thanks to a hash function. We are not going to go deeper into hash functions because they are out of the scope of this course, but the most important thing we have to know about them is that every time a hash function is applied, it needs to return the same value for the same input.

6. Lookups

When we want to find a value associated with a key, we need to hash the key

7. Lookups

and then look inside the corresponding slot to return the stored value. As we can see, this operation is really fast, and it takes O of one.

8. Collisions

Sometimes, hash functions can return the same output for different inputs. Suppose that our hash function returns one for the moussaka key. Slot number one is already filled, so if we try to insert the value for moussaka, we will find a collision. Collisions must be resolved, and several techniques exist, but we won't study them in this course. Luckily for us, Python, like most programming languages, implements hash tables and handles these problems for us.

9. Python dictionary

Python hash tables are called dictionaries. An empty dictionary will be defined as shown. We can define a dictionary with some elements. In this example, the names of the dishes are the keys, and the prices are the values.

10. Python dictionary - get

By using the name of a key inside square brackets, we can get its value. If the key doesn't exist, we will get an error. To solve this problem, we can also use the get method, which returns None if the key doesn't exist.

11. Python dictionary - items, keys & values

We can get all the items of a dictionary using the items method. The keys method helps us to get all the keys of the dictionary, and the values method, all the values.

12. Python dictionary - insert

To add a new key-value pair, we need to specify the new key with its value, and it will be inserted.

13. Python dictionary - modify

To modify the value of a particular key, we need to specify it and assign the new desired value. As we can see, the value has changed.

14. Python dictionary - remove

With the del keyword, we can delete a dictionary completely, and remove a key-value pair by specifying the desired key. Finally, a dictionary can be emptied by using the clear method.

15. Python dictionary - iterate

We can iterate over a dictionary using a for loop over its items. We can access the key and the value of each element.

16. Python dictionary - iterate

We can also iterate over the keys or the values.

17. Python dictionary - nested dictionaries

A dictionary can be nested within another dictionary. In this example, every dish has a price and a best served preference.

18. Let's practice!

Let's practice these concepts with some exercises!