Pebellslearn by building
0%
RoadmapsMatrixCoursesSandboxSign in
The Object Model  ›  Lesson

Mutable, Immutable & Hashable

Mutability 22 minWhich objects can change in place, and why only objects whose hash can never change are allowed to be keys
You're building a piece ofQuarry — the inspector
This piece — dedupe_rows(): Freezes nested rows into hashable keys, so duplicate rows can be found with a set instead of a double loop.
Scenario Quarry pulls the same export from two mirrors, and `set(rows)` refuses to help, because a list can't be a key.
Your task
Write dedupe_rows(rows): remove duplicate rows, keeping the first copy of each in the original order. Rows are JSON values (lists, dicts, strings, numbers, nested). Freeze each row into a hashable key — lists to tuples, dicts to frozensets of (key, frozen value) — and track the keys in a set. Return the original rows. Example: dedupe_rows([[1, 2], [1, 2], [2, 1]]) → [[1, 2], [2, 1]].

Mutable, Immutable & Hashable

In short: objects split into mutable (list, dict, set, most of your own classes — they can change value while keeping their identity) and immutable (int, str, tuple, frozenset, bool, None — they can't change at all). += mutates in place on a mutable object but builds a new object and rebinds the name on an immutable one — the difference only shows when a second name is watching. A dict/set key must be hashable, which really means "guaranteed not to change while it's stored" — that's why a plain list can never be a key, and why a key's hash must never change once it's filed, or the entry becomes unreachable even though it's still sitting there.

Key(["pune"]) filed in slot 6 of a dict's table; after k.fields.append("2026") the same key now hashes to slot 1, which is empty — the lookup says False even though the entry is still sitting in slot 6

+= on a string vs. a list

s += "!" and row += ["b"] look identical. They aren't:

python

A string can't grow, so += has to build a new one and rebind s. A list can grow, so += calls its in-place __iadd__ and keeps the same identity. The gap only shows when someone else is still holding the original:

What does this print?
t = (1, 2)
u = t
t += (3,)
print(u)

A tuple that still isn't fully frozen

A tuple locks which objects it holds, not whether those objects can change:

What does this print?
t = ([1, 2], "x")
try:
    t[0] += [3]
except TypeError:
    pass
print(t[0])

A tuple's immutability is shallow: it guarantees its own slots never point somewhere else, and says nothing about what those slots contain.

A dict key that goes missing

A dict doesn't search its keys one by one — it hashes the key to pick a slot, then confirms with ==. That only works if a key's hash is stable, which is exactly what a mutable value can't promise. The slot numbers below are only for illustration, since the real ones depend on the table's size:

watch it move · array

A dict files each key in the slot its hash picks. If a key's hash changes after it is filed, every later lookup searches the wrong slot.

The tuple ("pune", 2026) hashes to a number that picks slot 3, so the key is filed there. 8 cells. At index 3.

1 / 5
python

The entry never left. Step through the same class and watch found:

step through it
1class Key:
2 def __init__(self, fields):
3 self.fields = fields
4 def __eq__(self, other):
5 return self.fields == other.fields
6 def __hash__(self):
7 return hash(tuple(self.fields))
8 
9k = Key(["pune"])
10table = {k: "row 17"}
11found = k in table
12k.fields.append("2026")
13found = k in table
14still_there = any(key is k for key in table)
15table = {key: v for key, v in table.items()}
16found = k in table

After the append, found is False even though still_there is True. The lookup hashes the key's new value, goes to the wrong slot, and finds nothing. Rebuilding the dict (the last line) fixes it, because every key gets hashed again — but nothing tells you when a rebuild is needed, so that isn't a real fix. k's hash changed after it was filed, so a lookup now starts at the wrong slot and finds nothing. The real fix: hash only what can't change. Freeze the fields into a tuple, and refuse to let them be reassigned:

python

Any built-in mutable type refuses to hash at all rather than risk this: hash([1, 2]), hash({"a": 1}) and hash((1, [2])) all raise TypeError — even a tuple is only hashable if everything inside it is.

Freeze a row before using it as a key

Quarry's rows are lists and dicts, straight from JSON — never hashable as they are. To dedupe them, freeze each row into an equal-meaning immutable value, recursively:

python

frozenset for a dict's items ignores order, the same way dict equality does. One trap worth knowing: True == 1 and hash(True) == hash(1), so {1, True} has a single element. If a column might hold either, freeze (type(v).__name__, v) instead of the bare value.

Quick practice

What does this print?
results = []
for value in ([1, 2], (1, 2), {"a": 1}):
    try:
        hash(value)
        results.append("hashable")
    except TypeError:
        results.append("unhashable")
print(" ".join(results))
broken — fix it

Each call should start its own log. Run it, notice a and b are the same list, then fix the default.

🎯 Your turn

Write dedupe_rows(rows) for the inspector. rows is a list of JSON values — lists, dicts, strings or numbers, nested to any depth. Return the rows with duplicates removed, keeping the first copy and the original order. Two rows are duplicates if they're equal, including dicts whose keys appear in a different order.

  • dedupe_rows([[1, 2], [1, 2], [2, 1]]) → [[1, 2], [2, 1]]
  • dedupe_rows([{"id": 1, "tags": ["a"]}, {"tags": ["a"], "id": 1}]) → [{"id": 1, "tags": ["a"]}]

Hint: freeze each row (lists → tuples, dicts → frozensets of (key, frozen value) pairs, recursively), and use a set of frozen forms to check "seen before" in one hash lookup instead of comparing against every row so far.

Press ▶ Run, then ✓ Check. ✅

Practice — level up

0/6 solved

Solve each in its own editor — Run to try, Check to grade. Stuck? Reveal a Hint, or the full Solution + walkthrough.

Warm-upCan it be a key?

Write hashable_flags(values) returning a list with one boolean per value: True if it can be a dict key, False if not. Ask Python rather than checking types: try hash(value) and catch the TypeError.

mutabilityhashable
DrillEvery call gets its own log

start_log(first, log=[]) is meant to start a new log unless an existing one is passed in. Fix it, and write fresh_logs(firsts), which returns [start_log(f) for f in firsts]. With the shared default, every entry is the same growing list.

mutabilitymutable-default
BuildGroup rows by fields that might be lists

Write group_counts(rows, fields). Each row is a dict. Group the rows by the values of the named fields. Those values can be lists, so freeze them to build the key. Return [[values, count], ...] in first-seen order, where values is the list of the ORIGINAL field values from the first row in the group.

mutabilityhashabledictionaries
BossA key that can't be stranded

Write a class Coord(x, y) that is safe to use as a key. Two Coords with the same x and y must be equal and hash the same, and once built, any attribute assignment must raise AttributeError. Then coord_report(points) (given) builds one per [x, y] point, collects them in a set, tries to move the first one, and returns what happened.

mutability__hash____eq__dunder-methods
CapstoneFind the stranded keys

BadKey (given) hashes a list it still lets you change. Write stranded(keys, edits). Build a dict mapping BadKey(list(items)) to its index, for each list in keys. Apply each edit [i, value] by appending value to key i's list. Return {"stranded": [...], "entries_after_rehash": n}, where stranded lists, in order, the indices whose lookup table.get(key) no longer returns their own index, and n is the size of the dict after rebuilding it from its items.

mutabilityhashable__hash__dictionaries
ExplainHashing a row that can still change

A teammate wants Quarry's Row objects in a set, so they add __hash__ returning hash(tuple(self.fields)), while other stages keep editing row.fields in place. Explain what will go wrong and when, and propose a design that keeps both the set and the editing.

dedupe_rows.py
Call the function you wrote — just like your app's frontend would. Edit the inputs and hit Call.
dedupe_rows(rows) → listDrop duplicate rows, keeping the first copy of each, using frozen keys in a set.
try:
returned
Press Run to execute your code.
Press Check to run the tests for this lesson.