06. Hashing — dict, set, Counter

What you'll learn

• 1Use dict for O(1) key/value lookup
• 2Use set for O(1) membership and dedup
• 3Use defaultdict and Counter for clean code

Overview

If your solution has a nested loop that re-scans a list, you can usually replace the inner scan with a hash lookup and drop a factor of N. This is the most common O(n²) → O(n) optimization.

Core Concepts

1. dict basics

scores = {'alice': 90, 'bob': 82}
scores['alice']        # 90
scores['carol'] = 78   # insert
'alice' in scores      # True (O(1))
scores.get('dave', 0)  # default if missing — never raises
del scores['bob']
for k, v in scores.items(): ...   # iterate pairs

2. set

seen = set()
seen.add(3)
5 in seen        # O(1)
A, B = {1,2,3}, {2,3,4}
A | B            # union     {1,2,3,4}
A & B            # intersect {2,3}
A - B            # difference {1}
A ^ B            # symmetric diff {1,4}

3. defaultdict — no KeyError

from collections import defaultdict

# Group items
groups = defaultdict(list)
for word in words:
    groups[len(word)].append(word)

# Count items
count = defaultdict(int)
for c in 'banana':
    count[c] += 1

4. Counter — built-in counting

from collections import Counter
c = Counter('banana')
c.most_common(2)        # [('a', 3), ('n', 2)]
c['a']                  # 3
c['z']                  # 0 (no KeyError)

# Counter algebra
Counter('aab') + Counter('abc')   # {'a':3, 'b':2, 'c':1}

Examples

Example 1 — src/01_dict_basics.py

CRUD on a dict + iteration patterns.

Example 2 — src/02_set_dedup.py

Deduplicate a list with set() and preserve original order with dict.fromkeys.

Example 3 — src/03_two_sum.py

The classic two-sum problem reduced from O(n²) to O(n) using a dict.

Example 4 — src/04_counter.py

Word/character frequency with collections.Counter.

Common Mistakes

1. Using `if k in dict.keys():` — that's still O(n) on some Python versions. Just write `if k in dict:`.
2. Using a list when you mean a set. `if x in [1,2,3,...big...]:` is O(n).
3. Forgetting unhashable types: list and dict can't be dict keys. Use tuple instead.
4. Mutating a dict while iterating it. Iterate over list(d) or d.copy() instead.

Recap

• dict / set are your default tools for O(1) lookup.
• defaultdict and Counter eliminate boilerplate.
• Hashing-based optimization is the most common O(n²) → O(n) trick.

Try It

1. BOJ 1764 (Listen & See) — set intersection.
2. BOJ 1620 (Pokémon Master) — bidirectional dict.