Dictionaries & Sets: Key-Value Storage, Iteration, Membership & Uniqueness

You have met the list: an ordered row of things you reach by position, items[0], items[1]. It is the right tool when order is the point. But most real data is not “the third thing” — it is “the thing called port”, “the user with ID u42”, “how many times the word the appeared”. You want to look things up by name, not by number.

That is a dictionary — Python’s dict — and it is the most important data structure in the language. Python is built out of dicts: every module’s globals, every object’s attributes, every set of keyword arguments is a dict underneath, and JSON from a web API arrives as one. Its close cousin the set is the same machinery with the values thrown away: a bag of unique things, brilliant at exactly two jobs — answering “is this in there?” instantly, and removing duplicates. This lesson covers both, plus the one idea that explains their speed: hashing.

---

Why this matters

Here is the problem a dict solves. Suppose you have a million user IDs in a list and you want to know whether "u999999" is among them. Python must start at the front and compare every element until it finds a match or falls off the end. A million comparisons. Put those IDs in a set and ask again: Python computes one number from the ID, jumps straight to where it would live, and looks. One hop. On my laptop that is ~4,700 microseconds versus a twentieth of one — tens of thousands of times faster, and the gap widens as the data grows. You will measure it yourself later.

That is not a micro-optimisation; it is the difference between a script that finishes and one you kill after twenty minutes. The most common performance bug in beginner Python is a loop containing if x in some_big_list: — an innocent line that quietly makes your program quadratic.

Dicts also fix a correctness problem. Real data is missing things: the config has no port, the API omits address. Reach for config["port"] and your program dies with KeyError. Reach for config.get("port", 8080) and it carries on. Half this lesson is that difference — the crash and the fix.

The mental model: a list is a numbered row of lockers; a dict is a coat check. With lockers you must remember the number, and finding an item without it means opening every locker. With a coat check you hand over a ticket and get your coat back immediately, however many coats are behind the counter. The ticket is the key, the coat is the value, and the “immediately” is what the second half explains.

---

The dict: building one, and what a key is allowed to be

A dict is a collection of key → value pairs written in curly braces with colons. The key is how you find things; the value is what you get back.

# A server config: keys are names (strings), values are anything at all.
server = {"host": "web01", "port": 8080, "tls": True}

print(server)          # => {'host': 'web01', 'port': 8080, 'tls': True}
print(server["host"])  # => web01
print(len(server))     # => 3   (number of pairs, not characters)

Values can be any type — including lists and other dicts. Keys are fussier, and we will get to why. There are several ways to build a dict, and you will meet all of them in real code:

⚠️ dict.fromkeys(keys, []) gives every key the same list object, not a copy. d = dict.fromkeys(["a", "b"], []); d["a"].append(1) leaves you with {'a': [1], 'b': [1]} — appending to one appended to “both”, because there is only one list. Only use fromkeys with an immutable default like 0, None or "". For mutable defaults, use defaultdict(list), which you will meet shortly.

Keys must be hashable

Try to use a list as a key and Python refuses:

seen = {}
seen[["a", "b"]] = 1

Traceback (most recent call last):
  File "/home/you/tb2.py", line 2, in <module>
    seen[["a", "b"]] = 1
    ~~~~^^^^^^^^^^^^
TypeError: unhashable type: 'list'

Hashable means the object can be fed to the built-in hash() function and produces an integer that never changes for its lifetime. Python needs that number to decide where to file the entry. If a key’s hash could change after filing, the value would be stranded at an address nothing points to — so Python forbids mutable types as keys. The rule of thumb: immutable = hashable = usable as a key.

print(hash(42))            # => 42        (small ints hash to themselves)
print(hash(True))          # => 1
print(hash((1, 2)))        # => a big int, built from the items' own hashes
print(hash([1, 2]))        # TypeError: unhashable type: 'list'

That last row catches people: a tuple is usually a safe key, but hash((1, [2])) still raises TypeError: unhashable type: 'list' — hashability is contagious through the contents. The fix is always to convert the inner list to a tuple.

# Want a coordinate as a key? Use a tuple, not a list.
grid = {(0, 0): "origin", (1, 2): "treasure"}
print(grid[(1, 2)])   # => treasure

---

Reading and writing: d[k], .get(), and every method that matters

Writing is simple: assign to a key. If it exists you overwrite it; if it doesn’t, you create it. No “append”, no error either way.

server = {"host": "web01"}
server["port"] = 8080      # key didn't exist -> created
server["host"] = "web02"   # key existed     -> overwritten
print(server)              # => {'host': 'web02', 'port': 8080}

Reading is where beginners get hurt. server["hostname"] (note the typo) does not return None or an empty string — it raises:

Traceback (most recent call last):
  File "/home/you/tb1.py", line 2, in <module>
    print(config["hostname"])
          ~~~~~~^^^^^^^^^^^^
KeyError: 'hostname'

KeyError is Python saying “there is no such key.” The message is the key it couldn’t find — your best debugging clue, because it is usually a typo, a case difference ("Host" vs "host"), or a field the API didn’t send. The cure is .get():

config = {"host": "web01"}

print(config["port"])          # KeyError: 'port'        <- crash
print(config.get("port"))      # => None                 <- no crash
print(config.get("port", 8080))# => 8080                 <- no crash, useful default
print(config)                  # => {'host': 'web01'}    <- .get NEVER inserts

These four reads are the whole vocabulary, and choosing between them is a real decision:

setdefault is the odd one — it reads and writes:

cfg = {"host": "web01"}
print(cfg.setdefault("port", 8080))  # => 8080   (missing, so it inserts)
print(cfg)                           # => {'host': 'web01', 'port': 8080}
print(cfg.setdefault("port", 9999))  # => 8080   (present, so 9999 is IGNORED)

The name reads backwards to most people. Say it as “give me this key, creating it with this default if it’s absent.” It never overwrites an existing value.

One more trap worth flagging early: in checks keys, not values.

cfg = {"host": "web01"}
print("host" in cfg)             # => True    (a key)
print("web01" in cfg)            # => False   (a value! not found)
print("web01" in cfg.values())   # => True    (this is how you search values)

The full method table

Here is every dict method you will actually use, with what it returns and how it fails:

Watch the return values — this is a classic beginner trip-up. update() and clear() return None, because they change the dict in place. d = d.update(other) throws away your dict and leaves you with None. Meanwhile | returns a new dict and leaves both originals alone.

defaults = {"host": "localhost", "port": 8080}
user     = {"port": 9000}

print(defaults | user)     # => {'host': 'localhost', 'port': 9000}   right side wins
print(user | defaults)     # => {'port': 8080, 'host': 'localhost'}   order matters!
print({**defaults, **user})# => {'host': 'localhost', 'port': 9000}   same, works pre-3.9
print(defaults)            # => {'host': 'localhost', 'port': 8080}   untouched

---

Iterating: the trap that catches everyone

Loop over a dict and you get the keys — not the values, and not the pairs. This surprises nearly every beginner:

server = {"host": "web01", "port": 8080, "tls": True}

for x in server:
    print(x)

host
port
tls

If you expected web01, 8080, True, this is the moment to rewire: for x in d means for x in d.keys(). The idiomatic way to get both halves is .items(), and you should reach for it by reflex:

for key, value in server.items():
    print(f"{key:<5} = {value}")

host  = web01
port  = 8080
tls   = True

Those three view objects — keys(), values(), items() — are live windows, not snapshots. Change the dict and the view already knows:

srv = {"host": "web01"}
ks = srv.keys()
srv["port"] = 8080
print(ks)          # => dict_keys(['host', 'port'])   <- the view updated itself

A bonus most people never learn: keys() behaves like a set, so you can do algebra directly on it. (values() cannot — values needn’t be unique or hashable.)

a = {"host": 1, "port": 2, "tls": 3}
b = {"host": 9, "user": 8}
print(a.keys() & b.keys())          # => {'host'}          keys in BOTH
print(sorted(a.keys() - b.keys()))  # => ['port', 'tls']   keys only in a (sorted = stable output)

Insertion order is guaranteed

Since Python 3.7 a dict remembers the order you inserted keys and iteration replays it (an accident of CPython 3.6 that became a language promise in 3.7). It is insertion order — not sorted, not random:

d = {}
d["z"] = 1; d["a"] = 2; d["m"] = 3
print(list(d))          # => ['z', 'a', 'm']    insertion order, not alphabetical
print(sorted(d))        # => ['a', 'm', 'z']    sort explicitly if you want sorted

Two consequences. Any tutorial claiming “dicts are unordered” predates 3.7 and is out of date. And == still ignores order: {"a": 1, "b": 2} == {"b": 2, "a": 1} is True — order is preserved for iteration, but is not part of a dict’s identity.

Never resize a dict you are iterating

This one raises a genuinely confusing error:

counts = {"a": 1, "b": 2, "c": 3}
for key in counts:
    if counts[key] < 2:
        del counts[key]        # deleting DURING iteration

Traceback (most recent call last):
  File "/home/you/tb3.py", line 2, in <module>
    for key in counts:
RuntimeError: dictionary changed size during iteration

Note where the arrow points: at for key in counts, not at the del line. The iterator is walking the internal table; add or remove an entry and Python may need to resize and reshuffle it, at which point the iterator’s position is meaningless. Rather than hand you silently wrong results, Python raises.

The fix is to iterate over a snapshot, which list() gives you:

counts = {"a": 1, "b": 2, "c": 3}
for key in list(counts):      # list() copies the keys FIRST
    if counts[key] < 2:
        del counts[key]
print(counts)                 # => {'b': 2, 'c': 3}

Or build a new dict with a comprehension, which is cleaner still:

counts = {"a": 1, "b": 2, "c": 3}
counts = {k: v for k, v in counts.items() if v >= 2}
print(counts)                 # => {'b': 2, 'c': 3}

Sets do the same thing, with a capital-S message: RuntimeError: Set changed size during iteration. Changing a value in place is fine — only adding or removing keys resizes the table.

Nested dicts: the JSON shape

JSON from any web API arrives as dicts inside dicts inside lists. Reaching deep is easy; reaching deep safely is the skill.

data = {
    "user": {"name": "ada", "roles": ["admin"], "address": {"city": "London"}},
    "active": True,
}
print(data["user"]["address"]["city"])   # => London
print(data["user"]["roles"][0])          # => admin   (list index inside a dict)

Each [...] is an independent lookup, and any one of them can raise KeyError. If the API omits address for some users, data["user"]["address"]["city"] explodes. Chain .get() with {} defaults so every step stays a dict:

print(data.get("user", {}).get("address", {}).get("zip"))        # => None
print(data.get("user", {}).get("address", {}).get("zip", "N/A")) # => N/A
print(data.get("acct", {}).get("id"))                            # => None   (whole branch missing)

The {} default is the load-bearing part. Get it wrong and you get a different error that confuses everyone:

print(data.get("acct").get("id"))
# AttributeError: 'NoneType' object has no attribute 'get'

Because data.get("acct") returned None, and None has no .get. If you see 'NoneType' object has no attribute 'get', you forgot a {} default somewhere up the chain.

---

The collections helpers that earn their keep

The standard library’s collections module ships dict subclasses that delete whole paragraphs of your code. Two are genuinely worth learning now.

defaultdict takes a factory (a function it calls to make a value) and runs it automatically whenever you touch a missing key — so you never write the “is it there yet?” dance:

from collections import defaultdict

# Without: you must create the list before appending to it.
groups = {}
for name, dept in [("ada", "eng"), ("bob", "ops"), ("cy", "eng")]:
    if dept not in groups:
        groups[dept] = []
    groups[dept].append(name)

# With: the empty list appears on demand.
groups = defaultdict(list)
for name, dept in [("ada", "eng"), ("bob", "ops"), ("cy", "eng")]:
    groups[dept].append(name)

print(groups)        # => defaultdict(<class 'list'>, {'eng': ['ada', 'cy'], 'ops': ['bob']})
print(dict(groups))  # => {'eng': ['ada', 'cy'], 'ops': ['bob']}

⚠️ The sting: merely reading a missing key inserts it. d["ghost"] on a defaultdict(int) returns 0 and leaves {'ghost': 0} behind, growing your dict as you inspect it. Use .get() when you only want to look.

Counter is a dict built for tallying. Hand it any iterable and it counts:

from collections import Counter

words = "the quick the lazy the dog dog".split()
c = Counter(words)
print(c)                  # => Counter({'the': 3, 'dog': 2, 'quick': 1, 'lazy': 1})
print(c.most_common(2))   # => [('the', 3), ('dog', 2)]
print(c["missing"])       # => 0      no KeyError, and nothing is inserted
print(c.total())          # => 7      (3.10+)

Counter earns its own table because its extras are what make it worth importing:

What about OrderedDict? It is now mostly historical. Before 3.7 it was the only way to get a dict that remembered insertion order; plain dicts do that natively today. Two real differences survive: its == is order-sensitive, and it has move_to_end().

from collections import OrderedDict
print({"a": 1, "b": 2} == {"b": 2, "a": 1})                              # => True   order ignored
print(OrderedDict([("a",1),("b",2)]) == OrderedDict([("b",2),("a",1)]))  # => False  order matters

Unless you need one of those, use a plain dict.

Dict comprehensions, in passing

You have seen list comprehensions; dicts have the same trick with a key: value body. A full treatment comes later in the course, but you should recognise the shape:

prices = {"apple": 100, "banana": 40, "cherry": 250}

print({k: v * 2 for k, v in prices.items()})            # => {'apple': 200, 'banana': 80, 'cherry': 500}
print({k: v for k, v in prices.items() if v > 50})      # => {'apple': 100, 'cherry': 250}
print({v: k for k, v in prices.items()})                # => {100: 'apple', 40: 'banana', 250: 'cherry'}

That last one — inverting a dict — only works if the values are hashable and unique. Duplicate values silently collapse, keeping the last one.

---

Sets: uniqueness, membership, and set algebra

A set is an unordered collection of unique, hashable items. Same hash table as a dict, minus the values. If a dict is a coat check, a set is the guest list: it answers “are you on it?” instantly and refuses to write your name twice.

ids = {"u1", "u2", "u1", "u3"}
print(ids)          # => {'u3', 'u2', 'u1'}   duplicate dropped; YOUR ORDER WILL DIFFER
print(len(ids))     # => 3
print("u2" in ids)  # => True

Two things to internalise from that snippet. Duplicates are dropped silently — no error, they just never existed. And the printed order is not something you can rely on; run it again and you may get a different arrangement.

Why the order shuffles between runs. Python salts the hashing of strings with a random per-process seed (a defence against denial-of-service attacks that deliberately collide keys), so the slot a string lands in — and therefore the print order of a string set — genuinely differs each time you run the program. This is also why you should never save a hash() value to a file or database and expect it to match later. If you need stable output, call sorted(). Sets of small ints happen to look stable because hash(42) == 42, but do not lean on it.

The {} trap

{} is an empty dict, not an empty set. This is a wart of the syntax, and everyone hits it once:

print(type({}))       # => <class 'dict'>    <- NOT a set!
print(type(set()))    # => <class 'set'>     <- the only way to make an empty set
print(type({1, 2}))   # => <class 'set'>     <- non-empty braces ARE a set

Dicts got the braces first, so the empty set had to make do with set().

Members obey the same hashability rule as keys — {[1, 2]} raises TypeError: unhashable type: 'list'.

Set methods

discard vs remove is the only real decision: discard when you don’t care, remove when absence is a bug you want to hear about.

There is no indexing, ever — a set has no order to index into:

unique = {"u1", "u2", "u3"}
print(unique[0])

Traceback (most recent call last):
  File "/home/you/tb4.py", line 2, in <module>
    print(unique[0])
          ~~~~~~^^^
TypeError: 'set' object is not subscriptable

Need a specific element? You want a list. Need sorted output? sorted(unique) gives you a list back.

Set algebra

This is where sets stop being “lists without duplicates” and start being a superpower. Every operator has a method twin:

The difference between operator and method is not cosmetic: operators demand a set on both sides; methods accept any iterable.

a = {1, 2, 3, 4}
print(a.union([7]))   # => {1, 2, 3, 4, 7}   method takes a list happily
print(a | [7])        # TypeError: unsupported operand type(s) for |: 'set' and 'list'

Which makes the real-world use obvious. Two exports, two lists of IDs, one question — what changed?

old = {"u1", "u2", "u3", "u4"}
new = {"u3", "u4", "u5"}

print("added:  ", sorted(new - old))   # => ['u5']
print("removed:", sorted(old - new))   # => ['u1', 'u2']
print("kept:   ", sorted(old & new))   # => ['u3', 'u4']
print("churned:", sorted(old ^ new))   # => ['u1', 'u2', 'u5']

Four lines, and each would be a nested loop otherwise. This is the single most useful thing sets do.

frozenset

A frozenset is a set you cannot change — which makes it hashable, which means it can be a dict key or live inside another set:

fs = frozenset([1, 2])
print({fs: "pair"})                        # => {frozenset({1, 2}): 'pair'}          a set as a dict KEY
print({frozenset([1, 2]), frozenset([3])}) # => {frozenset({3}), frozenset({1, 2})}  a set OF sets
fs.add(3)                                  # AttributeError: 'frozenset' object has no attribute 'add'

Use it when you need a set of sets, or a set as a dict key — for example keying a cache on the set of permissions a request carries.

---

Why dicts and sets are fast: hashing and Big-O

Now the payoff. When you write d["eth0"], Python does four things: it calls hash("eth0") to get an integer; it masks that integer down to a slot number in the table (roughly hash & (size - 1)); it jumps straight to that slot; and it compares the key there with == to confirm. That is a constant number of steps — the dict could hold ten entries or ten million and it is the same four steps. That is what O(1) means: the cost does not grow with the data.

A list has no such trick. x in my_list starts at index 0 and compares its way along until it finds x or runs out — O(n), cost proportional to size. The diagram below traces both paths side by side; a set is the same machine as the dict with the value column removed, which is why it inherits the O(1).

The badges mark what matters to you as a learner: a key must be hashable (1), hash() turns it into an int (2) — which is exactly why a mutable list cannot be a key (3); the int becomes a slot address, with probing when two keys collide (4); the value comes back in one hop, O(1) average (5); while a list has to look at everything, O(n) (6).

Here is the honest complexity table. “Average” matters — a dict’s O(n) worst case needs a pathological set of keys that all collide into one slot, which you will never see by accident:

That last row is the trade-off: hash tables buy speed with empty space (the table must stay partly empty or collisions pile up). For a thousand items, who cares; for a hundred million, measure.

And the caveat folklore omits: O(n) is the worst case for a list. If the item sits at index 0 the list wins — ~28 ns, no hashing at all. Sets are not magic; they are consistently fast rather than sometimes fast. Below ~10 items the difference is noise, so use whatever reads better. Above a few hundred, in a loop, the set is the only sane answer.

---

Hands-on lab

Everything here is pure standard library — there is nothing to pip install. You need Python 3.10+ (Counter.total() needs 3.10; everything else works on 3.7+). If you like keeping work isolated, a venv costs nothing:

python3 -m venv .venv && source .venv/bin/activate   # Windows: .venv\Scripts\activate
python3 --version                                     # => Python 3.12.3 (yours may differ)
mkdir dictlab && cd dictlab

Step 1 — A word-frequency counter, three ways

Create word_freq.py:

"""Word frequency, three ways — they must all agree."""
from collections import defaultdict, Counter

TEXT = """the quick brown fox jumps over the lazy dog
the dog barks and the fox runs the fox wins"""

words = TEXT.split()
print(f"{len(words)} words, {len(set(words))} unique")

# --- Way 1: plain dict + .get(k, 0) ---------------------------------
counts_get = {}
for w in words:
    counts_get[w] = counts_get.get(w, 0) + 1

# --- Way 2: defaultdict(int) ----------------------------------------
counts_dd = defaultdict(int)
for w in words:
    counts_dd[w] += 1

# --- Way 3: Counter -------------------------------------------------
counts_ctr = Counter(words)

# All three produce the same mapping
print("way1 == way2:", counts_get == counts_dd)
print("way2 == way3:", counts_dd == counts_ctr)
print("way1 == way3:", counts_get == counts_ctr)

print("\ntop 3 (Counter.most_common):")
for word, n in counts_ctr.most_common(3):
    print(f"  {word:<6} {'#' * n} {n}")

# The KeyError a beginner writes first:
try:
    bad = {}
    for w in words:
        bad[w] = bad[w] + 1
except KeyError as ex:
    print(f"\nnaive bad[w] + 1 -> KeyError: {ex}")

Run it:

python3 word_freq.py

19 words, 12 unique
way1 == way2: True
way2 == way3: True
way1 == way3: True

top 3 (Counter.most_common):
  the    ##### 5
  fox    ### 3
  dog    ## 2

naive bad[w] + 1 -> KeyError: 'the'

What just happened: three different tools produced identical dicts — counts_get == counts_dd == counts_ctr is True, because defaultdict and Counter are dicts (subclasses), so they compare equal to a plain dict with the same pairs. The last block is the bug you’d write on day one: bad[w] + 1 reads a key that does not exist yet, so the very first word raises KeyError: 'the'. .get(w, 0) fixes it by supplying the “not seen yet” default; defaultdict(int) fixes it by manufacturing the 0 on demand; Counter fixes it by being purpose-built. For counting, always use Counter — the other two are what you use when the values aren’t counts.

Step 2 — Diff two lists of user IDs

Create id_diff.py:

"""Diff two lists of user IDs with set algebra, then dedupe keeping order."""

# Yesterday's export and today's export, straight from two CSVs.
yesterday = ["u1", "u2", "u3", "u4", "u5", "u3"]   # note: u3 listed twice
today     = ["u3", "u4", "u5", "u6", "u7"]

old, new = set(yesterday), set(today)
print(f"yesterday: {len(yesterday)} rows -> {len(old)} unique")
print(f"today    : {len(today)} rows -> {len(new)} unique")

# sorted() because a set has NO order — sort for stable, printable output
print("\nadded   (new - old):", sorted(new - old))
print("removed (old - new):", sorted(old - new))
print("common  (old & new):", sorted(old & new))
print("churned (old ^ new):", sorted(old ^ new))

print("\nis today a subset of yesterday? ", new <= old)
print("do they overlap at all?         ", not old.isdisjoint(new))

python3 id_diff.py

yesterday: 6 rows -> 5 unique
today    : 5 rows -> 5 unique

added   (new - old): ['u6', 'u7']
removed (old - new): ['u1', 'u2']
common  (old & new): ['u3', 'u4', 'u5']
churned (old ^ new): ['u1', 'u2', 'u6', 'u7']

is today a subset of yesterday?  False
do they overlap at all?          True

What just happened: set(yesterday) turned 6 rows into 5 unique IDs — the duplicate u3 vanished without a word. Then four set operations answered a real question (“who joined, who left, who stayed, what churned?”) in four lines with no loops at all. The sorted() calls are not decoration: without them the order would differ between runs.

Step 3 — Dedupe while preserving order

Append this to id_diff.py and re-run:

print("\n-- dedupe --")
print("set() drops duplicates but LOSES order:")
print("   ", set(yesterday), "<- run again, different order!")
print("dict.fromkeys() drops duplicates and KEEPS first-seen order:")
print("   ", list(dict.fromkeys(yesterday)))

# manual, order-preserving dedupe (what fromkeys does under the hood)
seen = set()
ordered = []
for uid in yesterday:
    if uid not in seen:      # O(1) membership test
        seen.add(uid)
        ordered.append(uid)
print("manual seen-set version:")
print("   ", ordered)
print("same as fromkeys:", ordered == list(dict.fromkeys(yesterday)))

-- dedupe --
set() drops duplicates but LOSES order:
    {'u4', 'u2', 'u3', 'u1', 'u5'} <- run again, different order!
dict.fromkeys() drops duplicates and KEEPS first-seen order:
    ['u1', 'u2', 'u3', 'u4', 'u5']
manual seen-set version:
    ['u1', 'u2', 'u3', 'u4', 'u5']
same as fromkeys: True

What just happened: run this twice and the set() line prints its five IDs in a different order each time (string hash salting), while the two ordered versions never budge. dict.fromkeys(seq) is the idiomatic order-preserving dedupe — it exploits the fact that dict keys are unique and insertion-ordered since 3.7. The manual seen loop shows what it’s doing underneath, and is the pattern to reach for when you need to dedupe on a computed key (e.g. lowercase the email before comparing).

Step 4 — Prove O(1) vs O(n) with timeit

Create bench_lab.py:

"""Prove O(1) vs O(n) with timeit. Numbers vary by machine; the RATIO is the point."""
import timeit

SETUP = """
n = {n}
haystack_list = list(range(n))
haystack_set  = set(haystack_list)
needle = n - 1          # worst case for the list: the very last item
"""

print(f"{'n':>10} | {'list (us)':>12} | {'set (us)':>9} | {'set is':>12}")
print("-" * 52)
for n in (1_000, 10_000, 100_000, 1_000_000):
    setup = SETUP.format(n=n)
    reps = 200 if n <= 10_000 else 20
    t_list = timeit.timeit("needle in haystack_list", setup=setup, number=reps) / reps
    t_set = timeit.timeit("needle in haystack_set", setup=setup, number=reps) / reps
    print(f"{n:>10,} | {t_list*1e6:>12.2f} | {t_set*1e6:>9.3f} | {t_list/t_set:>10,.0f}x")

print("\nlist grows 10x slower each time (O(n)); set does not move (O(1)).")

# Honest caveat: if the item is at the FRONT, the list is fine.
setup = SETUP.format(n=1_000_000).replace("needle = n - 1", "needle = 0")
t_list = timeit.timeit("needle in haystack_list", setup=setup, number=100) / 100
t_set = timeit.timeit("needle in haystack_set", setup=setup, number=100) / 100
print(f"\nneedle at index 0 of 1M: list {t_list*1e9:.0f} ns vs set {t_set*1e9:.0f} ns")

python3 bench_lab.py     # about a second — most of it building the million-item list

         n |    list (us) |  set (us) |       set is
----------------------------------------------------
     1,000 |         6.27 |     0.023 |        269x
    10,000 |        60.25 |     0.021 |      2,892x
   100,000 |       554.54 |     0.085 |      6,493x
 1,000,000 |      4711.37 |     0.038 |    125,635x

list grows 10x slower each time (O(n)); set does not move (O(1)).

needle at index 0 of 1M: list 28 ns vs set 26 ns

What just happened: your absolute numbers will differ — the shape is the lesson. Read the list column downwards: 6 → 60 → 554 → 4,711. Every time the data got 10× bigger, the search got 10× slower. That is O(n) with your own eyes. Now read the set column: 0.023 → 0.021 → 0.085 → 0.038. It does not move. A thousand items or a million, the set answers in the same breath — O(1). The final line is the honesty check: with the needle at index 0, the list is just as fast, because O(n) is the worst case. Sets aren’t magic, they’re reliable.

---

Common mistakes and troubleshooting

Three gotchas deserve more than a table row.

1. .get() returning None silently. .get() fixes KeyError, but it can also hide a bug. A KeyError is loud — it names the key and the line. .get() hands back None and lets your program carry on with nonsense, so the explosion lands somewhere else entirely:

scores = {"ada": 10}
total = scores.get("grace") + 5

Traceback (most recent call last):
  File "/home/you/tb5.py", line 2, in <module>
    total = scores.get("grace") + 5
            ~~~~~~~~~~~~~~~~~~~~^~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The error says TypeError on line 2, but the real bug is that "grace" was never in scores. Two rules: give .get() a default of the right type (scores.get("grace", 0) + 5 works), and use bare d[k] when a missing key genuinely means broken data — you want that crash. Also beware if d.get(k):, which is False for a key holding 0, "" or False. Ask if k in d: when you mean “is it present?”.

2. True == 1 and the invisible key merge. Python considers 1, 1.0 and True to be the same key, because they compare equal and hash equal. A dict cannot tell them apart:

print(hash(1), hash(1.0), hash(True))    # => 1 1 1
print(1 == 1.0 == True)                  # => True

d = {1: "int", 1.0: "float", True: "bool"}
print(d)         # => {1: 'bool'}   <- THREE literals, ONE entry
print(len(d))    # => 1
print({1, 1.0, True, 2})                 # => {1, 2}

Three pairs went in and one came out. Note the subtlety: the key stays 1 (the first one inserted is kept) while the value becomes "bool" (the last one wins). Mixing bools and numbers as keys is rare but produces bafflingly silent data loss when it happens. Floats have a related problem — {0.1 + 0.2: "x"} cannot be found with 0.3, because 0.1 + 0.2 is really 0.30000000000000004. Don’t use floats as keys.

3. Mutating while iterating. Worth repeating because the traceback points at the for line, not the line you actually wrote wrong. Any time you want to filter a dict, reach for a comprehension ({k: v for k, v in d.items() if …}) rather than a del inside a loop. It is shorter, faster, and cannot raise RuntimeError.

---

Cheat-sheet

Dictionaries

Sets

---

Interview and exam questions

Q: What’s the difference between a list and a dict, and when do you choose each? A: A list is an ordered sequence indexed by position; a dict maps unique keys to values. Choose a list when order matters and you access by index or iterate everything. Choose a dict when you look things up by a name/ID — that lookup is O(1) for a dict versus O(n) for scanning a list.

Q: Why can’t a list be a dict key? A: Keys must be hashable — they need a hash() that never changes while the key is in the dict, because the hash decides which slot stores the entry. Lists are mutable, so their hash could change after insertion and the value would be unreachable. Python forbids it up front with TypeError: unhashable type: 'list'. Use a tuple instead.

Q: What’s the difference between d[k], d.get(k) and d.setdefault(k, v)? A: d[k] returns the value or raises KeyError. d.get(k) returns the value or None (or a default you pass) and never modifies the dict. d.setdefault(k, v) returns the value if present, otherwise inserts v and returns it. Only setdefault mutates.

Q: You iterate a dict with for x in d: — what is x? A: The keys. for x in d: is for x in d.keys(). For values use d.values(); for both use for k, v in d.items():.

Q: Are dicts ordered? A: Yes — insertion-ordered since Python 3.7 (an implementation detail of CPython 3.6 that became a language guarantee). Iteration replays insertion order. But == between dicts ignores order, and it’s insertion order, not sorted order. Sets remain genuinely unordered.

Q: Explain why x in my_set is faster than x in my_list. A: A set hashes x to an integer, masks it to a slot, jumps there and compares — a constant number of steps regardless of size: O(1) average. A list compares element by element from the start: O(n). At a million items that’s ~4,700 µs versus ~0.04 µs. The caveat: O(n) is the list’s worst case; if the item is near the front the list is fine.

Q: What happens when two different keys hash to the same slot? A: A collision. Python probes other slots in a fixed sequence until it finds a free one (or the matching key), comparing full keys with == to confirm. Correctness is unaffected; a collision just costs extra steps. Pathologically many collisions degrade a dict to O(n), which is why string hashing is randomised per process — to stop attackers engineering it.

Q (coding): Count word frequencies and return the top 3. A:

from collections import Counter
def top3(text: str) -> list[tuple[str, int]]:
    return Counter(text.split()).most_common(3)

Without Counter: counts[w] = counts.get(w, 0) + 1 in a loop, then sorted(counts.items(), key=lambda kv: -kv[1])[:3].

Q (coding): Remove duplicates from a list while preserving order. A:

def dedupe(seq: list) -> list:
    return list(dict.fromkeys(seq))          # dict keys are unique AND ordered (3.7+)

set(seq) also dedupes but loses order. The manual version uses a seen = set() for O(1) checks — never if x not in result_list, which is O(n) per item and makes the whole thing O(n²).

Q (coding): Given two lists of IDs, find what was added and removed. A:

old, new = set(old_ids), set(new_ids)
added, removed = new - old, old - new

Q: Why does {1: 'a', True: 'b'} have only one entry? A: 1 == True and hash(1) == hash(True) == 1, so the dict treats them as the same key. The first key inserted is kept (1) and the last value wins ('b'), giving {1: 'b'}. 1.0 joins the same collision. Don’t mix bools, ints and floats as keys.

Q: When would you use a frozenset? A: When you need a set to be hashable — as a dict key or as a member of another set. For example, caching results keyed by the set of permissions in a request, or building a set of unique groups where each group is itself a set.

---

Key takeaways

• A dict maps keys to values with O(1) average lookup. It is the workhorse of Python — objects, modules, kwargs and JSON are all dicts underneath. A list is for order; a dict is for lookup by name.
• Keys must be hashable, which in practice means immutable — str, int, tuple, frozenset are fine; list, dict and set raise TypeError: unhashable type. A tuple counts only if everything inside it does too.
• d[k] raises KeyError; d.get(k, default) is the fix — but a default of the wrong type just moves the crash. Reach for d[k] when a missing key really is a bug you want to hear about.
• Iterating a dict gives you keys. for k, v in d.items(): is the idiom to burn in. Never add or delete keys while iterating — snapshot with list(d) or rebuild with a comprehension.
• Insertion order has been guaranteed since 3.7, which is why list(dict.fromkeys(seq)) is the one-line order-preserving dedupe. Any tutorial calling dicts unordered is out of date.
• Use Counter for counting and defaultdict for grouping — but remember reading a missing key on a defaultdict silently inserts it. OrderedDict is now mostly historical.
• {} is an empty dict; set() is the only empty set. Sets are unordered (so no indexing — TypeError: 'set' object is not subscriptable) and their print order for strings genuinely changes between runs. Call sorted() for stable output.
• Set algebra replaces nested loops: | union, & intersection, - difference, ^ symmetric difference. Operators need sets on both sides; the method twins (.union()) take any iterable.
• Hashing is the whole story: key → hash() → slot → value, in a constant number of steps no matter the size. That’s O(1) for dicts and sets versus O(n) for a list scan — worth ~100,000× at a million items, paid for with roughly 4.5× the memory.