Hash Map Applications

Whenever a problem asks "does X exist" or "how many times have I seen Y" or "what's the count of each value," reach for a hash map. The pattern shows up constantly.

Two Sum

Given an array and a target, find two indices that sum to the target. Brute force is $O(n^2)$. With a hash map: as you scan, for each $A[i]$, check whether $T - A[i]$ is already in the map. If yes, return the pair. If no, store $A[i] \to i$ and continue. $O(n)$ time, $O(n)$ space.

First non-repeating character

Count occurrences in one pass, then scan the string in order and return the first character whose count is 1. $O(n)$ time, $O(\sigma)$ space.

Subarray sum equals K

Compute running prefix sum $s$. At each step, look up how many times $s - K$ has appeared. That count equals the number of subarrays ending at the current index with sum $K$. Increment the count of $s$ in the map. $O(n)$ time.

Group by key

Anagrams, words with the same length, files with the same checksum — all the same pattern. Compute a canonical key per item, push each item into a list under its key.

Caches

Hash maps are the data structure underneath LRU caches. The map provides $O(1)$ lookup; a doubly linked list maintains the eviction order. Each map value points to the corresponding list node so you can move-to-front in $O(1)$.

When NOT to use a hash map

When keys have a small range (use an array), when you need ordered iteration (use a tree map), when memory is extremely tight (hash maps have 30-50% overhead even when full).