The Self-Taught Computer Scientist

Data Structures
138
a_dict = {}
a_dict[1776] = 'Independence Year' 
You can now use the key 1776 to look up the value 
'Independence Year'
like this:
print(a_dict[1776])
>> 'Independence Year' 
Now let’s take a look at how an example hash function works by determining the location of several 
keys, which, in this example, will be integers. Your computer does everything you are about to see 
for you behind the scenes when you use a dictionary in Python. Suppose you have a hash table with 
seven slots, and you want to store several integers in them (Figure 13.1). (In this case, for illustrative 
purposes, we are dealing only with keys and not keys and their values.)
The first number you need to store is 86. To store 86 in your hash table, you need a hash function. 
One simple hash function is to take each number and perform modulo by the number of slots avail-
able (Figure 13.2). For example, to get a hash value for 86, you evaluate 86 % 7. The result of 86 % 7 
is 2, which means you put 86 at index two in the array you are using to store your hash table’s data.
The next number you need to put into your hash table is 90, so you evaluate 90 % 7, which is 6. 
So, you put 90 at index six in your array (Figure 13.3).
0
1
2
3
Hash Table
4
5
6
Figure 13.1: A hash table stores key- value pairs in an array.
0
1
2
3
4
5
6
86
86
% 7
=
2
Figure 13.2: To store 86 in the hash table, you perform modulo 
by the number of slots and get 2.

---

Chapter 13 Hash Tables
139
Finally, you need to add the numbers 21, 29, 38, 39, and 40 to your hash table. Here is what hap-
pens when you use modulo 7 on these numbers:
21 % 7 = 0
29 % 7 = 1
38 % 7 = 3
39 % 7 = 4
40 % 7 = 5
When you add these numbers to your hash table, it looks like Figure 13.4.
So far, adding data to your hash table has gone as planned. Suppose you want to add 30 to your 
hash table. Since 30 % 7 is 2, you should put 30 in slot 2. There is a problem, however, because 86 
is already in that slot. Two numbers hashing to the same slot is a collision. To resolve this collision, 
you can place 30 in the next empty slot. That resolution works, but then when you have to find 30, 
you have to use a hash function to find its location in the array, look in slot 3, realize that it is not 
30, and then look in subsequent slots until you find it, which adds time complexity. There are other 
ways of handling collisions, such as keeping lists (usually linked lists) at each location and putting 
each colliding pair into the list that goes with the original colliding location. When you create a hash