--- title: Dictionaries source: 'https://academia.sh/en/courses/python-data-structures/dictionaries' course: 'Data Structures and Functional Tools' language: en updated: '2026-08-17T18:10:25+00:00' license: 'CC BY-SA 4.0' --- # Dictionaries Searching for the same item among two hundred does 200 comparisons in a list but 1 in a set and a dict; asking for keys returns not a copy but a view, and it sees a key added afterward — going from 2 to 3, while a list snapshot stays at 2. The previous lesson showed a tuple **could be** a key and measured that a key is found by equality, not identity. The container that takes a key and reaches a value was not measured. A **dict** is the container that binds a key to a value. This lesson asks it two questions, both answered with a number. The first pays the first half of the course's fourth debt: when the same two hundred items are searched for in a list and a set, **how many comparisons** happen? The data is the same, the items are the same; only the container holding them changes. The second is about copying: when a dict's keys are asked for, is what comes back a **copy**, or a **window** that keeps looking at the dict? ## What a Mapping Looks At A list has one way to search for an item: walk the slots in order and ask each one whether it equals the target. A dict and a set use another way — they compute which bucket a key falls into from its **hash value** and look there directly. This is why both require a hashable key; that was the condition the previous lesson measured. The mechanism itself is not this course's subject. How a hash table is built, load factor, collision resolution, and the table's growth behavior were built in the **Data Structures** course; complexity analysis and growth classes in the **Algorithms** course. Neither repeats here. That built the **mechanism**; here, what's measured is which container Python delivers it through, and how many concrete comparisons a single test costs. The numbers below are not a growth-class claim; they're a count made with specific data. - **CO25** — The item itself counts the comparison: the equality method increments a shared counter every time it is called. The setup is its own oracle; the number is a record, not a guess. - **CO26** — All three containers are built from the **same two hundred items**; the items are created once, and all three containers look at the same objects. - **CO27** — The counter resets **right before** each test; comparisons made while building the containers do not enter the measurement. - **CO28** — The sought item is **rebuilt every time**, so the search has to be done by equality, not identity. - **CO29** — Two conditions are measured separately: an item **found** in the container and one **not found**. - **CO30** — Position effect in the list is measured separately too; the count is read separately for the first, middle, and last item. ```python """Same two hundred items, three containers: how many comparisons does membership testing do.""" class Counting: """A value that counts equality comparisons.""" counter = {"comparisons": 0} def __init__(self, value): self.value = value def __eq__(self, other): Counting.counter["comparisons"] += 1 return isinstance(other, Counting) and self.value == other.value def __hash__(self): return hash(self.value) def measure(container, target): Counting.counter["comparisons"] = 0 found = target in container return Counting.counter["comparisons"], found N = 200 ITEMS = [Counting(i) for i in range(N)] CONTAINERS = (("list", list(ITEMS)), ("set", set(ITEMS)), ("dict", {o: o.value for o in ITEMS})) print(f"{'container':<10s}{'searching last item':>20s}{'found':>9s}" f"{'searching missing item':>25s}{'found':>9s}") for label, container in CONTAINERS: present, found1 = measure(container, Counting(N - 1)) absent, found2 = measure(container, Counting(N)) print(f"{label:<10s}{present:>20d}{str(found1):>9s}{absent:>25d}{str(found2):>9s}") print() first_count, _ = measure(CONTAINERS[0][1], Counting(0)) middle_count, _ = measure(CONTAINERS[0][1], Counting(N // 2)) print(f"in list, first item {first_count} | middle item {middle_count} | " f"last item {measure(CONTAINERS[0][1], Counting(N - 1))[0]}") print(f"in set, first item {measure(CONTAINERS[1][1], Counting(0))[0]} | " f"middle item {measure(CONTAINERS[1][1], Counting(N // 2))[0]} | " f"last item {measure(CONTAINERS[1][1], Counting(N - 1))[0]}") print() DICT_C = CONTAINERS[2][1] Counting.counter["comparisons"] = 0 value = DICT_C[Counting(N - 1)] print(f"reading a value from the dict: {Counting.counter['comparisons']} comparisons, " f"returned value {value}") ``` ``` container searching last item found searching missing item found list 200 True 200 False set 1 True 0 False dict 1 True 0 False in list, first item 1 | middle item 101 | last item 200 in set, first item 1 | middle item 1 | last item 1 reading a value from the dict: 1 comparisons, returned value 199 ``` ## Two Hundred Against One The upper table's first column gives the course's fourth debt: searching for the same item does **200** comparisons in a list, **1** in a set and a dict. Same data, same objects, same target value. Only the access method changes. **Cost is decided by access method, not data.** The second column sharpens the distinction further. Searching for an item **not in** the container, the list still does **200** comparisons — to know it is not there, it has to look at all of them. The set and dict do **0**: the hash computation took them to an empty bucket, and there was nothing there to compare against. Proving absence is the most expensive thing in a list, and the cheapest in a set. The two middle rows show a list's number **is not one number**: first item **1**, middle **101**, last **200** comparisons. In a list, cost depends on **where** the target sits. The same three searches in a set give **1**, **1**, **1** — position never enters the measurement, because a set does not walk slots, it computes. The last row measures a dict's real job. Reaching a value from a key does **1** comparison — the same number as set membership. A dict does the same search a set does, and keeps the value where it finds it. The two are two faces of the same mechanism: a set only says "is it there," a dict says "yes, and here's what it maps to." ## View or Snapshot The forms that ask for a dict's keys, values, or pairs do not return a list. What they return is a **view**: an object with no slots of its own that keeps looking at the dict. Its opposite is a **snapshot** — a list that freezes the state at the moment it was asked for in a separate container, breaking its link to the dict. Building both at the same moment and then mutating the dict makes the difference measurable. - **CO31** — Three views and one snapshot are built **at the same moment**, before the dict is touched; then a single key is added, and all four are read again. - **CO32** — Length is read from each container with its own method; the measurement never derives one container's length from another's. - **CO33** — In the thousand-entry measurement, the snapshot's slot count is printed; the view's slot count is **never printed**, since a view holds no slots. - **CO34** — Two view objects are compared with both `is` and `==`; no identity value is printed, only sameness is tested. - **CO35** — Mutating while looping is tried twice: once over a view, once over a snapshot. The attempt ending in an exception has **added one key** before it is cut off, and the second attempt continues from that state. - **CO36** — The order measurement uses a small three-key dict; order is read from the key list itself. ```python """View versus snapshot: which one sees a key added afterward.""" d = {"a": 1, "b": 2} keys_view = d.keys() values_view = d.values() items_view = d.items() key_list = list(d.keys()) before = (len(keys_view), len(values_view), len(items_view), len(key_list)) d["c"] = 3 after = (len(keys_view), len(values_view), len(items_view), len(key_list)) print(f"{'container':<22s}{'before add':>12s}{'after':>7s}" f"{'sees new key':>15s}") for label, before_n, after_n, contains in ( ("keys() view", before[0], after[0], "c" in keys_view), ("values() view", before[1], after[1], 3 in values_view), ("items() view", before[2], after[2], ("c", 3) in items_view), ("list(keys()) copy", before[3], after[3], "c" in key_list)): print(f"{label:<22s}{before_n:>12d}{after_n:>7d}{str(contains):>15s}") print() big = {i: i for i in range(1000)} view = big.keys() snapshot = list(big.keys()) print(f"in a thousand-entry dict, the view holds no slots; the snapshot holds " f"{len(snapshot)}") print(f"view is big.keys() -> {view is big.keys()} | " f"view == big.keys() -> {view == big.keys()}") print() try: for key in big: if key == 3: big[1000] = 1000 except RuntimeError as e: print(f"adding while looping over a view: {type(e).__name__}") snapshot_turns = 0 for key in list(big): if key == 3: big[1001] = 1001 snapshot_turns += 1 print(f"adding while looping over a snapshot: no problem, " f"{snapshot_turns} turns ran, dict grew to {len(big)} entries") print() order = {"north": 1, "slope": 2, "summary": 3} print(f"insertion order: {list(order)}") del order["north"] order["north"] = 9 print(f"after delete and re-add: {list(order)}") order["slope"] = 20 print(f"after changing an existing key's value: {list(order)}") ``` ``` container before add after sees new key keys() view 2 3 True values() view 2 3 True items() view 2 3 True list(keys()) copy 2 2 False in a thousand-entry dict, the view holds no slots; the snapshot holds 1000 view is big.keys() -> False | view == big.keys() -> True adding while looping over a view: RuntimeError adding while looping over a snapshot: no problem, 1001 turns ran, dict grew to 1002 entries insertion order: ['north', 'slope', 'summary'] after delete and re-add: ['slope', 'summary', 'north'] after changing an existing key's value: ['slope', 'summary', 'north'] ``` ## The Window Never Closes The upper table puts three of four rows on the same side. All three views go from length **2** to **3**, and all three **see** the key added afterward. The snapshot stays at **2** and does not see it. The views did not even exist at the moment of the addition — the dict had two entries when they were built. But what they carried was not two entries, it was a **link to the dict itself**; when the dict changed, what they saw changed too. The second block sets the cost and the gain side by side. In the thousand-entry dict, the snapshot opens **1000** slots — one link per key. The view opens none; no matter how large the dict it looks at, what it carries is a single link. If a dict's keys will only be looped over, taking a snapshot is a thousand-slot cost for nothing in return. The view object itself is rebuilt every time it is asked for — `view is big.keys()` is **False** — but two views count as equal, because both look at the same dict. What's paid in exchange is in the third block. Adding a key to the dict while looping over a view gives `RuntimeError`: once the dict grows during the loop, where the view is looking becomes ambiguous, and the language treats this as a fault and cuts the loop. The same work runs fine over a snapshot — it carries the state at the moment it was taken, and the turn count does not change no matter what happens to the dict afterward. The second measurement starting at **1001** turns is because the first, cut-off loop had already added one key before the exception. The rule that follows: **take a snapshot if it is going to be mutated while looping, use a view if it is only going to be read.** A snapshot's cost is slots, a view's cost is fragility. The last three lines show ordering. Keys stay in **insertion order**. A key deleted and re-added goes not to the front but to the **end**, because re-adding is a new entry. Changing an existing key's value does not disturb the order at all — the entry's place is kept, only its value is refreshed. ## Spellings for Merging and Looking Up For lists, `+` versus `+=` was the difference between building a new container and growing the existing one. The same distinction exists for dicts, in five separate spellings. Next to it sits the lookup side: five spellings do five different things when a key that does not exist is asked for. - **CO37** — All five forms start from a **freshly built** copy of the same three-entry dict; value objects are created once before the measurement. - **CO38** — The dict on the right **collides on one key** with the one on the left, showing how the merge finds the key count. - **CO39** — On the lookup side, the **class name** of the raised exception is written; if a value is returned, it is printed directly. ```python """Forms of merging a dict, and what five spellings do with a missing key.""" COUNTER = {"created": 0} class Item: def __init__(self, value): COUNTER["created"] += 1 self.value = value def __repr__(self): return f"Item({self.value})" def reset(): COUNTER["created"] = 0 def created(): return COUNTER["created"] VALUES = {name: Item(i) for i, name in enumerate(("north", "slope", "summary", "south"))} LEFT = {"north": VALUES["north"], "slope": VALUES["slope"], "summary": VALUES["summary"]} RIGHT = {"summary": VALUES["south"], "south": VALUES["south"]} def union_new(d): return d | RIGHT def union_inplace(d): d |= RIGHT return d def update_fn(d): d.update(RIGHT) return d def copy_fn(d): return dict(d) def unpack_build(d): return {**d, **RIGHT} FORMS = (("d | e", union_new), ("d |= e", union_inplace), ("d.update(e)", update_fn), ("dict(d)", copy_fn), ("{**d, **e}", unpack_build)) print(f"{'form':<14s}{'new items':>9s}{'same container':>16s}{'keys':>7s}" f"{'values shared':>16s}") for label, op in FORMS: d = dict(LEFT) before = d reset() result = op(d) shared = all(any(v is x for x in VALUES.values()) for v in result.values()) print(f"{label:<14s}{created():>9d}{str(result is before):>16s}" f"{len(result):>7d}{str(shared):>16s}") print() merged = LEFT | RIGHT print(f"colliding key 'summary' -> {merged['summary']} | " f"same object as right side's value: {merged['summary'] is RIGHT['summary']}") print() print(f"{'spelling':<24s}{'result'}") try: LEFT["missing"] except KeyError as e: print(f"{'d[missing]':<24s}{type(e).__name__}") print(f"{'d.get(missing)':<24s}{LEFT.get('missing')}") print(f"{'d.get(missing, default)':<24s}{LEFT.get('missing', Item(9))}") print(f"{'d.pop(missing, default)':<24s}{LEFT.pop('missing', Item(9))}") print(f"{'missing in d':<24s}{'missing' in LEFT}") ``` ``` form new items same container keys values shared d | e 0 False 4 True d |= e 0 True 4 True d.update(e) 0 True 4 True dict(d) 0 False 3 True {**d, **e} 0 False 4 True colliding key 'summary' -> Item(3) | same object as right side's value: True spelling result d[missing] KeyError d.get(missing) None d.get(missing, default) Item(9) d.pop(missing, default) Item(9) missing in d False ``` All five forms create **0** new values, and all five share values. A dict does on the key side what a list does: what it carries is not values, it is links to them. The distinction is again in the "same container" column — `d | e`, `dict(d)`, and `{**d, **e}` build a new container, `d |= e` and `d.update(e)` grow the existing one. Key count is not five, the sum of three and two — it is **4**. The colliding key is not counted twice; the right side's value overwrites the left's, and `merged['summary'] is RIGHT['summary']` confirms it. Merging a dict's result is therefore not a predictable number — it depends on the collision count, and only the keys can say what that is. The lower table gives the five spellings' answer to a missing key. Only bracket access produces an **exception**; the remaining four return a value. `get` without a default gives `None`, and that is not a fault report — a dict could hold a key whose value really is `None`, so getting `None` back is not a certain way to say "missing." The only spelling that tests absence for certain is membership testing, done with the **1** or **0** comparisons from this lesson's first measurement. ## Summary - On the same two hundred items, membership testing does **200** comparisons in a list, **1** in a set and a dict; searching for an item not present, the list still does **200**, the set and dict do **0**. - A list's number depends on position — first item **1**, middle **101**, last **200**; in a set all three searches give **1**, because a set computes rather than walking slots. - `keys()`, `values()`, and `items()` are views: they keep looking at the dict and see a key added afterward — their length goes from **2** to **3**. A snapshot taken with `list(...)` stays at **2**. - A view holds no slots; a thousand-entry dict's snapshot opens **1000**. In exchange, adding to the dict while looping over a view gives `RuntimeError`, while looping over a snapshot does not. - Keys stay in insertion order; a deleted and re-added key goes to the end, and changing an existing key's value does not disturb the order. ## Next Step In this lesson's measurement, the set stood quietly beside the dict and gave the same numbers — **1** and **0**. What it does on its own was never asked. The next lesson looks at the set alone and measures its most common job: dropping duplicates from a list. The question again gets a numeric answer. How many comparisons and how many objects does hand-picking duplicates cost against handing them to a set, and are the items coming back out of a set new or old?