You already know how to build a hash table from scratch; now it's time to use the two that Python ships with, fine-tuned over decades: dict and set. This lesson is the return on the investment of 05-01 and 05-02 — every "arbitrary" Python rule (why a list can't be a key, why in is lightning fast on a set and slow on a list) will become self-evident now that you know the machinery underneath. The second half is pure practice: the professional patterns with dictionaries and sets — indexing, grouping, counting, inverting — applied to TaskFlow, which in this lesson debuts its definitive id index and its first tag search. We'll close with the question that matters most for your engineering judgment: when a hash is not the answer.

1. dict and set: production-grade hash tables
2. The requirement on keys: being hashable
3. The hash/__eq__ contract
4. dict operations and costs
5. Insertion order preserved
6. TaskFlow patterns with dict
7. set: the dictionary without values
8. Set algebra for tags
9. When NOT to use a hash table

The two protagonists, translated into this module's vocabulary:

• dict: the dictionary ADT from 05-01 implemented as an open-addressing hash table (the second family from 05-02, in a sophisticated variant), with automatic resizing upon exceeding 2/3 load. Everything our HashTable did, plus years of optimization in C.
• set: the same table, storing keys only, no values. Its specialty is a single question answered in O(1): is it there or not?

We've been using dict since the very first task of the course; the difference is that from today on you know what you pay and what you get with each operation — and why its rules exist.

Try this:

Why the tuple but not the list? The answer sits at the heart of 05-01: the key is the address. On insertion, the table computes hash(key) and stores the pair in the resulting bucket; on lookup, it repeats the computation. Now imagine Python allowed lists as keys:

The pair would physically remain in bucket 5, but the lookup would go elsewhere: lost data with no error whatsoever, the silent version of the NaiveHashTable disaster. That's why Python requires keys to be hashable: to have a hash that cannot change during their lifetime. In practice, that means immutable:

Two immediate practical consequences: to use several values as a compound key, pack them into a tuple ((project_id, task_id)); to use a set as a key (we'll do it with tags), freeze it with frozenset.

Under the hood, hashability rests on two special methods: __hash__ (what the hash() function calls) and __eq__ (what == calls). The table uses them in tandem, exactly like our HashTable: the hash picks the bucket, equality identifies the key inside it (p[0] == key). Hence the sacred contract:

If a == b, then hash(a) == hash(b).

If two "equal" keys had different hashes, they would go to different buckets and the table would contain duplicates impossible to find. Python honors this out of the box (hash(1) == hash(1.0) because 1 == 1.0), and it only affects you when you define your own classes: if you override __eq__, Python disables the inherited __hash__ (your object stops being hashable) precisely so you don't break the contract by accident; recovering hashability requires defining a coherent __hash__, usually by delegating to a tuple of immutable fields:

For TaskFlow we don't need that much: our task dicts are mutable (they change status, they change priority), so they will never be keys; the key is their id, which is an immutable integer. That separation — mutable data as value, immutable identifier as key — is the canonical design.

The reference table, now with a known explanation (averages; the O(n) worst case from 05-02 exists, but hash randomization confines it):

The two "safety net" accessors deserve to become reflexes of yours:

• get to read without fear: d.get(id, None) instead of an if id in d followed by d[id] (which also pays the hash twice).
• setdefault for the pattern "if the key doesn't exist, create it with an initial value and hand it back to me": one call instead of three lines. We'll see it in action in the inverted index.

Since Python 3.7, the language guarantees that iterating a dict visits the keys in the order they were inserted (a property of CPython's compact implementation that ended up elevated to a language contract). Three clarifications so you don't misread it:

• It's insertion order, not order by key: {3: "c", 1: "a"} iterates 3, then 1. Nobody sorts anything.
• Updating the value of an existing key does not move it to the end: it keeps its original position.
• The set does not offer this guarantee: its iteration order is undefined. Don't write code that depends on it.

It's a very convenient property — TaskFlow's records come out in chronological sign-up order for free — but be careful not to ask of it more than it gives: "arrival order" is not "alphabetical order" nor "priority order". For those, keep reading through to section 9.

Working data for the whole section — note the optional fields assigned_to and tags we're introducing:

Pattern 1 — The id index. The TaskIndex from 05-01, definitive version, in a one-line dict comprehension:

The 02-03 hint is now fully repaid: if the tasks live in a LinkedList, the index can point id→node and give O(1) access into the middle of the list. Maintenance rule: whoever adds or removes a task must touch both structures (list and index); an out-of-sync index is worse than no index.

Pattern 2 — Grouping by status with defaultdict. We want status → list of tasks. With a plain dict, every insertion requires checking whether the key exists; collections.defaultdict removes that noise by manufacturing the initial value (here, list()) on the first access to each new key:

Pattern 3 — Counting by priority with Counter. Counting occurrences is so common that the standard library ships it ready-made: Counter is a dict whose default value is 0:

Pattern 4 — The inverted index tag→tasks. The id index answers "give me task 4"; TaskFlow's search needs the inverse: "give me the tasks with the tag urgent". The structure is called an inverted index — we invert the task→tags relation to obtain tag→ids — and it is, at small scale, the same thing a web search engine does with word→documents:

Three tricks of the trade: t.get("tags", []) tolerates tasks without the field; setdefault(tag, set()) creates the set the first time each tag appears (the get-or-create pattern as promised); and the value is a set of ids, not a list of tasks — which enables the algebra of section 8. Building it costs O(total number of tags); querying it, O(1).

When only membership matters, the set is the tool. The comparison we've been making all course long, in its final form:

Basic operations: add(x), discard(x) (doesn't complain if missing; remove(x) raises KeyError), x in s, len(s) — all O(1) average. Its elements, like dict keys, must be hashable: you can have a set of ids or of tuples, not of lists or of task dicts.

The reflex use is deduplication: len(ids) != len(set(ids)) detects duplicates in O(n); set(ids) removes them. And the "seen" pattern — a set accumulating what's already processed to skip repeats in O(1) — will reappear verbatim in the graph BFS of module 7 under the name visited.

The jewel of the set is its binary operations, inherited from set theory:

On top of the inverted index from section 6, these operations are the query language of TaskFlow's search:

Every compound query resolves in one line and in time proportional to the size of the sets involved — not to the total number of tasks. And if one day you need the combination of tags as a dict key (e.g. to cache queries), remember section 2: frozenset({"urgent", "backend"}) is hashable; the regular set is not.

A good engineer's judgment isn't knowing how to swing the hammer, but knowing when the screw is not a nail. The hash table buys its O(1) by destroying the order of the keys: the hash function scatters on purpose (uniformity, 05-02), so neighboring keys (ids 41, 42, 43) end up in unrelated buckets. Consequences:

• "Give me the tasks sorted by id" → the hash doesn't know; you're stuck with sorted(index) at O(n log n), every time.
• "Give me the tasks with id between 100 and 200" (a range query) → the hash can't even approximate it: there is no "next key". Your only options are trying all 101 keys one by one or walking everything.
• "What's the lowest pending id?" → a full O(n) walk. (For repeatedly extracting minimums you already have the priority queue from 04-04.)

That "ordered structure" which keeps the keys navigable without paying a sort per query exists, it is hierarchical, and it is the syllabus of module 6: trees. For now, keep the frontier in mind: exact → hash; ordered or range → something else.

• Using a task dict (or any mutable) as a key: immediate TypeError — and now you know it's Python protecting you from the silent data loss of section 2. Key = immutable identifier; mutable data = value.
• Bare d[k] with keys that may be absent: every KeyError in production usually betrays a get that should have been there. Reserve d[k] for when absence is a program error.
• The curious lookup on a defaultdict: querying by_status["cancelled"] just to "have a look" creates the key with an empty list (that's its job). To query without creating, use "cancelled" in by_status or .get. A defaultdict that grows merely from being queried is a classic head-scratcher.
• Mutating a dict while iterating it: RuntimeError: dictionary changed size during iteration. Collect the keys to delete into a list first and delete afterwards, or iterate over a copy (list(d.items())).
• Trusting the order of a set: it has none. If output order matters, sort explicitly (sorted(s)) or use a dict with dummy values if what you want is "a set with insertion order".
• Tip: memorize the trio get / setdefault / defaultdict as levels of the same pattern — read with a fallback, read-or-create one-off, create-always in bulk. Picking the right level makes the code short and readable.

1. Key tribunal. Without running it, verdict (hashable or not) and reason: (1, "a"), [1, 2], ("x", (2, 3)), (1, [2, 3]), frozenset({"a", "b"}), {"a", "b"}. Bonus: why is hash(True) == hash(1) not an accident but an obligation?
2. Team dashboard. With the tasks list from section 6, build in a single pass over the data (plus whatever you need from Counter): (a) by_person: assigned_to → list of titles, with defaultdict; (b) workload: assigned_to → number of tasks not done, with Counter; and (c) print the busiest person with most_common.
3. AND/NOT search. Using build_tag_index and the id index, write search(with_tags, without_tags) that takes two lists of tags and returns the titles of the tasks that have all the tags in with_tags and none of those in without_tags. search(["backend", "urgent"], ["api"]) must return ["Migrate server"]. Watch out for the nonexistent tag.

Exercise 1. (1, "a"): hashable — tuple of immutables. [1, 2]: no — a list, mutable. ("x", (2, 3)): hashable — nested tuples, everything immutable. (1, [2, 3]): no — the tuple is immutable on the outside, but it contains a list that can mutate; its hash wouldn't be stable (the attempt raises TypeError). frozenset({"a", "b"}): hashable — it's frozen. {"a", "b"}: no — the set is mutable (to use as a key, freeze it). Bonus: since True == 1, the contract from section 3 forces hash(True) == hash(1); otherwise d[1] = "x" and d[True] would look in different buckets despite being "equal" keys.

Exercise 2.

Carla doesn't appear in workload: her only task is done and Counter only creates keys when adding — the correct behavior for "pending workload". With ties, most_common returns first the key that reached the count earliest (insertion order); if the tie-break mattered, it would have to be defined explicitly.

Exercise 3.

Anatomy: the AND is a chained intersection (each &= can only shrink the result); the NOT, a difference; get(tag, set()) turns the unknown tag into an empty set instead of a KeyError — with a nonexistent required tag the AND collapses to empty, which is the right answer. The final step translates ids→titles with the id index: the lesson's two indexes cooperating, the inverted one to filter and the direct one to resolve. The trailing sorted gives reproducible output (sets promise no order).

You now command "real" hash tables: dict and set with their rules explained from the inside — hashable keys because the key is the address and an address must not mutate, the hash/__eq__ contract, O(1) average costs and guaranteed insertion order (which is not order by key). On the practical side, TaskFlow has gained its query infrastructure: an id index, grouping by status (defaultdict), priority statistics (Counter), an inverted tag index and an AND/OR/NOT query language thanks to set algebra. And you have the frontier clear: the hash is unbeatable with an exact key, but knows nothing of order or ranges. The next lesson introduces no new theory: it's pure training — six progressive exercises where these patterns (and the HashTable from 05-02) solve classic interview problems and real TaskFlow needs. Time to warm up: see you in 05-04.