Hash Map Patterns
A hash map is the single most common way an O(n squared) solution becomes O(n). The move is nearly always the same: instead of searching for the value you need, remember what you have already seen and look it up. Two sum is the canonical example, and once you see the shape you find it everywhere, from subarray sums to grouping anagrams to detecting duplicates.
Where to start, and what comes next
- 01
Complement / Two Sum
The complement pattern, which is the purest form of trading space for time. Everything else here is a variation on it.
- 02
Frequency Count
Counting, then answering questions about the counts. Pairs with bucketing, which beats a heap when the key range is bounded.
- 03
Hash Map Design
LRU and LFU caches, where a map is combined with another structure because neither alone gives O(1) for everything required.
- 04
HashMap & HashSet API
merge, computeIfAbsent and getOrDefault remove most of the null-checking boilerplate. Worth knowing before you need them under time pressure.
If you only have time for three things
- The complement pattern: check the map before inserting, so an element is never paired with itself.
- Running total plus a map of previously seen totals, which counts subarrays summing to a target even with negatives present.
- merge with a sum function as the idiomatic frequency counter, and computeIfAbsent for grouping.
The hash map answer is often the expected one, so the interesting part of the conversation is usually the caveat. Be ready to say that O(1) is an average, that a bad hash degrades it, and that Java treeifies a bucket past eight entries so the modern worst case is O(log n). If you propose a map, also be ready to say what it costs in space, because that is the trade you just made.
The idea underneath
If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.
Problems that use these patterns
Head to head
Questions people ask
Why check for the complement before inserting?
So an element cannot pair with itself. Searching for a target of 6 in an array containing a single 3 would otherwise find the 3 it just stored and report a false pair.
When is a hash map the wrong choice?
When you need order. Sorted iteration, range queries and nearest-key lookups are all impossible on a hash table, and reaching for TreeMap or a sorted structure is the right call there.
What breaks a HashMap key?
Mutating the object after inserting it. The entry was filed under its original hash, so changing a field that hashCode reads leaves it unreachable while still occupying the map. Keys should be immutable, which is much of why String is the default choice.