The Self-Taught Computer Scientist

0
1
2
3
4
5
86
6
90
86
% 7
=
2
Figure 13.3: To store 90 in the hash table, you perform modulo by 
the number of slots and get 6.
0
1
2
3
4
5
6
86
21
29
38
39
40
90
86
% 7
=
2
Figure 13.4: Your hash table after adding all the numbers

---

Data Structures
140
table, your goal is to use the correct number of slots and a hash function that produces the fewest 
collisions. However, when you are programming in Python, you don’t have to worry about collisions 
because dictionaries handle them for you.
As I mentioned earlier, in the previous example you are not storing key- value pairs. You can modify 
this example to store key- value pairs using two arrays: one to store keys and one for values. So, for 
example, if you were mapping 
self
to 
taught
, your hash function would turn 
self
into an index in 
an array. You would then store 
self
at that index in the array for keys and 
taught
at that index in 
the array for values.
When to Use Hash Tables
Unlike the other data structures you’ve learned about so far (and the ones you will learn about later), 
on average, searching for data in a hash table is O(1). Inserting and deleting data in a hash table is 
O(1) on average as well. Collisions can erode the efficiency of hash tables, making searching, insertion, 
and deletion O(
n) in the worst- case scenario. Still, hash tables are one of the most efficient structures 
for storing large data sets. The reason hash tables are so efficient is that to determine whether a piece 
of data is in a hash table, all you have to do is run your data through your hash function and check 
an array at that index, which is only one step. Figure 13.5 shows the run time for a hash table’s oper-
ations. It does not include a run time for the Access column for hash tables because hash tables do 
not allow you to access the 
nth item in it like an array or linked list.
Earlier, you learned about search algorithms and how if you sort your data, you can perform a 
binary search, which is significantly faster than a linear search. You also learned that there was another 
way to search for data that is even more efficient than the binary search you will learn about later. 
That method is searching for data in a hash table, which is O(1), meaning that searching for data in 
a hash table is the fastest possible way to search for data. The ability to look up data in constant time 
instead of having to do a linear or binary search makes an enormous difference when working with 
large data sets.
Data 
Structure
Time Complexity
Average
Worst
Access
Search
Insertion Deletion
Access
Search
Insertion Deletion
Array
O(1)
O(n)
O(n)
O(n)
O(1)
O(n)
O(n)
O(n)
Stack
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Queue
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Linked 
List
O(n)
O(n)
O(1)
O(1)
O(n)
O(n)
O(1)
O(1)
Hash 
Table
N/A
O(1)
O(1)
O(1)
N/A
O(n)
O(n)
O(n)
Binary 
Search 
Tree
O(log n)
O(log n)
O(log n)
O(log n)
O(n)
O(n)
O(n)
O(n)