Hash Table Basics

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 stored

shelf = {"a": 1, "b": 2}
shelf["c"] = 3
shelf["a"] = 9
print(len(shelf), shelf["a"])