The Algebra of Membership

What a hash map really is

A hash map is an array of buckets, indexed not by position but by a hashed version of the key. The hash function h(k) takes an arbitrary key (a string, a tuple, an integer) and produces an index into the bucket array. If the function distributes keys uniformly and the array stays sparse, the expected number of keys in any one bucket is a small constant. Lookup becomes: hash the key, jump to the bucket, compare a handful of entries. That's the O(1) you've been taking for granted.

The word amortised matters. When the array fills beyond some threshold (traditionally 0.7 or 0.75 of capacity), the runtime allocates a larger array, typically double, and rehashes every existing key into it. That rehash is O(n). But since you can do many inserts between rehashes, the average cost per insert is still O(1). The worst-case insert, however, is O(n). For hard real-time systems, this is the same subtlety that appears in dynamic arrays: amortised and worst-case are different numbers, and which one matters depends on your deadline.

The seen-so-far pattern

The most important technique this module teaches is a shape of solution, not a data structure. Whenever you are asked a question like "does there exist a pair of elements satisfying property P?" and the brute force is O(n²), try this: iterate once, and at each element ask "what complement would satisfy P with me?" and then check whether you've already seen that complement.

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

Notice the order. You check first, then record. If you recorded first, an element could "pair with itself" in a target = 2x situation. Check-then-record is the version that is robust.

Three patterns you'll reuse

Frequency counting

Almost every problem about repetition (duplicates, majority element, top-k) starts with a frequency table. Python's Counter wraps this; in languages without it, a plain hash map works identically. The technique matters more than the API.

def top_k_frequent(nums, k):
    from collections import Counter
    freq = Counter(nums)
    # Bucket sort by frequency - beats general sort for this case.
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, cnt in freq.items():
        buckets[cnt].append(val)
    out = []
    for i in range(len(buckets) - 1, 0, -1):
        out.extend(buckets[i])
        if len(out) >= k: return out[:k]
    return out

Grouping by signature

When you want to group items that share some canonical form (anagrams, rotations, shape-equivalent trees), map each item to a signature, then use the hash map as an index from signatures to groups.

def group_anagrams(strs):
    groups = {}
    for s in strs:
        sig = tuple(sorted(s))
        groups.setdefault(sig, []).append(s)
    return list(groups.values())

For lowercase-ASCII anagrams, the 26-length count tuple is a cheaper signature than sorted. The technique is the same; only the signature function changes.

Running-sum + hash

The subarray-sum-equals-K problem reduces to: find two prefix sums that differ by K. Maintain a hash map of prefix sum → count, and at each step look up running_sum - K:

def subarray_sum(nums, k):
    from collections import defaultdict
    seen = defaultdict(int)
    seen[0] = 1          # empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

The seen[0] = 1 seed represents the empty prefix and is responsible for counting subarrays that start at index 0. Leaving it out silently undercounts.

Complexity: when is O(1) actually O(1)?

Hash map operations are expected O(1) under three assumptions: the hash function distributes keys uniformly; the table is periodically resized to keep the load factor bounded; and the cost of hashing a key is itself O(1). The last point deserves attention. Hashing a string of length L is O(L), not O(1). If your keys are long strings, your hash map operations are O(L) per access. In most practical cases this is fine; in tight inner loops it can dominate.

Worst-case behaviour is O(n) per operation, when adversarially chosen keys collide in one bucket or when the table resizes. Production hash maps in Python, Java, and most modern runtimes use randomised hashing to prevent the first; the second is priced in via amortisation.

When a hash map is the wrong tool

If you need the keys in sorted order, or you need range queries ("give me all keys between 10 and 20"), a hash map is worthless. Reach for a balanced binary search tree: Python's SortedDict, Java's TreeMap, C++'s std::map. If you need to find the key "closest to" a query, again a tree beats a hash map. If memory is tight and the universe of keys is small and dense, a plain array indexed by the key is simpler and faster.

Hash sets are hash maps without values

Everything above applies equally to set. The set is the specialisation of the map where you only care about membership. The classic use is deduplication (list(set(xs)) in O(n)) and set algebra: union, intersection, difference. In Python, these are operator-overloaded: a & b, a | b, a - b. In other languages they are methods. Either way, the underlying algorithm is the same: iterate the smaller set, look up each element in the larger.

Where beginners go wrong

• Using a list for membership. if x in big_list is O(n); if x in big_set is O(1). If you do the former inside a loop, you've written O(n²) by accident.
• Mutating a set while iterating it. Every language throws an error or silently misbehaves. Build a new set if you need to transform membership.
• Expecting ordered iteration. Python 3.7+ preserves insertion order in dict, but sets are not ordered. Never rely on iteration order if you want your code to be portable.
• Using a mutable object as a key. A list cannot be a dict key because its hash would change when you mutate it. Use a tuple. In general: only hashable, immutable values belong in hash maps.

What to read next

Continue with Module 05 · Trees & Recursion, where hashing reappears in memoisation. The earlier modules, Arrays and Strings, both benefit from a second pass once you're fluent with the seen-so-far pattern; many of their problems collapse to one-pass solutions once a hash map is in your toolkit.