Key-value thinking

A list is an ordered sequence. To find something in a list, you scan from the start — O(n). A dict (also called a hash map or hash table) is a different data structure that maps keys to values with effectively O(1) lookup: the time to find a key doesn't grow with the number of entries.

Why dict lookup is O(1)

When you write d["alice"] = 42, Python doesn't store the entry at the end of a list to be scanned later. It runs a hash function on "alice" to produce a number, uses that number to compute a storage slot, and puts the value there. When you later ask for d["alice"], it hashes "alice" again, goes straight to the same slot, and reads the value. One hop, regardless of how many keys are in the dict.

The detail that matters for problem-solving: if you find yourself scanning a list repeatedly for the same information, a dict can often reduce that to a single scan that builds the dict, followed by O(1) lookups.

Pattern 1: Count with a dict

Problem. Given a list of words, how many times does each word appear?

Brute force: for each unique word, scan the whole list and count — O(n²). With a dict: make a single pass, incrementing a counter for each word — O(n).

words = ["cat", "dog", "cat", "bird", "dog", "cat"]
counts = {}
for word in words:
    if word in counts:
        counts[word] += 1
    else:
        counts[word] = 1
# counts == {"cat": 3, "dog": 2, "bird": 1}

The dict key is the thing you're counting; the value is the count. You'll use this pattern constantly.

Pattern 2: Group with a dict

Problem. Given a list of words, group them by their length.

One pass: for each word, use its length as the key and append to a list of words at that key.

words = ["cat", "dog", "elephant", "ant", "bee", "ox"]
by_length = {}
for word in words:
    length = len(word)
    if length not in by_length:
        by_length[length] = []
    by_length[length].append(word)
# by_length == {3: ["cat", "dog", "ant", "bee"], 8: ["elephant"], 2: ["ox"]}

The dict key is the grouping criterion; the value is a list of items in that group. You can use any hashable value as a key — lengths, first letters, categories, whatever makes the grouping meaningful.

When to reach for a dict

The mental trigger: "I'm scanning a list more than once for the same thing."

If you scan once to build a set of values and then check membership repeatedly, convert it to a set (O(1) membership test, like a dict without values). If you need to store associated data, use a dict. Either way you're trading memory — the dict or set uses space proportional to the input — for speed.

Where to go next

Next: solving with dicts — implementing the count and group patterns in Python, plus the classic "two sum" problem that shows exactly when O(n) beats O(n²).