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!