Hashing & Hash Maps

Why this matters / recognition signals

A hash map turns “is this value present / have I seen this before / what’s paired with this key” from an O(n) linear scan (or O(log n) on sorted data) into O(1) average-case lookup, by trading a small amount of extra memory for direct-addressed access. It’s the single highest-leverage data structure in interview problem-solving — a huge fraction of “can you do better than brute force?” follow-ups resolve to “yes, cache what you’ve seen in a hash map.”

Reach for it when the problem says:

“Have I seen this before” / “find the first duplicate” / “check existence” → hash set.
“Two numbers that sum to target” on unsorted input → hash map (index or complement lookup), since sorting would either cost O(n log n) or destroy the original indices the answer needs.
“Group items by some derived key” (anagrams, same digit sum, same remainder) → hash map from derived key → list of items.
“Count frequency of each element” → hash map from element → count.
“Find a pair/subarray with a given sum, in a single pass” → running hash map of prefix sums or seen values (see Arrays & Strings for the prefix-sum half of this).

How a hash map achieves O(1) average lookup

A hash map is, under the hood, an array (the bucket array) plus a hash function that maps a key to an array index. put/get compute index = hash(key) % capacity and go straight to that slot — no scanning.

flowchart LR
    K["key: 'cat'"] --> H["hash(key)
e.g. 2,286,887,772"]
    H --> M["% capacity (e.g. 16)"]
    M --> IDX["bucket index: 12"]
    IDX --> Bucket["buckets[12]"]

Two keys can hash to the same index — a collision — because the key space (all possible strings, all possible integers) is far larger than the bucket array. Two standard ways to handle it:

Chaining: each bucket holds a small list (or tree, in Java 8+‘s HashMap once a bucket gets large) of all entries that hashed there. A lookup goes to the bucket, then scans the short list for a matching key.

flowchart LR
    B0["bucket 0"] --> E0["empty"]
    B1["bucket 1"] --> N1["('bob', 30) → ('cab', 12)"]
    B2["bucket 2"] --> E2["empty"]
    B3["bucket 3"] --> N3["('amy', 25)"]
    Note["'bob' and 'cab' both hash to bucket 1 —
chained as a linked list; get('cab') walks the chain
and compares keys with equals() until it finds a match"]

Open addressing (e.g. linear probing): no per-bucket list — on a collision, probe forward (index+1, index+2, …) until an empty slot is found. Lookup re-runs the same probe sequence until it finds the key or hits an empty slot (which proves absence).

flowchart LR
    subgraph Table["bucket array, capacity 8"]
        direction LR
        S0["0: —"] --- S1["1: 'bob'"] --- S2["2: 'cab' (collided w/ bob, probed +1)"] --- S3["3: —"] --- S4["4: 'amy'"]
    end
    Note2["insert('cab') hashes to index 1, occupied by 'bob' →
probe index 2, empty → placed there"]

Java’s HashMap uses chaining (with a treeification optimization for long chains); Python’s dict uses open addressing internally. Either way, as long as the hash function spreads keys roughly uniformly across buckets, each bucket holds O(1) entries on average, so lookup is O(1) average.

Why worst case is O(n)

The O(1) average claim depends entirely on keys being spread out. It breaks down when:

A bad hash function clusters keys into few buckets — e.g. a hash function that only looks at part of the key, or returns the same value for many inputs. All colliding keys pile into one bucket’s chain (or one long open-addressing probe sequence), and a lookup degrades to scanning that whole pile — O(n).
Adversarial input deliberately targets the hash function — if an attacker knows your hash function, they can craft n keys that all collide, turning every operation into O(n) and the whole map into an O(n²) denial-of-service vector for n inserts. This is a real, historically-exploited vulnerability class (hash-flooding attacks), which is why production hash maps (Java’s HashMap since Java 8, Python’s dict) seed their hash function with per-process randomization and/or treeify long chains specifically to bound this worst case.
Too many entries in too few buckets (high load factor) without resizing — even with a good hash function, if the bucket array never grows, chains get long simply from volume, degrading toward O(n/capacity) per lookup — see load factor below.

Load factor and resizing

Load factor = number of entries / number of buckets. It’s the practical dial on the space/time tradeoff: low load factor means mostly-empty buckets (wastes memory, but chains stay short); high load factor means full buckets (saves memory, but chains grow, degrading lookup toward O(n)).

Java’s HashMap resizes (doubles bucket-array capacity, then rehashes every entry into new bucket positions) once load factor exceeds a threshold — default 0.75. This is exactly the same amortized O(1) argument as dynamic array doubling (see Complexity Analysis): resizing is O(n), but it happens exponentially less often as the map grows, so the amortized cost per insert stays O(1).

Worked example — inserting keys "a", "b", "c", "d", "e" into a table starting at capacity 4, load factor threshold 0.75 (resize when entries / capacity > 0.75):

Insert	Entries before	Capacity before	Load factor after insert	Resize triggered?	Capacity after
”a”	0	4	1/4 = 0.25	no	4
”b”	1	4	2/4 = 0.50	no	4
”c”	2	4	3/4 = 0.75	no (at, not over, threshold)	4
”d”	3	4	4/4 = 1.00	yes — resize to 8, rehash all 4	8
”e”	4	8	5/8 = 0.625	no	8

Every entry gets rehashed into a new bucket index on resize (% capacity changes when capacity changes), which is why resizing isn’t just “allocate more space” — it’s a full O(n) rebuild, amortized away by exponential growth exactly as with dynamic arrays.

Java implementation — Group Anagrams

Representative problem: group a list of strings so that anagrams end up together. The insight: two strings are anagrams iff they produce the same canonical key — here, their sorted character sequence. Hash map from canonical key → list of original strings turns an O(n² · k) pairwise-comparison brute force into O(n · k log k) (n strings, each sorted in O(k log k) for length k).

public List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> groups = new HashMap<>();
    for (String s : strs) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        String key = new String(chars);       // canonical form, e.g. "eat" -> "aet"
        groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(groups.values());
}

Java — Two Sum (unsorted input)

Contrast with the sorted, opposite-direction two-pointer version in Two Pointers & Sliding Window: on unsorted input, sorting first would cost O(n log n) and destroy the original indices the answer needs to return. A hash map does it in one O(n) pass instead — for each number, check whether its complement was already seen before inserting the current number (checking after inserting would incorrectly let an element pair with itself).

public int[] twoSumUnsorted(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();  // value -> index
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (seen.containsKey(complement)) {
            return new int[] { seen.get(complement), i };
        }
        seen.put(nums[i], i);   // record AFTER checking, so nums[i] can't pair with itself
    }
    return new int[] { -1, -1 };
}

Python implementations

Group Anagrams

from collections import defaultdict
 
def group_anagrams(strs: list[str]) -> list[list[str]]:
    groups: dict[str, list[str]] = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))    # canonical form, e.g. "eat" -> "aet"
        groups[key].append(s)
    return list(groups.values())

Two Sum (unsorted input)

def two_sum_unsorted(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}   # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i   # record AFTER checking, so num can't pair with itself
    return [-1, -1]

Complexity comparison

Approach	Time	Space	Why
Two Sum — brute force (all pairs)	O(n²)	O(1)	Nested loop over all pairs
Two Sum — sort + two pointers	O(n log n)	O(1) or O(n) (if indices must be preserved, needs a copy)	Sorting destroys original indices unless tracked separately
Two Sum — hash map	O(n) average, O(n²) worst case	O(n)	One pass; O(1) average lookup per element, degrades only under hash collisions
Group Anagrams — pairwise comparison	O(n² · k)	O(1) extra	Compares every string against every other string
Group Anagrams — hash map of sorted-string keys	O(n · k log k)	O(n · k)	One pass, one sort per string, grouped by canonical key
Hash map get/put	O(1) average	O(n) total entries	Direct bucket addressing when the hash function spreads keys well
Hash map get/put, worst case	O(n)	O(n)	All keys collide into one bucket/chain (bad hash function or adversarial input)

Common pitfalls

Using a mutable or poorly-designed object as a key without proper hashCode()/equals() (Java) or __hash__/__eq__ (Python): if two “equal” objects produce different hash codes, they’ll land in different buckets and the map will never find one from the other, even though they “look” equal — a classic silent-bug source in Java when a custom class overrides equals() but forgets hashCode().
Mutating a key after inserting it: the bucket index was computed from the key’s hash at insertion time; mutating the key afterward doesn’t move it to the new bucket, so future lookups with the mutated key silently fail to find it. Never use a mutable object (e.g. a Java ArrayList or ad-hoc mutable class) as a hash key unless it’s guaranteed not to change while it’s in the map.
Checking membership before inserting vs. inserting before checking, in Two Sum-style problems: inserting first can let an element incorrectly pair with itself (target = 2*nums[i]). Always check the complement first, then insert.
Assuming Python dicts preserve insertion order means they behave like a sorted structure: insertion-order preservation (guaranteed since Python 3.7) is not the same as being sorted by key — iterating a dict gives insertion order, not key order.
Treating O(1) average as a hard guarantee in performance-critical or adversarial-input contexts: for user-controlled keys in a public-facing service, a naive hash function is a real denial-of-service surface (hash-flooding); this is why it’s worth knowing production hash maps randomize their hash seed, not just accepting “O(1) average” as the whole story.
Forgetting that null/None keys and default-dict auto-vivification have their own edge cases: e.g. checking key in dict vs dict.get(key) on a defaultdict — merely reading a missing key from a defaultdict inserts it, which can silently bloat the map or break a subsequent len()/iteration check.

Practice problems

Two Sum (unsorted — hash map; contrast with the sorted two-pointer version in Two Pointers & Sliding Window)
Group Anagrams (canonical-key grouping)
Contains Duplicate / Contains Duplicate II (within distance k) (hash set / hash map of last-seen index)
Longest Consecutive Sequence (hash set, O(n) by only starting a count from numbers with no predecessor present)
Subarray Sum Equals K (running prefix sum + hash map of prefix-sum counts — bridges to Arrays & Strings)
Top K Frequent Elements (hash map for counts, then bucket sort or a heap on top — bridges to Heaps & Priority Queues)
Isomorphic Strings / Word Pattern (two-way hash map to enforce a consistent bijection)

Interview angles

“Why is hash map lookup O(1) if it’s backed by an array?” — the hash function maps any key to a fixed-size bucket index in O(1) (for fixed-length keys — more on variable-length below), so lookup is direct addressing, not scanning; O(1) average depends on the hash function spreading keys evenly so each bucket holds a small constant number of entries.
“What’s the actual worst case, and when does it happen?” — O(n): all keys collide into one bucket (bad hash function, or adversarial/attacker-crafted input specifically designed to collide) — name hash-flooding as the real-world manifestation and randomized hash seeding as the mitigation.
“Chaining vs. open addressing — what’s the tradeoff?” — chaining degrades gracefully under high load factor (chains just get longer) and handles deletion trivially, but has pointer-chasing/cache-locality overhead; open addressing is more cache-friendly (contiguous array) but degrades faster near full capacity and needs tombstones or careful shifting on deletion to avoid breaking probe sequences.
“Isn’t computing a hash for a string O(k) for length k, not O(1)?” — correct catch: hash map operations on variable-length keys are O(k) to compute the hash plus O(1) average for the bucket lookup itself, which is why complexity claims for string-keyed hash maps are usually stated as “O(k) per operation,” not flatly O(1) — worth naming this precision unprompted.
“Why does the hash map need to resize, and why double instead of adding a fixed amount?” — same amortized argument as a dynamic array (see Complexity Analysis): doubling makes resizes exponentially rarer as the map grows, keeping the amortized cost per insert O(1); fixed-increment growth would make resizes happen O(n) times, degrading amortized insert to O(n).
“Two Sum on unsorted input — why not just sort and two-pointer it?” — sorting costs O(n log n) (worse than the O(n) hash map approach) and destroys the original indices unless you separately track them, which adds back the complexity the sort was trying to avoid; hash map is strictly better here unless the problem specifically also needs the array sorted for another reason.

Notes

Explorer