What is a hash table?
A hash table stores pairs of a key and a value. It can find a key in about one step, however many pairs it holds. A Python dictionary is a hash table.
A compiler uses one to find a variable's details from its name. Searching a list of 100,000 names one by one would be far too slow.
By the end of this lesson
Note
I can explain how a hash table finds a key quickly.
Key words
| Word | What it means | Example |
|---|---|---|
| Hash table | a store of key and value pairs found by hashing the key | |
| Key | the label you look a value up by | "make" |
| Hash function | a rule that turns a key into a number | |
| Bucket | one numbered slot of the table | |
| Collision | two keys that land in the same bucket | |
| Chaining | keeping a small list in each bucket |
The cells students fill in are left blank in this preview.
A hash function gives a bucket number
A table is an array of buckets. The hash function takes a key and gives a whole number. The remainder after dividing by the number of buckets is the bucket the key belongs to.
A simple rule adds up the codes of the letters. The same key always gives the same bucket, so a lookup goes straight there.
Worked example: three names, 8 buckets
| Key | Letter codes added | Remainder after dividing by 8 | Bucket |
|---|---|---|---|
| make | 109 + 97 + 107 + 101 = 414 | 6 | 6 |
| gcc | 99 + 99 + 99 = 297 | 1 | 1 |
| ld | 108 + 100 = 208 | 0 | 0 |
The cells students fill in are left blank in this preview.
Work out a bucket yourself
# A hash function: add the letter codes, then take the remainder.
SIZE = 8
key = "make"
total = 0
for ch in key:
total = total + ord(ch)
print(total, total % SIZE)
# Change key to "ld" and run again.
The bucket for make in 8 buckets
python3 -c "print(sum(ord(c) for c in 'make') % 8)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Python hashes a whole number to itself
python3 -c "print(hash(7), hash(7.0))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Two keys can land in the same bucket
There are far more possible keys than buckets, so sooner or later two keys share one. That is a collision.
A good table does not stop collisions. It copes with them. A collision is not an error, and the table must still find both keys.
Two tool names, one bucket
python3 -c "print(sum(ord(c) for c in 'cpp') % 8, sum(ord(c) for c in 'ar') % 8)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A common mistake
Warning
Many people think each key gets its own bucket, so a collision means data is lost. It does not. A bucket may hold several pairs. The table keeps the key beside each value, and checks the key before it answers.
Chaining keeps a small list in each bucket
With chaining, every bucket is a list of key and value pairs. To store a pair, hash the key and add the pair to that bucket's list.
To look up a key, hash it, go to the bucket and compare keys one by one. If the buckets stay short, that is a few comparisons, however big the table is.
Worked example: the chained table
| Bucket | Pairs held |
|---|---|
| 0 | ld |
| 1 | gcc |
| 3 | cpp, ar |
| 6 | make |
| Other buckets | Empty |
The cells students fill in are left blank in this preview.
Fill a table with chaining
# A table of 8 buckets. Each bucket is a list of [key, value] pairs.
SIZE = 8
table = []
for i in range(SIZE):
table.append([])
def bucket_of(key):
total = 0
for ch in key:
total = total + ord(ch)
return total % SIZE
for key in ["cpp", "ar", "make"]:
table[bucket_of(key)].append([key, len(key)])
print(table[3])
print(table[6])
# Add "ld" and print table[0].
A dictionary is a hash table
python3 -c "d = {'gcc': 1, 'make': 2}; print(d['make'], 'ld' in d)"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A crowded table slows down, so it grows
If a table has 8 buckets and 800 keys, each bucket holds about 100 pairs and a lookup is slow again.
So real tables count their pairs. When there are too many for the buckets, they make a bigger table. They then move every pair in again, because each bucket number depends on the size.