The workhorses
Python's dict is a production-grade hash table, and a set is the same machine storing keys with no values. Both give amortized O(1) for insert, lookup, and delete. What that means daily:
key in dandx in sare O(1). Comparex in some_list: O(n).- Counting, grouping, and de-duplicating all become one-pass jobs.
One rule follows from how the machine works: keys must be hashable, and every built-in immutable type is (strings, numbers, tuples of immutables). Mutable objects like lists can't be keys: if a key changed after being filed, its hash would point at the wrong bucket forever. This is the payoff of string immutability from lesson 3-1.
The tally pattern from lesson 3-2 is the single most common dict idiom:
Code exercise · python
Run this vote counter: one O(n) pass to tally, then max with key=tally.get finds the winner, and set(votes) de-duplicates the options. (We sort the set before printing because sets have no reliable order.)
Turning O(n²) into O(n): two sum
The classic interview question: given a list of numbers and a target, return the indexes of two numbers that add up to the target.
Brute force checks every pair: the nested loop from lesson 1-2, O(n²).
The hash-table insight, the same scan-to-lookup move as lesson 3-2: walk the list once, and for each number x ask "have I already seen target − x?". That question is a dict lookup, O(1). Keep a dict mapping each seen number → its index.
One pass, one dict: O(n). This exact transformation (replace an inner search loop with a hash lookup) is the most reusable optimization in this whole course.
Code exercise · python
Your turn: implement `two_sum` in one pass with a `seen` dict mapping number -> index. For each number x at index i, if target - x is in seen, return [seen[target - x], i]. Otherwise record seen[x] = i. Return [] if no pair exists.
Quiz
Why can a list not be a dict key?
Grouping by a computed key
Counting and two-sum both mapped a key to one value. The third everyday dict idiom maps a key to a group: SQL's GROUP BY, log lines grouped by user, files grouped by extension — all the same move.
The mechanism: pick a canonical key, a value that every member of a group computes identically and non-members do not. Then one pass with groups.setdefault(key, []).append(item) files everything, O(1) per item.
Worked example: group a word list into anagram families. The canonical key for an anagram group is the word's letters in sorted order — "listen", "silent", and "enlist" all sort to "eilnst", so all three land under the same dict key. (Note the key is a string built with "".join(...): a sorted list of letters could not be a key, because lists are not hashable.)
Code exercise · python
Your turn: implement `group_anagrams(words)`. For each word, compute the canonical key `"".join(sorted(word))` and append the word to that key's list with setdefault. The printing loop is done for you.