Hash Maps

What is a hash map?

A hash map is a key-value store that answers "what value is associated with this key?" in O(1) average time. Python's built-in dict is a hash map. The basic operations are:

seen = {}
seen[key] = value          # insert or overwrite
value = seen[key]          # get (raises KeyError if missing)
value = seen.get(key, 0)   # get with a default, no KeyError
key in seen                # membership test
del seen[key]              # delete

Internally, a hash function converts the key into an array index. Two keys that hash to the same index are called a collision; Python handles collisions via open addressing. If many keys collide into the same bucket the lookup degrades to a linear scan - worst case O(n). With a good hash function and a reasonable load factor, collisions are rare and the average stays O(1).

The core trade-off: hash maps give O(1) average lookup and insert at the cost of O(n) space and no sorted order. Python dicts preserve insertion order since 3.7, but the keys are not sorted by value. If you need sorted iteration or range queries, a balanced BST (or Python's sortedcontainers.SortedDict) is the right tool.

Core operations

Key patterns

Complement lookup

For each element, ask "is the element I need to pair with this already in the map?" Record each element's index (or value) as you scan forward. The inner scan collapses from O(n) to O(1), turning an O(n²) brute force into O(n).

When to use - the problem gives a target sum or difference between two elements and asks you to find the pair (two sum, a pair with a given difference). The brute force checks every pair at O(n²); the map collapses the inner search to a single O(1) lookup.

How it works - scan once and keep a map of every value you have already seen. For each new element, compute the value that would complete the pair and look it up in the map. Because you store as you go, the match - if one exists - is always an earlier element, so a single forward pass finds it. Check for the complement before you store the current element; otherwise an element can pair with itself when the target is exactly double its value. One pass, O(n) time, O(n) space.

Frequency counting

Build a map from element to its count, then reason about counts. collections.Counter is the idiomatic tool; a plain dict with .get(key, 0) + 1 works identically. The key shift: after building the frequency map, the rest of the problem operates on counts, not on the original values.

When to use - the question is about how often values appear: "how many times does X occur", "which element is most common", "do two collections have the same multiset of items". Sorting or repeated scans to count would cost O(n log n) or O(n²); one pass over the data builds every count.

How it works - walk the input once and increment a counter for each element. After the pass the map holds every value's exact frequency, so the rest of the problem reads answers off the counts instead of re-examining the raw values. The counts are what carry the information - equal frequency maps mean equal multisets, the largest count names the mode. Building the map is O(n) time and O(k) space, where k is the number of distinct values.

Grouping by derived key

Compute a canonical form for each element - a transformed representation that is identical for all elements in the same group. Use that canonical form as the hash map key. All elements mapping to the same canonical form land in the same group.

When to use - the problem asks you to bucket items by some shared property: group anagrams, collect words by first letter, partition numbers by a modular value. Comparing every item against every other to find its group is O(n²); a derived key drops it to one O(n) pass.

How it works - for each element, compute a key that is the same for every item that belongs together and different for items that don't. For anagrams that key is the sorted characters - every anagram of a word produces the identical sorted form, so they collide into one bucket on purpose. Append each element to the list stored under its key; a defaultdict(list) creates the empty list on first access so you never special-case the first item. One pass groups everything, at the cost of computing each key.

Canonical examples

Two Sum

The complement lookup pattern in its canonical form. The insight: instead of checking every pair (O(n²)), record what we have seen and ask "is this element's complement already recorded?" - turning the inner loop into a single O(1) hash map lookup.

Group Anagrams

Grouping by derived key. The insight: two strings are anagrams if and only if they have the same sorted character tuple. That sorted tuple is the canonical key - every anagram group shares exactly one key, and the hash map collects them automatically.

When to reach for a hash map

• The problem says "seen before" or "contains duplicate" - store visited elements in a set or map.
• You need to count occurrences of elements - frequency map with Counter.
• You need to find a complement or pair that satisfies a numeric condition - complement lookup.
• You need to group elements by a derived property (anagram key, first character, modular value).
• The problem requires O(1) lookup by key where a list would give O(n) search.
• You are building a cache or memo table for previously computed results.
• You need to track the first or last occurrence of something by value.

Practice problems

• Two Sum - Complement lookup in its simplest form.
• Contains Duplicate - Seen-before check with a set.
• Valid Anagram - Character frequency comparison.
• Group Anagrams - Grouping by canonical key.
• Top K Frequent Elements - Frequency count then bucket or heap.
• LRU Cache - Hash map + doubly linked list for O(1) get and eviction.