Arrays and hash maps

Why it matters

Most real programs are built on two structures: an ordered sequence (an array, which Python calls a list) and a key-value lookup table (a hash mapA key-value table that hashes each key to choose a slot, giving average O(1) lookup, insert and delete; Python's dict., which Python calls a dict; a set is a hash map with keys only). Choosing the right one is often the whole difference between a solution that takes a second and one that takes an hour. Counting, grouping, de-duplicating and "have I seen this before?" are all hash map problems.

Arrays (Python lists)

A list stores items one after another, so the computer can jump straight to any position.

Lists are great when order matters and you access by position or add at the end. They are slow when you search by value or change the front.

Hash maps (Python dicts and sets)

A hash map runs each key through a hash functionA function that turns a key into a number used to pick a slot in a hash map's internal array. that turns it into a number, and uses that number to choose a slot in an internal array. To look the key up later, it hashes it again and goes straight to the slot. Two keys can land in the same slot (a collisionTwo different keys landing in the same hash map slot; the table handles it so lookups still work.); the table handles that and grows when it gets full, so the average cost stays constant.

Keys must be hashableAble to be used as a dict key or set member: numbers, strings and tuples are; lists and dicts are not.: numbers, strings and tuples work; lists and dicts do not (they can change, which would change their hash). Since Python 3.7, dicts also remember insertion order.

Worked example 1: counting

Count how often each word appears.

def word_counts(text):
    counts = {}
    for word in text.lower().split():
        counts[word] = counts.get(word, 0) + 1
    return counts

word_counts("the cat and the hat")
# {'the': 2, 'cat': 1, 'and': 1, 'hat': 1}

counts.get(word, 0) returns the current count, or 0 the first time. One pass, O(1) per word, so O(n) overall. The standard library has a ready-made version, collections.Counter, and Counter(words).most_common(3) gives the top three. Writing the loop yourself first makes it clear what Counter does.

To find the most common word, loop over the dict once and keep the best so far. Decide what happens on ties (for example, pick the alphabetically first word) and on empty input (return None), and write the rule down. Interviewers and teammates will ask.

Worked example 2: two sum

Given a list of numbers and a target, return the indexes of two different items that add up to the target.

The brute-force version checks every pair: O(n^2). The hash map version asks a better question at each step: "have I already seen the number that would complete this pair?"

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:
            return (seen[need], i)
        seen[n] = i
    return None

Trace nums = [2, 7, 11, 15], target = 9:

• i = 0, n = 2, need 7, not seen. Store {2: 0}.
• i = 1, n = 7, need 2, seen at index 0. Return (0, 1).

Checking seen before storing the current number stops an item pairing with itself: with [3] and target 6, the 3 is not in seen yet when we look for its partner. With [3, 3], the second 3 finds the first. One pass, O(n) time, O(n) space.

Patterns to recognise

• "How many times..." or "most frequent..." means count with a dict.
• "Have I seen..." or "remove duplicates" means a set.
• "Find a pair / complement" means store what you have seen, look up what you need.
• "Group by..." means dict of lists: groups.setdefault(key, []).append(item).

Common mistakes

• Searching a list inside a loop (if x in my_list) when a set would make it O(1).
• KeyError from counts[word] += 1 on a new key. Use .get(word, 0), setdefault, or collections.defaultdict(int).
• Using a list as a key. Convert it to a tuple first.
• Pairing an item with itself in two-sum by storing before checking.
• Forgetting normalisation. "The" and "the" are different keys unless you lowercase first.

Quick recap

• Lists: O(1) by position and at the end; O(n) to search or change the front.
• Dicts and sets: O(1) average lookup, insert and delete by key.
• Count with d.get(k, 0) + 1; find pairs by storing what you have seen.

Try it

The Do tab has three small functions: count words, find the most common one (with a tie rule), and two-sum in one pass.