Unit 6 · Intro to Programming

Dictionaries & Sets

Lists answer "what is at position 3?". Dictionaries answer "what is associated with this key?" — and they answer it in roughly constant time no matter how large they get. The calendar calls them maps. Once you have them, a whole class of slow list-scanning code disappears.

By the end you can

Build, read and update a dictionary safely.
Use the counting and grouping patterns from memory.
Say which objects can be keys, and why.
Choose between a list, a set and a dictionary deliberately.

Why it matters & where it comes from

Why it exists

Searching a list for a value means looking at every item. A dictionary jumps straight to the answer by computing where it must be. That difference is $O(n)$ versus $O(1)$, and on real data it is the difference between instant and unusable.

In the real world

Every database index, every cache, every word-frequency count is a hash table. Python's own namespaces are dictionaries — when you write x = 5, an entry goes into one.

Story & open questions

Hash tables date to 1953 at IBM. Since Python 3.7 dictionaries preserve insertion order, which was originally an implementation accident in 3.6 that proved so useful it was written into the language specification.

Dictionaries

Definition

A dictionary maps keys to values, written {'a': 1, 'b': 2}. Keys are unique; assigning to an existing key replaces its value. Lookup is d[key].

Example The core operations

python

ages = {'ada': 36, 'alan': 41}

ages['ada']            # 36
ages['grace'] = 45     # adds a new pair
ages['ada'] = 37       # replaces the existing value
'alan' in ages         # True  - tests KEYS, not values
len(ages)              # 3
del ages['alan']       # removes the pair

ages.keys()            # the keys
ages.values()          # the values
ages.items()           # (key, value) pairs

A missing key raises

ages['nobody'] is a KeyError. Three ways to avoid it:

if k in d: before reading — clearest when you need a branch anyway.

d.get(k) returns None when absent, or d.get(k, 0) to supply your own default.

d.setdefault(k, []) inserts the default and returns it, which is the grouping idiom below.

Example Iterating

python

for name in ages:                 # iterates KEYS by default
    print(name, ages[name])

for name, age in ages.items():    # cleaner when you need both
    print(name, age)

Iterating a dictionary gives keys, not pairs. Reaching for .items() when you want both is the idiom.

The two patterns worth memorising

Example Counting

python

def count_chars(s: str) -> dict:
    """Return a dictionary mapping each character of s to its count.

    >>> count_chars('aab')
    {'a': 2, 'b': 1}
    """
    counts = {}
    for ch in s:
        counts[ch] = counts.get(ch, 0) + 1
    return counts

get(ch, 0) supplies zero the first time a character appears, so the same line handles both the new and the repeat case. Without it you need an if.

Example Grouping

python

def group_by_length(words: list) -> dict:
    """Return a dictionary mapping each length to the words of that length.

    >>> group_by_length(['at', 'to', 'cat'])
    {2: ['at', 'to'], 3: ['cat']}
    """
    groups = {}
    for w in words:
        groups.setdefault(len(w), []).append(w)
    return groups

setdefault returns the list already stored, or inserts a new empty one and returns that. Either way there is a list to append to.

Example Inverting

python

def invert(d: dict) -> dict:
    """Return a dictionary with keys and values swapped.

    >>> invert({'a': 1, 'b': 2}) == {1: 'a', 2: 'b'}
    True
    """
    return {v: k for k, v in d.items()}

Only safe when the values are unique and hashable. Duplicate values collapse, keeping whichever came last.

What can be a key

Rule Keys must be hashable

A key must be immutable: int, float, str, bool, and tuples of those. Lists and dictionaries cannot be keys.

The reason is direct. A dictionary places a key by computing a number from its contents. If the contents could change afterwards, the key would be filed in a location that no longer matches and would become unfindable.

Example Tuples work, lists do not

python

grid = {}
grid[(0, 0)] = 'start'      # fine - tuples are immutable
grid[[0, 0]] = 'start'      # TypeError: unhashable type: 'list'

Using coordinate tuples as keys is the standard way to represent a sparse grid without allocating every cell.

Sets

Definition

A set is an unordered collection of unique hashable values, written {1, 2, 3}. Think of it as a dictionary with keys and no values. The empty set is set(), since {} is an empty dictionary.

Example Membership and algebra

python

a = {1, 2, 3}
b = {3, 4}

3 in a          # True - fast, unlike a list scan
a | b           # {1, 2, 3, 4}  union
a & b           # {3}           intersection
a - b           # {1, 2}        difference

set([1, 1, 2])  # {1, 2} - deduplication in one step
sorted(set(xs)) # unique values, back in order

Rule Choosing the structure

Order matters, duplicates allowed, index by position → list.

Only membership and uniqueness matter → set.

Each item carries associated data → dictionary.

The Unit 5 dedupe function scanned a growing list for every item, which is quadratic. Tracking seen items in a set makes it linear, and that is the whole reason to reach for one.

Common pitfalls

• {} is an empty dictionary, not an empty set. Use set().
• Using a list as a key. Convert to a tuple first.
• Assuming in on a dictionary checks values. It checks keys.
• Relying on set order. Sets have none, so sorted() whenever output order matters.
• Changing a dictionary's size while iterating it. Iterate over list(d.keys()) if you must delete during the loop.

Practice

Predict each answer before running it. Original exercises written for this guide in the style of the course's weekly sets.

Practice 1 · Key or value?

For d = {'a': 1}, what are 'a' in d and 1 in d?

Answer

True and False. Membership tests keys. Use 1 in d.values() for the other question.

Practice 2 · Counting

Count word frequencies in a sentence.

Solution

python

def word_counts(text: str) -> dict:
    """Return a dictionary mapping each word of text to its count.

    >>> word_counts('a b a')
    {'a': 2, 'b': 1}
    """
    counts = {}
    for w in text.split():
        counts[w] = counts.get(w, 0) + 1
    return counts

Practice 3 · Empty set

What type is {}?

Answer

dict. The empty set has to be written set(), because the brace notation was taken by dictionaries first.

Practice 4 · Faster dedupe

Rewrite Unit 5's dedupe using a set, keeping order.

Solution

python

def dedupe(xs: list) -> list:
    """Return a new list with duplicates removed, order preserved.

    >>> dedupe([1, 2, 1, 3])
    [1, 2, 3]
    """
    seen = set()
    out = []
    for x in xs:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

The set makes each membership test constant time instead of a scan, so the whole function goes from quadratic to linear.

Practice 5 · Unhashable

Why does d[[1, 2]] = 'x' fail?

Answer

Lists are mutable, so their hash could change after insertion and the entry would become unfindable. Python forbids it outright. Use a tuple.

Practice 6 · Max by value

Find the key with the largest value in a non-empty dictionary.

Solution

python

def top_key(d: dict) -> str:
    """Return a key of d whose value is largest.

    >>> top_key({'a': 1, 'b': 5})
    'b'
    """
    best = None
    for k, v in d.items():
        if best is None or v > d[best]:
            best = k
    return best

Ties resolve to whichever came first. Say so in the docstring if it matters.

Practice 7 · Set algebra

Find words appearing in both of two sentences.

Solution

set(a.split()) & set(b.split()). Intersection expresses it directly; a nested loop would be quadratic and less readable.

Practice 8 · Grouping by first letter

Group words by their first letter.

Solution

python

def by_letter(words: list) -> dict:
    """Return a dictionary mapping first letters to the words starting
    with them.

    >>> by_letter(['ant', 'ape', 'bee'])
    {'a': ['ant', 'ape'], 'b': ['bee']}
    """
    groups = {}
    for w in words:
        groups.setdefault(w[0], []).append(w)
    return groups

An empty string in the input would raise on w[0]; guard it or document that words are non-empty.

Expanded topic checklist

Course coverage. This unit is part of the complete CSC108H1 topic map. It should cover the following items before you move on:

Dictionaries. Create, read, update, delete; keys, values, items.
Safe access. in, get with a default, setdefault.
Patterns. Counting, grouping, inverting.
Sets. Uniqueness, membership, the algebra operations, and choosing between the three structures.

Textbook/source alignment

The calendar names "maps" among the elementary data types. Dictionary patterns are heavily assessed on assignments; check the syllabus on Quercus for the assigned exercises.

Core idea map

A dictionary trades memory for speed by computing where a key belongs rather than searching for it. Unit 9 makes that trade explicit as $O(1)$ versus $O(n)$.

Study routine. Whenever you write x in some_list inside a loop, stop and ask whether a set belongs there. It is the single most common speed fix in the course.

Deep practice extensions

Use these after the main practice set. They push on definitions and edge cases rather than routine calculation.

Extension 1 · Missing key

What happens on d['absent']?

Guide

A KeyError. Use d.get('absent', default) to avoid it.

Extension 2 · Key requirements

Why must keys be immutable?

Guide

Because the key's contents determine where it is stored. If they changed, the entry could never be found again.

Extension 3 · Structure choice

When is a set the right structure?

Guide

When you only care whether something is present and want no duplicates, and order does not matter.

Extension 4 · Iteration default

What does for x in d give?

Guide

The keys. Use d.items() for pairs, d.values() for values.

← Unit 05Lists & aliasing Unit 07 →Classes, objects & methods