Hash Table Basics
Hash Tables: lesson 1 of 8
Turn a key into an address and skip the search.
Lesson 1 of 8 · 4 min
Hash Table Basics
Step 1 of 6
hash—resultempty table
keys
SKU-118
SKU-903
get 118
get 000
table — bucket = last two digits % 6
0
1
2
3
4
5
118·42
903·7
A hash table is numbered bins. The key itself decides which bin — no shelf-walking, no sorting.
The Idea
A hash table runs each key through a hash function that returns a bucket number. Storing and looking up both jump straight to that bucket, so the average cost stays O(1) however many keys are inside. The price: keys must be hashable, and order is never promised.
Real-World Example
A pharmacy files finished prescriptions into numbered bins using the last two digits of the order number. Nobody walks the shelves reading labels — the number on your slip is the bin. Two hundred waiting bags cost the same lookup as five.
The Code
stock = {} # an empty hash table
stock["SKU-118"] = 42 # hash the key -> bucket -> store
stock["SKU-903"] = 7
print(stock["SKU-118"]) # 42 -> average O(1)
print("SKU-903" in stock) # True -> also O(1)
stock["SKU-118"] += 1 # read and write, still O(1)
print(stock.get("SKU-000", 0)) # 0 -> safe default, no crash
print(len(stock)) # 2 -> count is storedYour turn
What does this print?
shelf = {"a": 1, "b": 2}
shelf["c"] = 3
shelf["a"] = 9
print(len(shelf), shelf["a"])Mini quiz
1 / 3