Grokking Algorithms

5.5
A phonebook where the keys are names and values are phone 
numbers. he names are as follows: Esther, Ben, Bob, and Dan.
5.6
A mapping from battery size to power. he sizes are A, AA, AAA, 
and AAAA.
5.7
A mapping from book titles to authors. he titles are 
Maus
, 
Fun 
Home
, and 
Watchmen
.
Recap
You’ll almost never have to implement a hash table yourself. he 
programming language you use should provide an implementation for 
you. You can use Python’s hash tables and assume that you’ll get the 
average case performance: constant time.
Hash tables are a powerful data structure because they’re so fast and 
they let you model data in a diferent way. You might soon ind that 
you’re using them all the time:

---

94
Chapter 5
 
 
I
 
 
Hash tables
• You can make a hash table by combining a hash function
with an array.
• Collisions are bad. You need a hash function that
minimizes collisions.
• Hash tables have really fast search, insert, and delete.
• Hash tables are good for modeling relationships from one
item to another item.
• Once your load factor is greater than .07, it’s time to resize
your hash table.
• Hash tables are used for caching data (for example, with
a web server).
• Hash tables are great for catching duplicates.

---

95
In this chapter
• 
You learn how to model a network using a new, 
abstract data structure: graphs.
• 
You learn breadth-irst search, an algorithm you 
can run on graphs to answer questions like,
“What’s the shortest path to go to X?”
• 
You learn about directed versus undirected graphs.
• 
You learn topological sort, a diferent kind of
sorting algorithm that exposes dependencies 
between nodes.