A dictionary or set is built on a hash table. To check whether a key is present, Python computes the key's hash, jumps to the matching slot, and compares. That takes about the same time whether the collection has ten items or ten million. A list has no such shortcut: to check x in my_list, Python compares x with items one at a time until it finds a match or reaches the end, so the time grows with the length.
What the difference looks like
ids = list(range(1_000_000)) id_set = set(ids) 999_999 in ids # scans up to a million items (slow) 999_999 in id_set # one hash lookup (fast)
Repeating a membership test thousands of times against a list turns a quick job into a very slow one, a common hidden cost in pipeline scripts. Doing 100,000 lookups against a 1-million-item list means up to 100 billion comparisons.
Practical example: filter new ids
seen = set(existing_ids) # build once new_rows = [r for r in rows if r["id"] not in seen]
This is linear in the data size. The same code with existing_ids as a list becomes quadratic.
The rules of a hash table
- Keys must be hashable, which in practice means immutable: strings, numbers, tuples of hashables. Lists and dictionaries cannot be keys, because their content can change and so their hash would too.
- Collisions happen when two different keys map to the same slot. Python resolves them by probing for another slot, and keeps the table sparse enough (resizing as it grows) that this stays rare, so the average cost stays constant. In the worst case it degrades, but that is unusual with good hashes.
- Dictionaries keep insertion order, guaranteed by the language since Python 3.7. Sets do not guarantee any order.
- Memory: hash tables use more memory than lists, because of the empty slots and stored hashes. That is the price of fast lookup.
Complexity summary
Lookup, insert and delete in a dict or set are O(1) on average. Membership in a list is O(n). Building the set costs O(n) once.
How to answer
Name the hash table, state the average O(1) with the caveat about collisions, mention hashable keys, and give the "dedupe or filter ids with a set" example from real work.