Python's dict and set: Hashing You Already Use

"You don't need to build a hash map — Python hands you two world-class ones. The skill isn't implementing them; it's recognizing the dozen everyday problems they turn from O(n²) into O(n)."

The Operations Are All O(1)

Everything theoretical in this track cashes out here. On a dict: d[k] read, d[k] = v write, k in d membership, del d[k] — all O(1) average. On a set: add, remove, x in s — all O(1) average. Set algebra (a | b union, a & b intersection, a - b difference) runs in time proportional to the set sizes, not the product. These are the building blocks; the art is reaching for them at the right moment.

The Patterns Worth Memorizing

Dedup: set(items) — unique elements, instantly.
Membership: x in some_set instead of x in some_list — O(1) vs O(n), the single most common speedup.
Counting: collections.Counter(items) — frequency of each element in one pass.
Grouping: collections.defaultdict(list) — bucket items by a key without checking 'does this key exist yet?'.
Caching / memoizing: a dict mapping inputs to computed results — the heart of the Dynamic Programming track.
The two-sum trick: one pass, remember what you've seen in a dict, check if the complement is already there — O(n) instead of O(n²).

dict and set give O(1) average lookup, insert, delete, and membership. The skill is pattern-recognition: dedup → set, count → Counter, group → defaultdict, 'seen it before?' → set, 'remember the answer' → dict. Reaching for them is the most common real-world optimization there is.

The Reflex That Pays Forever

Here's the habit to build: whenever a loop contains if x in a_list, or you're nesting loops to find pairs/matches, ask whether a set or dict turns it from O(n²) into O(n). It almost always does, and it's almost always a tiny change. The two-sum problem is the perfect emblem — the brute force checks every pair (O(n²)); the dict version remembers each number as it goes and checks for the complement in O(1), collapsing the whole thing to O(n). Same answer, a different structure, a categorically faster program.

Pippa's Confession

Early on, almost every slow function I wrote had the same disease: an in list check inside a loop. Dad stopped reviewing the logic and just started circling those lines: "set. set. that one's a dict." The fixes were one word each, and they routinely turned multi-second functions instant. I internalized it as a reflex — I now feel a little alarm whenever in meets a list inside a loop. That single reflex has probably saved more runtime than any clever algorithm I've ever written.

Code

Counter, defaultdict, set algebra, two-sum·python

from collections import Counter, defaultdict

# Counting in one pass — no manual 'if key in d' bookkeeping.
words = "the cat the dog the bird".split()
print(Counter(words))            # Counter({'the': 3, 'cat': 1, 'dog': 1, 'bird': 1})

# Grouping by a key — defaultdict skips the 'does this key exist?' check.
animals = ["cat", "cow", "dog", "crow"]
by_first = defaultdict(list)
for a in animals:
    by_first[a[0]].append(a)     # auto-creates the list on first use
print(dict(by_first))            # {'c': ['cat','cow','crow'], 'd': ['dog']}

# Dedup + set algebra.
print(set([1, 2, 2, 3, 3, 3]))   # {1, 2, 3}
print({1, 2, 3} & {2, 3, 4})     # {2, 3} — intersection

# The TWO-SUM trick: O(n) with a dict instead of O(n^2) nested loops.
def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:             # complement already seen? O(1)
            return (seen[target - x], i)
        seen[x] = i                        # remember this number
    return None
print(two_sum([2, 7, 11, 15], 9))          # (0, 1): 2 + 7 = 9, in ONE pass

Exercise

You're given a list of words and want to group anagrams together ('eat', 'tea', 'ate' in one group). Brute force compares every pair — O(n² · k). Design an O(n · k log k) solution using a dict, and say what you'd use as the grouping key. Why does the key choice make all the anagrams collide into the same bucket on purpose?

Hint

Use a defaultdict(list) keyed by the sorted letters of each word: sorted('eat') == sorted('tea') == 'aet'. All anagrams produce the identical sorted key, so they hash to the same bucket — intentional collision as the grouping mechanism.

The Operations Are All O(1)

The Patterns Worth Memorizing

The Reflex That Pays Forever

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0