Grokking Algorithms

An apple costs 67 cents.
>>> book[“milk”] = 1.49 
Milk costs $1.49.
>>> book[“avocado”] = 1.49
>>> print book
{‘avocado’: 1.49, ‘apple’: 0.67, ‘milk’: 1.49}

---

79
Use cases
Pretty easy! Now let’s ask for the price of an avocado:
>>> print book[“avocado”]
1.49
The price of an avocado
A hash table has keys and values. In the 
book
hash, the names of 
produce are the keys, and their prices are the values. A hash table maps 
keys to values.
In the next section, you’ll see some examples where hash tables are 
really useful.
EXERCISES
It’s important for hash functions to consistently return the same output 
for the same input. If they don’t, you won’t be able to find your item 
after you put it in the hash table!
Which of these hash functions are consistent?
5.1 
f(x) = 1 
Returns “1” for all input
5.2 
f(x) = rand() 
Returns a random number every time
5.3 
f(x) = next_empty_slot() 
5.4 
f(x) = len(x)
Use cases
Hash tables are used everywhere. This section will show you a few
use cases.
Using hash tables for lookups
Your phone has a handy phonebook built in.
Each name has a phone number associated with it.
Returns the index of the next 
empty slot in the hash table
Uses the length of the 
string as the index

---

80
Chapter 5
 
 
I
 
 
Hash tables
Suppose you want to build a phone book like this. You’re mapping 
people’s names to phone numbers. Your phone book needs to have this 
functionality:
• Add a person’s name and the phone number associated
with that person.
• Enter a person’s name, and get the phone number associated
with that name.
This is a perfect use case for hash tables! Hash tables are
great when you want to
• Create a mapping from one thing to another thing
• Look something up
Building a phone book is pretty easy. First, make a new hash table:
>>> phone_book = dict()
By the way, Python has a shortcut for making a new hash table. You can 
use two curly braces:
>>> phone_book = {}