Hash Map Patterns: One Lookup in Place of a Search

A hash map pattern replaces a search inside a loop with one lookup in a map of the items already seen. The cue is a property of the problem rather than a word in it: each item needs a partner, a count or a group that depends only on items that came before it. Finding two prices that add up to a budget has that property, because the partner of a price p is the one price equal to budget − p, its complement. A hash map, a table that finds a value from its key in about one step on average, can hold every earlier price, so each item asks the map instead of scanning back over the list. How the table manages that is the Hash Tables topic in Data Structures.

The pattern keeps one invariant: before item i is checked, the map holds exactly the items before i, each with its index. Looking up first and recording second is what keeps it true. The trace follows the values 4 1 6 3 8 and the target 9, one step per item, with the caret under the item being checked.

4 1 6 3 8
^
needs 9 - 4 = 5: not in the map
map after: {4: 0}

4 1 6 3 8
  ^
needs 9 - 1 = 8: not in the map
map after: {4: 0, 1: 1}

4 1 6 3 8
    ^
needs 9 - 6 = 3: not in the map
map after: {4: 0, 1: 1, 6: 2}

4 1 6 3 8
      ^
needs 9 - 3 = 6: found at index 2
pair: 2 3

The pass stopped at index 3 without reading the 8, and no pair was ever compared directly. Each lookup costs O(1) on average and O(n) in the worst case, when many keys land in the same slot, so the pass is O(n) on average for n values, with O(n) extra space for the map. Checking every pair instead costs O(n²).

A cloakroom works the same way: each coat gets a numbered hook, so collecting it means reading the ticket rather than searching the rail. The likeness breaks at who picks the hook. The attendant chooses a free one, while a hash map computes the hook from the key, so two keys can be sent to the same hook and have to share it.

The map can hold more than indices: a count of each item, or a list of items under a shared key. When the input is already sorted, two pointers find a pair with no map at all, in O(1) extra space, and the Two Pointers topic shows how.