Dictionary Performance

x in some_list starts at index 0 and compares x with each item using == until 1 matches or the list runs out. A dict hashes x, jumps to the slot the hash points at, and compares only there. With the __eq__ method from the previous section, a class can count its own comparisons, which makes the difference visible:

calls = 0

class Tracked:
    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        global calls
        calls += 1
        return self.n == other.n

    def __hash__(self):
        return hash(self.n)

as_list = [Tracked(n) for n in range(10000)]
as_dict = {Tracked(n): n for n in range(10000)}

for probe in [9999, 5000, -5]:
    calls = 0
    in_list = Tracked(probe) in as_list
    list_calls = calls
    calls = 0
    in_dict = Tracked(probe) in as_dict
    print(probe, in_list, list_calls, in_dict, calls)

Output:

9999 True 10000 True 1
5000 True 5001 True 1
-5 False 10000 False 0

The list pays for every item before the match, and a miss pays for all of them. The dict pays 1 == call for a hit and none for a miss, because no stored hash matched -5. Grow both to 1,000,000 items and the list counts grow with them while the dict counts stay put.

Build the lookup dict once, then reuse it

The cost multiplies when a lookup sits inside a loop. Matching each of 50,000 orders to its customer by scanning a list of 20,000 customers repeats the scan for every order. Building a dict keyed by customer ID takes 1 pass over the customers, and after that each order costs 1 lookup.

customers = [
    {"id": 7, "name": "Ana"},
    {"id": 3, "name": "Bo"},
    {"id": 9, "name": "Cy"},
]
orders = [
    {"order": "A1", "customer": 9},
    {"order": "A2", "customer": 3},
    {"order": "A3", "customer": 9},
]

by_id = {c["id"]: c for c in customers}
for o in orders:
    print(o["order"], by_id[o["customer"]]["name"])

Output:

A1 Cy
A2 Bo
A3 Cy

Membership checks speed up the same way. A list named seen that grows inside a loop turns every in into a longer scan, while a dict whose values you ignore keeps each check at 1 hash. dict.fromkeys(items) builds that dict in 1 call with None as every value, and since dicts keep insertion order, it also drops repeats while keeping first appearances in place:

events = ["u3", "u1", "u3", "u2", "u1", "u3"]

seen = {}
first_visits = []
for user in events:
    if user not in seen:
        seen[user] = True
        first_visits.append(user)
print(first_visits)

print(list(dict.fromkeys(events)))

Output:

['u3', 'u1', 'u2']
['u3', 'u1', 'u2']

What a dict does not speed up

Only lookups by key are fast. "Bo" in by_id.values() walks every value one by one, the same as a list. If you search by name often, build a second dict keyed by name.

Reach for a dict
  • You look items up by an ID or name many times.
  • You check membership inside a loop.
  • You need the latest value per key, with repeats overwriting.
Keep a list
  • You read items by position or slice them.
  • Duplicates and their order are the data.
  • You visit every item anyway, as in a sum or a filter.
  • You check a few items once: building a dict costs a full pass first.

A dict uses more memory than a list of the same items: each entry stores the key and its value alongside the key's hash, and the table keeps spare empty slots so new keys find room.

flagged_ids is a list of 200,000 card IDs and payments holds 1,000,000 rows. Which change cuts the most work from this function?

def find_flagged(payments, flagged_ids):
    hits = []
    for p in payments:
        if p["card_id"] in flagged_ids:
            hits.append(p)
    return hits

About this lesson

This section is part of the Dictionaries: Advanced lesson on DataDriven, the home of data engineering. Lessons cover SQL, Python, Spark, data modeling and pipeline architecture, and each section pairs its explanation with worked examples and practice you run as you go.