lesson 173 Algorithms & Complexity · advanced

Hash-based problems: sets and dictionaries

A set or dictionary turns a value into a number (its hash) and goes straight to the slot where it would be. Checking `in` costs about the same for ten items or ten million.

You'll be able to

Measure that in on a list compares item by item while in on a set does not
Solve repeat and pair problems in one pass with a dictionary of what you have seen
Explain why lists can't be keys or set members, and use tuples instead

The idea

code in codes on a list compares code with one item after another: O(n). A set or dictionary works differently. It calls hash(code), which turns the value into a number, uses that number to pick a slot, and only compares with whatever sits in that slot. Equal values always have equal hashes, so a value that is there is found in that slot, and a value that isn't usually costs no comparison at all. On average that is O(1).

To see it, the example uses a str subclass that counts every == it takes part in.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Counting the comparisons behind `in`

class Sku(str):
    comparisons = 0

    def __eq__(self, other):
        Sku.comparisons += 1
        return str.__eq__(self, other)

    __hash__ = str.__hash__

catalogue = [Sku(f"SKU-{n:05}") for n in range(20000)]
as_list = catalogue
as_set = set(catalogue)

for wanted in ["SKU-00007", "SKU-19999", "SKU-99999"]:
    Sku.comparisons = 0
    in_list = Sku(wanted) in as_list
    list_cost = Sku.comparisons
    Sku.comparisons = 0
    in_set = Sku(wanted) in as_set
    print(wanted, in_list, list_cost, in_set, Sku.comparisons)

Hashing only works if a value's hash never changes, so only hashable values (numbers, strings, tuples of hashable values) can be dictionary keys or set members. A list can change after it is stored, so Python refuses it.

example-2.py · A list as a dictionary key

visits = {}
visits[["C00077", "2024-01-16"]] = 1
print(visits)

example-3.py · Visits per customer and day, keyed by a tuple

def visits_per_day(events):
    visits = {}
    for customer, day in events:
        key = (customer, day)
        if key not in visits:
            visits[key] = 0
        visits[key] += 1
    return visits

events = [
    ("C00077", "2024-01-16"),
    ("C01338", "2024-01-16"),
    ("C00077", "2024-01-16"),
    ("C00077", "2024-01-20"),
]
print(visits_per_day(events))

When to use it: any time a loop asks *have I seen this before?*, *is this in that other collection?* or *what goes with this key?*: duplicates, joins, counts, matching pairs. Build the set or dictionary once, then look up as often as you like. Mistakes to avoid: building the set inside the loop (that rebuilds it every pass and is O(n²) again); searching dictionary.values(), which is a scan; and using a list or dictionary as a key. Sets and dictionaries don't keep values sorted, so if you need order, keep a list beside them or sort at the end.

Review

Sets and dictionaries hash a value to find its slot: in and [key] are O(1) on average.
Build the set or dictionary once, outside the loop; then *seen before?* and *partner exists?* are single lookups.
Keys and set members must be hashable: use tuples, not lists.
Next: two simple structures that decide *which* waiting item comes out next, stacks and queues.

Practise this