Grokking Algorithms

1 
String
 here means any kind of data—a sequence of bytes.

---

77
Hash functions
The hash function outputs “3”. So let’s store the price of an apple at 
index 3 in the array.
Let’s add milk. Feed “milk” 
into the hash function.
The hash function says “0”. Let’s store the price of milk at index 0.
Keep going, and eventually the whole array will be full of prices.
Now you ask, “Hey, what’s the price of an avocado?” You don’t need to 
search for it in the array. Just feed “avocado” into the hash function.
It tells you that the price is stored at index 4. And sure enough,
there it is.

---

78
Chapter 5
 
 
I
 
 
Hash tables
The hash function tells you exactly where the price is stored, so you 
don’t have to search at all! This works because
• The hash function consistently maps a name to the same index. Every 
time you put in “avocado”, you’ll get the same number back. So you 
can use it the first time to find where to store the price of an avocado, 
and then you can use it to find where you stored that price.
• The hash function maps different strings to different indexes. 
“Avocado” maps to index 4. “Milk” maps to index 0. Everything maps 
to a different slot in the array where you can store its price.
• The hash function knows how big your array is and only returns valid 
indexes. So if your array is 5 items, the hash function doesn’t return 
100 … that wouldn’t be a valid index in the array.
You just built a “Maggie”! Put a hash function and an array together, 
and you get a data structure called a 
hash table
. A hash table is the first 
data structure you’ll learn that has some extra logic behind it. Arrays 
and lists map straight to memory, but hash tables are smarter. They use 
a hash function to intelligently figure out where to store elements.
Hash tables are probably the most useful complex data structure 
you’ll learn. They’re also known as hash maps, maps, dictionaries, and 
associative arrays. And hash tables are fast! Remember our discussion 
of arrays and linked lists back in chapter 2? You can get an item from an 
array instantly. And hash tables use an array to store the data, so they’re 
equally fast.
You’ll probably never have to implement hash tables yourself. Any good 
language will have an implementation for hash tables. Python has hash 
tables; they’re called 
dictionaries
. You can make a new hash table using 
the
dict
function:
>>> book = dict()
book
is a new hash table. Let’s add some prices to 
book
:
>>> book[“apple”] = 0.67