PYTHON / DICTIONARIES AND SETS
Choosing the right built-in container
Pick between list, tuple, set, and dict by matching the container's shape and lookup cost to the question your code actually asks of the data.
What you will learn
- Choose a container from its dominant operation, not from what you typed first
- Replace repeated `x in big_list` scans with a set or dict built once
- Use dict.fromkeys when you need deduplication that keeps first-seen order
- Check hashability and mutability before choosing a set or a dict key
Understanding Choosing the right built-in container
Every built-in container stores the same objects; they differ in what one step of work can answer. A list is a numbered sequence, so it answers "what is at position 3" and "what came next" immediately, but answering "is carol here" means walking elements until a match, which costs time proportional to length. A set and a dict hash the element or key and jump straight to a bucket, so membership and key lookup stay roughly constant no matter how many entries exist. A tuple is a list that refuses to change, and that refusal is what makes it hashable and therefore usable as a dict key or set element.
The practical decision comes from three questions. First, what do you ask most often: a position, a membership test, or a value looked up by some identifier? Second, do duplicates carry information, as in a log of events, or are they noise, as in a list of visited URLs? Third, does insertion order matter to the output? Answering those three usually leaves exactly one container standing: order plus duplicates gives a list, membership only gives a set, identifier to value gives a dict, and a fixed record that must itself be a key gives a tuple.
The cost that surprises people is a scan hidden inside a loop. Checking `if item in seen_list` for each of n items does about n*n comparisons, so ten thousand items becomes roughly a hundred million comparisons while the set version stays near ten thousand hash lookups. Building the set is not free, but it is a single pass, so the rule is to build the fast structure once outside the loop rather than rescanning inside it. For a handful of elements none of this matters, and a list is often the clearer choice.
log = ["alice", "bob", "alice", "carol", "bob", "alice"]
# Order and duplicates matter -> list
print(f"list: first={log[0]} total={len(log)}")
# Only membership matters -> set
seen = set(log)
print(f"set: unique={sorted(seen)} 'dave' in seen -> {'dave' in seen}")
# Key to value -> dict
counts = {}
for name in log:
counts[name] = counts.get(name, 0) + 1
print(f"dict: {counts}")
# A fixed compound key -> tuple
edges = {("alice", "bob"): 3, ("bob", "carol"): 1}
print(f"tuple key: {edges[('alice', 'bob')]}")The right container is the one whose internal structure answers your most frequent question in one step instead of forcing a scan.
Worked examples
Deduplication that keeps order
Shows why a set is the wrong tool when the original order is part of the answer.
raw = ["b", "a", "b", "c", "a"]
unique_ordered = list(dict.fromkeys(raw))
print(unique_ordered)
unique_unordered = set(raw)
print(len(unique_unordered), sorted(unique_unordered))Example explained
Line 1dict.fromkeys builds a dict whose keys are the values of raw, and duplicate keys collapse into the first occurrence.
Line 2Because dicts keep insertion order, list() over those keys returns b, a, c in the order they first appeared.
Line 3set(raw) also gives three elements, but a set has no defined iteration order, so sorted() is needed to print it predictably.
Line 4If your output must match input order, reach for dict.fromkeys, not set.
Only hashable things can be keys
Demonstrates that the mutability of a container decides whether it can index a dict.
seats = {}
seats[("row1", 4)] = "taken"
print(seats[("row1", 4)])
try:
seats[["row1", 5]] = "taken"
except TypeError as e:
print("TypeError:", e)Example explained
Line 1A tuple of two strings works as a key because its contents cannot change, so its hash stays valid for the dict's lifetime.
Line 2The same two values in a list raise TypeError, since a mutable object's hash could drift and strand the entry in the wrong bucket.
Line 3This is why compound keys, such as (row, seat) or (x, y), are written as tuples.
Line 4The fix is never to hash a list, but to convert it: tuple(["row1", 5]).
Index a list of records by key
Shows converting a repeated linear search over dicts into a single dict lookup.
people = [{"id": 3, "name": "carol"}, {"id": 1, "name": "alice"}]
def find(pid):
for p in people:
if p["id"] == pid:
return p["name"]
return None
index = {p["id"]: p["name"] for p in people}
print(find(1), index[1])
print(find(9), index.get(9))Example explained
Line 1find() touches every record until it matches, so its cost grows with len(people) on every call.
Line 2The comprehension does that walk exactly once and stores id -> name, so later lookups are single hash operations.
Line 3index[1] and find(1) agree, which is the point: the dict is a faster route to the same answer.
Line 4index.get(9) mirrors find()'s missing-value behaviour by returning None instead of raising KeyError.
Two containers for one dataset
Shows keeping a list for order and a set for fast membership over the same items.
queue = []
queued = set()
for task in ["build", "test", "build", "deploy", "test"]:
if task in queued:
print("skip", task)
continue
queue.append(task)
queued.add(task)
print(queue)
print(len(queued))Example explained
Line 1queue holds the order the tasks must run in, which a set could not express.
Line 2queued exists only to answer 'have I seen this', and that test stays constant-time as the queue grows.
Line 3Both are updated together, so they never disagree about which tasks are present.
Line 4Without the set, `task in queue` would rescan the list on every iteration.
Important notes
Sets and dicts trade memory for speed: they keep sparse hash tables, so a set of a few million integers uses noticeably more memory than a list of the same values.
For fewer than roughly a dozen elements, a list scan is typically as fast as hashing and easier to read; switch containers because of measured size, not habit.
Common mistakes
Testing `if x in results` where results is a list inside a loop; the code works on ten items and becomes unusably slow at ten thousand because the work grows quadratically.
Calling set(big_list) inside the loop instead of before it, which rebuilds the whole set on every iteration and is slower than the plain list scan it replaced.
Using a set to deduplicate data that is later printed or written to a file, then filing a bug when the order changes between runs of different inputs; the ordered fix is dict.fromkeys.
Trying to store a list as a dict key or set element and reading 'unhashable type' as a Python defect rather than as a signal to use a tuple.
Try it yourself
Change, predict, then run
Given words = ["to", "be", "or", "not", "to", "be"], produce three results with the right container for each: the unique words in first-seen order, the count of each word, and a True/False test for whether "not" appears.
Open the Python workspaceCheck your understanding
You process 200,000 incoming user IDs, must skip any ID already seen, and must finally report the accepted IDs in the order they arrived. Which container choice fits best?
- A list of accepted IDs plus a set of seen IDs, updated together
- A single list, using `id in accepted` to skip duplicates
- A single set, since sets automatically reject duplicates
- A sorted list, checking the end of the list for duplicates
Show answer
The task has two separate demands: constant-time membership and preserved arrival order. A set answers the first, a list the second, so keeping both costs one extra add per item. A single set is tempting because deduplication is free, but sets have no defined order, so the final report would be unreliable; the single-list option preserves order yet turns each check into a scan, making the run quadratic.