Tuples, Sets, Dicts

Data Structures in Practice

Chapter 3 · Tuples, Sets, Dicts

Chapter 2 looked inside the list. This chapter covers three neighbours that solve problems a list handles badly: the tuple (a list that cannot change), the set (membership and uniqueness) and the dict (lookup by key). The last two rest on one idea, hashing, so the rules for what may be hashed come first.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings are claimed in this chapter. Where the order of a set is involved, the text says so: set order is not something to rely on.

Tuples: Fixed Shape

A tuple is an ordered row of references like a list, but it cannot be changed after creation: no append, no item assignment. That gives you a promise to the reader (this group of values is a single fixed record) and a practical benefit: a tuple of hashable items can itself be hashed.

p = (3, 4)
try:
    p[0] = 9
except TypeError as e:
    print("TypeError:", e)

t = ([1, 2], 5)
t[0].append(3)
print(t)
    

TypeError: 'tuple' object does not support item assignment
([1, 2, 3], 5)
    

Shallow immutability

A tuple fixes which objects it holds, not what those objects contain. A list inside a tuple can still change, exactly like the shallow copies of Data Structures in Practice 2. A tuple holding a list is also not hashable, as the next section shows.

The Hashing Rule

Sets and dict keys are stored by hash: a whole number computed from the value, used to jump straight to the right spot instead of scanning (the idea behind the constant-cost lookups in Data Structures in Practice 1). For that to work, a value's hash must never change while it is stored, so Python only allows hashable values, which in practice means immutable ones. Equal values must also have equal hashes.

def key_ok(k):
    try:
        hash(k)
        return True
    except TypeError:
        return False

print(key_ok((1, 2)), key_ok([1, 2]), key_ok((1, [2])))
print(key_ok(frozenset({1})), key_ok({1}))

grid = {(0, 0): "start", (2, 3): "goal"}
print(grid[(2, 3)])
    

True False False
True False
goal
    

So: numbers, strings, None, tuples of hashables and frozenset (an immutable set) may be keys; lists, sets and dicts may not. The tuple-as-key trick is the everyday payoff: coordinates, pairs and composite identifiers make natural keys.

Equal Values Collide

Because equal values must hash alike, 1, 1.0 and True are the same key:

print(hash(1) == hash(1.0), 1 == 1.0)
print({1: "a", 1.0: "b", True: "c"})
    

True True
{1: 'c'}
    

One entry survives, keeping the first key but the last value. For your own classes, defining __eq__ without __hash__ makes instances unhashable (Python refuses to guess); define both, based on the same fields, to use them in sets:

class Q:
    def __init__(self, x):
        self.x = x
    def __eq__(self, other):
        return isinstance(other, Q) and self.x == other.x
    def __hash__(self):
        return hash(self.x)

print(len({Q(1), Q(1)}))
    

Sets: Membership and Algebra

A set stores each value once and answers x in s by hashing, not scanning. It also supports the operations from school maths, which replace many hand-written loops:

Question	Operator	Method
In either?	a \| b	union
In both?	a & b	intersection
In a but not b?	a - b	difference
In exactly one?	a ^ b	symmetric_difference
Is a inside b?	a <= b	issubset
Nothing shared?	(none)	isdisjoint

a = {1, 2, 3, 4}
b = {3, 4, 5}
print(a | b, a & b, a - b, a ^ b)
print({1, 2} <= a, a.isdisjoint({9}))
    

{1, 2, 3, 4, 5} {3, 4} {1, 2} {1, 2, 5}
True True
    

Do not rely on set order

Small whole numbers happen to print in order here, but a set makes no ordering promise. Use sorted(s) whenever order matters. Also, {} is an empty dict; an empty set is set().

Removing Duplicates

set(items) removes duplicates but loses the original order. To keep first-seen order, use dict.fromkeys, since a dict remembers insertion order (next section):

words = ["to", "be", "or", "not", "to", "be"]
print(len(set(words)))
print(list(dict.fromkeys(words)))
    

4
['to', 'be', 'or', 'not']
    

Dicts: Patterns You Will Reuse

A dict maps hashable keys to any values. Since Python 3.7 it remembers insertion order (a language guarantee, unlike sets). Re-assigning an existing key keeps its position; deleting and re-adding moves it to the end. Two dicts are equal when they hold the same pairs, regardless of order, which is different from lists.

d2 = {"b": 1, "a": 2}
d2["c"] = 3
del d2["b"]
d2["b"] = 4
print(d2, list(d2))
print({"x": 1, "y": 2} == {"y": 2, "x": 1}, [1, 2] == [2, 1])
    

{'a': 2, 'c': 3, 'b': 4} ['a', 'c', 'b']
True False
    

Counting and Grouping

The two commonest jobs are counting things and collecting things by key. Plain dicts do both with get and setdefault; the standard library adds Counter and defaultdict to say it more directly.

from collections import defaultdict, Counter

d = {}
for w in words:
    d[w] = d.get(w, 0) + 1
print(d)

g = defaultdict(list)
for w in words:
    g[len(w)].append(w)
print(dict(g))

print(Counter(words).most_common(2))
    

{'to': 2, 'be': 2, 'or': 1, 'not': 1}
{2: ['to', 'be', 'or', 'to', 'be'], 3: ['not']}
[('to', 2), ('be', 2)]
    

Safe Lookups and Merging

print(d2.setdefault("z", 0), d2.pop("q", "none"))
print({**{"a": 1, "b": 2}, **{"b": 3}}, {"a": 1} | {"a": 2})
    

0 none
{'a': 1, 'b': 3} {'a': 2}
    

In both merges the right-hand dict wins on a shared key. d[k] raises KeyError for a missing key; d.get(k, default) and d.pop(k, default) do not.

A decision habit

Ask what the question is. "Is it in there?" or "what is unique?" points to a set. "What goes with this key?" points to a dict. "Which position?" or "keep it in sequence" points to a list. "A fixed record, or a key made of several parts" points to a tuple.

Challenges

Exercise 1

Write can_be_key(value) that returns True if the value could be used as a dict key (use hash inside try/except). Test it on 5, "hi", (1, 2), [1, 2], (1, [2]), {1}, frozenset({1}) and None, and say which results come from the tuple rule.

📄 View solution

Exercise 2

Write unique_in_order(items) two ways: with dict.fromkeys, and with a seen set plus a result list. Check both give [3, 1, 2, 4] for [3, 1, 3, 2, 1, 4], and explain why plain list(set(items)) is not good enough.

📄 View solution

Exercise 3

Write group_by_first_letter(words) returning a dict from first letter to the list of words starting with it (use setdefault). Then, given the sets {"ann", "bob", "cy"} and {"bob", "dee"}, print the sorted union, intersection, difference and symmetric difference.

📄 View solution

Quick Reference

Tuple: fixed record; hashable if everything inside is hashable
Hashable means immutable in practice; equal values must hash equal
Set: unique values, fast membership, algebra with | & - ^; never rely on order
Dict: key to value, insertion order guaranteed, equality ignores order
Counting and grouping: Counter, defaultdict, setdefault
Order-preserving unique: list(dict.fromkeys(items))

Coming next

Data Structures in Practice 4 covers stacks and queues: last-in-first-out and first-in-first-out, deque, the queue module, and uses such as undo history and task queues.