Dictionaries

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.

"""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.

"""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.

"""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?