Associative Containers

Abstract¶

Associative containers allow programmers to store and retrieve values using keys that are not restricted to consecutive integers starting from 0. Python’s dictionary and set will be introduced as examples of associative containers. Similar to sequence types, readers will learn how to construct these containers using enclosure and comprehension, access their keys and values, and utilize various methods to operate on them. To explain the near constant-time lookups, the idea of hashing will be introduced, along with the issues of hash collisions, the basic conflict resolution strategy, and the intricate relationship between hashability and immutability.

import random

import matplotlib.pyplot as plt

%matplotlib widget

Motivation¶

The following code simulates the outcomes of rolling a die multiple times.

dice_rolls = [random.randint(1, 6) for i in range(10)]
print(*dice_rolls)

4 5 2 6 6 4 2 5 2 1

What is the distribution?

plt.figure(0, clear=True)
distribution = [dice_rolls.count(i) / len(dice_rolls) for i in range(7)]
plt.stem(range(7), distribution)
plt.xlabel("Outcomes")
plt.title("Distribution")
plt.ylim(0, 1)
plt.show()

In the above code, distribution[i] stores the fractional count of outcome i.

However, distribution[0] is 0 because a die does not have outcome 0. Can we avoid such redundancy?

distinct_outcomes = [
    outcome for outcome in range(1, 7) if dice_rolls.count(outcome) > 0
]
distribution = [
    dice_rolls.count(distinct_outcomes[i]) / len(dice_rolls)
    for i in range(len(distinct_outcomes))
]

plt.figure(1, clear=True)
plt.stem(distinct_outcomes, distribution)
plt.xlabel("Outcomes")
plt.title("Distribution")
plt.ylim(0, 1)
plt.show()

In the above code,

distinct_outcomes stores the list of distinct outcomes, and
distribution[distinct_outcomes[i]] stores the fractional count of the i-th distinct outcome.

What about finding the distribution of characters in an article?

There are over 1 million unicode characters. Can we:

Obtain the distribution efficiently without creating an entry for each unicode character?
Avoid keeping a separate set of distinct characters in addition to their distribution?
Access the fractional count of a particular character efficiently without searching through the list of distinct outcomes?

It is desirable to have a composite data type that

can keep a set of unique keys of different types (such as the characters in our example), and
associate to different keys possibly different values of any types (such as the fractional counts of the characters).

Such a data structure is called an associative container.

Construction¶

In Python, there are two built-in classes for associative containers:

set can store unique keys of possibly different types.
dictionary can store a set of key-value pairs.

We have already used sets and dictionaries before.

%%pytutor
a = (lambda **kwargs: kwargs)(start=0, stop=5, step=1)
b = set([1, 1, 2, 3, 3, 3])
assert len(a) == len(b)

Both set and dict implement the len method that returns the number of keys. They are mutable, so we can add/remove keys and values and modify their object references.

Similar to tuple/list, we can create a set/dictionary using enclosure and comprehension.

Enclosure¶

For dict, enclose a comma-separated sequence of key : value pairs by braces { and }.

%%pytutor
empty_dictionary = {}
a = {"a": 0, "b": 1}
b = {**a, "c": 0, "d": 1}

For set, omit : value.

%%pytutor
a = {(1, 2.0), print, *range(2), *"23"}
empty_set = {*()}  # Why not use {}?

We can also create a set/dictionary from other objects using their constructors set/dict.

%%pytutor
empty_set = set()
string2set = set("abc")
range2set = set(range(2))
list2set = set(["abc", range(2)])
set2set = set(list2set)

%%pytutor
empty_dict = dict()
enumerate2dict = dict(enumerate("abc"))
zip2dict = dict(zip("abc", "123"))
kwargs2dict = dict(one=1, two=2)
dict2dict = dict(kwargs2dict)

dict.fromkeys?
### BEGIN SOLUTION
fromkeys_dict = dict.fromkeys(range(100), 0)
### END SOLUTION

# test
assert all(fromkeys_dict[k] == 0 for k in fromkeys_dict)

Signature: dict.fromkeys(iterable, value=None, /)
Docstring: Create a new dictionary with keys from iterable and values set to value.
Type:      builtin_function_or_method

Comprehension¶

The following function uses a one-line dictionary comprehension to return the distribution of items in a sequence:

def distribute(seq):
    return {k: seq.count(k) / len(seq) for k in set(seq)}

def plot_distribution(seq, fig_num=None):
    dist = distribute(seq)
    plt.figure(fig_num, clear=True)
    plt.stem(
        dist.keys(),  # set-like view of the keys
        dist.values(),  # view of the values
    )
    plt.xlabel("Items")
    plt.title("Distribution")
    plt.ylim(0, 1)
    plt.show()


plot_distribution("What is the distribution of different characters?", 2)

The object methods keys and values provide a dynamic view of the keys.
Unlike a copy, subsequent changes to the dictionary are also reflected in a previously returned view.
items provides a set-like view of the key-value pairs.

%%pytutor
a = dict(enumerate("abc"))
views = a.keys(), a.values(), a.items()
print(a.pop(1))  # remove the key 1 and its associated value
print(a.popitem())  # remove and return one key-value pair
a.clear()  # clear the dictionary

set has pop and clear but not popitem. However, set.pop behaves like dict.popitem instead of dict.pop.

%%pytutor
a = set("abc")
print(a.pop())  # remove and return an element
a.clear()  # clear the set

def composite_set(stop):
    ### BEGIN SOLUTION
    return {x for factor in range(2, stop) for x in range(factor ** 2, stop, factor)}
    ### END SOLUTION


print(*sorted(composite_set(100)))

4 6 8 9 10 12 14 15 16 18 20 21 22 24 25 26 27 28 30 32 33 34 35 36 38 39 40 42 44 45 46 48 49 50 51 52 54 55 56 57 58 60 62 63 64 65 66 68 69 70 72 74 75 76 77 78 80 81 82 84 85 86 87 88 90 91 92 93 94 95 96 98 99

Fast access to items¶

Hashing¶

Why are some keys missing in the following dictionary/set?

%%pytutor
a = {0: "a", 0.0: "b", 2: "b"}
b = {0j, 0, 0.0, "", False}
assert 0 == 0.0 == 0j == False != ""

Associative containers are implemented as hash tables for efficient lookup of keys.

Hash Tables

Python also uses dictionaries to implement global/local frames, and hash collisions can slow down the lookup process.

What are hashable?

def hashable(obj):
    try:
        hash(obj)
    except Exception:
        return False
    return True


for i in 0, 0.0, 0j, "", False, (), [], {}, set(), frozenset(), ([],):
    if hashable(i):
        print("{} may be hashable. E.g., hash({!r}) == {}".format(type(i), i, hash(i)))
    else:
        print("{} may not be hashable.".format(type(i)))

<class 'int'> may be hashable. E.g., hash(0) == 0
<class 'float'> may be hashable. E.g., hash(0.0) == 0
<class 'complex'> may be hashable. E.g., hash(0j) == 0
<class 'str'> may be hashable. E.g., hash('') == 0
<class 'bool'> may be hashable. E.g., hash(False) == 0
<class 'tuple'> may be hashable. E.g., hash(()) == 5740354900026072187
<class 'list'> may not be hashable.
<class 'dict'> may not be hashable.
<class 'set'> may not be hashable.
<class 'frozenset'> may be hashable. E.g., hash(frozenset()) == 133146708735736
<class 'tuple'> may not be hashable.

set has an immutable counterpart called frozenset, which is hashable.

hashable(frozenset())

True

assert 0 == 0.0 == 0j == False != ""
assert hash(0) == hash(0.0) == hash(0j) == hash(False) == hash("")

Solution to Exercise 3

To avoid duplicate keys occupying different entries in a hash table.
Hash collision can be detected by == and handled by collision resolution techniques. To keep the hash table small, it is unavoidable to have hash collisions.

Solution to Exercise 4

No. hash(([],)) fails in particular because the value of an immutable object can still be changed if it points to a mutable object.

Solution to Exercise 5

No because id remains unchanged even if the value of an object changes.

%%hermes --no-context
Explain in a paragraph or two why most mutable objects are not hashable.

🌿 Fork/new: main (will create on click)

See Also

In Python, the hash value of an object must remain stable for as long as the object is used as a key in a hash‑based container such as a dict or set. When an object is mutable, its internal state can change after it has been inserted into one of these containers. If those changes affect the object’s hash, the container’s internal bucket mapping becomes invalid—looking up the key may fail, collisions balloon, or the structure can even corrupt itself. To avoid these subtle and hard‑to‑diagnose bugs, Python marks most mutable types (lists, dictionaries, bytearrays, etc.) as unhashable by raising a TypeError when hash() is called.

The only mutable types that bypass this rule are some container types that store only hashable items (like list or dict) whose own hash is never used directly; instead, they rely on the hashes of their elements internally. But when a type’s identity itself can change in a way that would alter the hash, the safest design is to make it explicitly unhashable, ensuring that instances can only be used as values or elements in unordered collections, but never as keys in hash‑tables.

%%hermes --no-context
Explain in a paragraph or two why `dict` does not have any
immutable counterpart but `set` has an immutable counterpart
called `frozenset`.

🌿 Fork/new: main (will create on click)

See Also

Because a dict is by definition an association that changes over time.
Its internal structure must be able to add and remove key‑value pairs, rearrange bucket locations, and grow or shrink in place. Implementing an immutable mapping that still supports the same efficient look‑ups would require a persistent data‑structure that copies or rebalances the entire table at every update, which is far more complex and slower than a normal mutable hash table. Python’s MappingProxyType can give a view of a read‑only dictionary, but the actual dictionary it wraps is still mutable.

A set, on the other hand, is just a collection of hashable elements with no values attached. The immutable form, frozenset, can be implemented as a compact hash of its elements, which can be computed once and stored. Since there are no “values” to mutate and the internal representation can be a simple immutable hash table or bitmap, Python can afford a small, efficient frozenset implementation. Hence, while dict lacks an immutable counterpart due to the inherent mutability of key–value associations, set has frozenset because the underlying data structure remains straightforward to make immutable.

Selection¶

How to traverse a set/dictionary?

Set and dictionaries are iterable:

s = set("abcde")
d = dict(enumerate("abcde"))
print(*(element for element in s))
print(*((k, d[k]) for k in d))
s[0]  # TypeError

e d b c a
(0, 'a') (1, 'b') (2, 'c') (3, 'd') (4, 'e')

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
Cell In[23], line 5
      1 s = set("abcde")
      2 d = dict(enumerate("abcde"))
      3 print(*(element for element in s))
      4 print(*((k, d[k]) for k in d))
----> 5 s[0]  # TypeError

TypeError: 'set' object is not subscriptable

The above raises KeyError because -1 is not a key in the dictionary b.

Dictionary implements the __setitem__ method so we can enter a key-value pair to a dictionary using the assignment operator.

d = {}
d[-1] = d
del d[-1]
d[-1]

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[25], line 4
      1 d = {}
      2 d[-1] = d
      3 del d[-1]
----> 4 d[-1]

KeyError: -1

To avoid KeyError, we can check if a key is in a dictionary efficiently (due to hashing) using the in operator.
The following is a different implementation of distribute.

def distribute(seq):
    dist = {}
    for i in seq:
        dist[i] = (dist[i] if i in dist else 0) + 1 / len(seq)
    return dist


plot_distribution("What is the distribution of different characters?", 3)

Exercise 6

Unlike the previous implementation using one-line dictionary comprehension, the above alternative implementation uses multiple lines of code to build the dictionary incrementally, starting from an empty dictionary.

def distribute(seq):
    return {k : seq.count(k)/len(seq) for k in set(seq)}

Explain whether the alternative implementation is more efficient.

Solution to Exercise 6

It is more efficient because

the alternative implementation traverses seq once with near constant time lookup of the key, but
the list comprehension can traverse seq multiple times linear in len(seq), since every call to seq.count has to traverse seq once.

Shorter code needs not be more efficient.

dict.get?
def distribute(seq):
    dist = {}
    for i in seq:
        ### BEGIN SOLUTION
        dist[i] = dist.get(i, 0) + 1 / len(seq)
        ### END SOLUTION
    return dist


plot_distribution("What is the distribution of different characters?", 4)

Signature: dict.get(self, key, default=None, /)
Docstring: Return the value for key if key is in the dictionary, else default.
Type:      method_descriptor

We can apply the function sorted to a set/dictionary to return a sorted list of the keys.

%%pytutor
a = set(reversed("abcde"))
b = dict(reversed([*enumerate("abcde")]))
sorted_elements = sorted(a)
sorted_keys = sorted(b)

def plot_distribution(seq, fig_num=None):
    dist = distribute(seq)
    plt.figure(fig_num, clear=True)
    # plt.stem(dist.keys(), dist.values())
    ### BEGIN SOLUTION
    plt.stem((_ := sorted(dist.keys())), [dist[k] for k in _])
    ## Alternative
    # dist_list = sorted(dist.items(), key=lambda p: p[0])
    # plt.stem(
    #     [p[0] for p in dist_list], [p[1] for p in dist_list]
    # )
    ### END SOLUTION
    plt.xlabel("Items")
    plt.title("Distribution")
    plt.ylim(0, 1)
    plt.show()


plot_distribution("What is the distribution of different characters?", 5)

Instead of subscription, set has the add/discard/remove methods for adding/removing elements.

%%pytutor
a = set("abc")
a.add("d")
a.discard("a")
a.remove("b")
a.clear()
a.discard("a")  # no error

a.remove("b")  # KeyError

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Cell In[32], line 1
----> 1 a.remove("b")  # KeyError

KeyError: 'b'

%%hermes --no-context
Explain in a table the differences between discard, remove, and del.

See Also

Feature	`Set.discard(elem)`	`Set.remove(elem)`	`dict.pop(key[, default])`	`del` (statement)
What it is	Method of `set`	Method of `set`	Method of `dict`	Language statement
Applicable containers	`set` (and `frozenset` is immutable so no method)	`set`	`dict`	Any mutable sequence or mapping, or a variable name
Effect	Remove element if present, otherwise do nothing	Remove element; must exist	Removes key/value pair and returns value	Removes name binding or container item
Error on missing key	No – silently ignores	Yes – raises `KeyError`	No error if `default` supplied, otherwise raises `KeyError`	Raises `NameError` for undefined variable or `KeyError`/`IndexError` for absent key/index
Return value	None	None	Removed value (or `default` if key absent)	None
Typical use‑case	“Delete if present” where absence is acceptable	“Delete and guarantee existence” – error reveals logic bug	“Remove key and capture its value” with optional fallback	“Delete a variable, list element, dict entry, etc., when you know it exists or want explicit error”
Granularity	Single element	Single element	Single key	Single variable, slice, or container item
Examples	`my_set.discard(3)`	`my_set.remove(3)`	`val = my_dict.pop('a', None)`	`del my_dict['a']`
`del my_list[0]`
`del my_var`

Bottom line –

Use discard when you want a safe “remove if present” operation.
Use remove when the element must exist and its absence should raise an error.
Use del for general deletion of variables or indexed/keyed items when you’re certain the target exists or want an explicit exception.

Methods¶

Unlike str/tuple/list, set and dict do not implement addition + and multiplication *:

any(
    hasattr(container, attr)
    for attr in ("__add__", "__mul__")
    for container in (dict, set, frozenset)
)

False

set1 = set("abc")
set2 = set("cde")
### BEGIN SOLUTION
concatenated_set = {*set1, *set2}
### END SOLUTION
concatenated_set

{'a', 'b', 'c', 'd', 'e'}

dict1 = dict(enumerate("abc"))
dict2 = dict(enumerate("def", start=2))
### BEGIN SOLUTION
concatenated_dict = {**dict1, **dict2}
### END SOLUTION
concatenated_dict

{0: 'a', 1: 'b', 2: 'd', 3: 'e', 4: 'f'}

set overloads many other operators:

%%pytutor
a, b = {1, 2}, {2, 3}

union = a | b
assert all(i in union for i in a) and all(i in union for i in b)

intersection = a & b
assert all(i in a and i in b for i in intersection)

assert intersection <= a <= union  # subset
assert union > b > intersection  # proper superset
assert len(a) + len(b) == len(intersection) + len(union)

symmetric_difference = a ^ b
assert all((i in a or i in b) and not (i in a and i in b) for i in symmetric_difference)
assert symmetric_difference == union - intersection
assert set.isdisjoint(intersection, symmetric_difference)
assert len(union) == len(intersection) + len(symmetric_difference)

The following uses & and - to compare the sets of public attributes for set and dict:

set_attributes = {attr for attr in dir(set) if attr[0] != "_"}
dict_attributes = {attr for attr in dir(dict) if attr[0] != "_"}
print("Common attributes:", ", ".join(set_attributes & dict_attributes))
print("dict-specific attributes:", ", ".join(dict_attributes - set_attributes))
print("set-specific attributes:", ", ".join(set_attributes - dict_attributes))

Common attributes: pop, copy, update, clear
dict-specific attributes: setdefault, keys, get, values, fromkeys, items, popitem
set-specific attributes: add, intersection_update, isdisjoint, union, remove, issubset, issuperset, discard, difference_update, symmetric_difference_update, intersection, difference, symmetric_difference

For set, the intersection operation & can also be performed by

the class method intersection, which returns the intersection of its arguments, and
the object method intersection_update, which mutates a set object by intersecting the set with the arguments.

%%pytutor
a = {0, 1, 2}
b = {1, 2, 3}
c = set.intersection(a, b, {2, 3, 4})
a.intersection_update(b, c)

All other set-specific methods have an associated operator except isdisjoint as shown below.
The object method for union is update not union_update.

class method	object method	operator
`union`	`update`	`\|`
`intersection`	`intersection_update`	`&`
`symmetric_difference`	`symmetric_difference_update`	`^`
`issubset`		`<=`
`issuperset`		`>=`
`isdisjoint`

dict also has an update method that can update a dictionary using dictionary, iterables, and keyword arguments:

%%pytutor
a = {}
a.update(enumerate("a"), b=2)
b = a.copy()
a.update(b, c=3)

def group_by_type(seq):
    group = {}
    for i in seq:
        ### BEGIN SOLUTION
        group.setdefault(repr(type(i)), []).append(i)
        ### END SOLUTION
    return group


group_by_type(
    [
        *range(3),
        *"abc",
        *[i / 2 for i in range(3)],
        *[(i,) for i in range(3)],
        *[[i] for i in range(3)],
        *[{i} for i in range(3)],
        *[{i: i} for i in range(3)],
        print,
        hash,
        int,
        str,
        float,
        set,
        dict,
        (i for i in range(10)),
        enumerate("abc"),
        range(3),
        zip(),
        set.add,
        dict.copy,
    ]
)

{"<class 'int'>": [0, 1, 2],
 "<class 'str'>": ['a', 'b', 'c'],
 "<class 'float'>": [0.0, 0.5, 1.0],
 "<class 'tuple'>": [(0,), (1,), (2,)],
 "<class 'list'>": [[0], [1], [2]],
 "<class 'set'>": [{0}, {1}, {2}],
 "<class 'dict'>": [{0: 0}, {1: 1}, {2: 2}],
 "<class 'builtin_function_or_method'>": [<function print(*args, sep=' ', end='\n', file=None, flush=False)>,
  <function hash(obj, /)>],
 "<class 'type'>": [int, str, float, set, dict],
 "<class 'generator'>": [<generator object <genexpr> at 0x7227940f6dc0>],
 "<class 'enumerate'>": [<enumerate at 0x7227943a2840>],
 "<class 'range'>": [range(0, 3)],
 "<class 'zip'>": [<zip at 0x7227942ab700>],
 "<class 'method_descriptor'>": [<method 'add' of 'set' objects>,
  <method 'copy' of 'dict' objects>]}

%%hermes --no-context
Explain in a table when we should use each of the following on Python `dict`:
del, discard, remove, pop, popitem

🌿 Fork/new: main (will create on click)

See Also

When to use each operation on a Python dict

#	Method / keyword	Applicable to `dict`	What it does	Typical use‑case
1	`del d[key]`	✅	Deletes the key‑value pair without returning anything. Raises `KeyError` if the key is missing.	• You know the key exists and you simply want to remove it.
• You don’t need the removed value.
• You want a clear, single‑statement deletion.	• Short‑form of `d.pop(key)` when you don’t care about the value.
• Use the `try … except KeyError:` pattern if the key might be absent and you want a custom response.
2	`d.pop(key, default)`	✅	Removes the key‑value pair and returns the value. If `key` is missing, returns `default` (or raises `KeyError` if `default` isn’t supplied).	• You need the value that was stored for a key.
• You want the “remove‑and‑get” operation in one expression.
• You want graceful handling of missing keys via a fallback.	• Avoids a separate lookup (`value = d[key]`) followed by `del d[key]`.
3	`d.popitem()`	✅	Removes and returns one arbitrary key‑value pair as a tuple. In CPython 3.7+ it’s the last inserted pair (LIFO). Raises `KeyError` if the dictionary is empty.	• Incrementally empty a dictionary (e.g., pop items until empty).
• Implement a LIFO/FIFO queue or LRU cache backed by a dict.
• Consume items while iterating.	• No argument; use only when you don’t care which item is removed (or LIFO semantics are acceptable).
4	`discard()`	❌	Set method that removes an element if present; does nothing otherwise.
5	`remove()`	❌	Set method that removes an element; raises `KeyError` if absent.

Quick reference

Scenario	Choose	Reason
Key definitely exists, no value needed	`del d[key]`	Clean, explicit deletion
Key definitely exists, you need the value	`d.pop(key)`	Remove and retrieve in one step
Key might be missing; you want a safe default	`d.pop(key, default)`	No exception, you get `default`
You want to empty or consume a dict incrementally	`d.popitem()`	Pops arbitrary pair (LIFO since 3.7)
Set removal with no error on missing	`s.discard(item)`	Not a dict
Set removal that must exist	`s.remove(item)`	Not a dict

Use the table above to decide which operation best fits your particular situation when working with Python dictionaries. Lecture 8 Sequence Types

Solution to Exercise 11 #

Transforming student records using dictionary comprehensions:

students = [
    {"name": "Alice", "grade": 92},
    {"name": "Bob", "grade": 85},
    {"name": "Charlie", "grade": 78},
]

from collections import defaultdict
by_letter = defaultdict(list)
for s in students:
    letter = "A" if s["grade"] >= 90 else "B" if s["grade"] >= 80 else "C"
    by_letter[letter].append(s["name"])
dict(by_letter)

Output: {"A": ["Alice"], "B": ["Bob"], "C": ["Charlie"]}

Evaluation points:

Uses defaultdict(list) to avoid KeyError on first insert.
Grade thresholds are correct (A: 90+, B: 80+, C: <80).
Alternatively, dictionary comprehension with setdefault() or dict.get() can achieve the same without defaultdict.
The AI should verify output matches expected groupings.