Hash Table

Intuition

A hash table stores key-value pairs and finds a key in O(1) on average. Think of it as an array whose index can be anything hashable: a big integer, a string, a tuple. A hash function turns the key into an integer, and that integer modulo the table size picks a bucket. To look a key up, you hash it again and only inspect that one bucket.

A good hash function is cheap to compute and spreads keys evenly. For integers a classic choice is key mod M with a prime M; for strings, treat the characters as digits of a number in some base and reduce modulo a large value (polynomial string hashing is its own topic).

Different keys can land in the same bucket, a collision. Collisions are unavoidable once there are more possible keys than buckets, so every hash table has a strategy:

• Separate chaining: each bucket holds a small list of entries; a lookup scans that list. With n entries in m buckets, a lookup costs O(1 + n/m) on average.
• Open addressing: all entries live in the array itself; on a collision you probe other slots (linear probing tries i + 1, i + 2, ...; quadratic probing tries i + 1, i + 4, i + 9, ...). Deletion needs "tombstone" markers so later probes do not stop early.

The ratio n/m is the load factor. Real implementations keep it bounded (around 0.75 for Java's HashMap, about 2/3 for CPython's dict) by doubling the table and rehashing every entry when it gets too full. Doubling makes the occasional O(n) resize cost O(1) amortized per insertion.

What you use in practice:

• Python: dict and set (open addressing; dict keeps insertion order), collections.Counter for frequencies, collections.defaultdict for grouping. Keys must be hashable, so use tuples instead of lists and frozenset instead of set.
• Java: HashMap / HashSet (chaining; long chains turn into small trees). LinkedHashMap keeps order.
• C++: unordered_map / unordered_set. Use map/set only when you need sorted order.

When to use it in interviews / OAs

Hash tables are the most common tool for turning an O(n^2) scan into O(n). Typical signals:

• "Have I seen this before?": duplicates, first unique character, detecting a repeated state in a simulation.
• Counting: anagram checks, majority element, top-k frequent elements (count, then heap or bucket sort), ransom-note style "can A be built from B".
• Complement lookup: two sum and its relatives; store what you have seen, query what you need.
• Grouping by a canonical key: group anagrams (sorted letters or a 26-length count tuple), group shifted strings (difference pattern), isomorphic strings (two maps, one in each direction).
• Prefix sums + hash map: number of subarrays with sum k, longest subarray with equal 0s and 1s (map 0 to -1), subarray sums divisible by k (store remainders).
• Index maps inside designs: LRU cache (key to list node), insert/delete/get-random in O(1) (value to array index), coordinate compression (value to rank), memoization of DP states.

Template

A minimal separate-chaining map with resizing. You will rarely write one at work, but "design a hash map" is a real interview question, and building it once makes the complexity discussion concrete.

class ChainedHashMap:
    def __init__(self, capacity: int = 8) -> None:
        self.buckets: list[list[list]] = [[] for _ in range(max(1, capacity))]
        self.size = 0

    def _bucket(self, key) -> list:
        return self.buckets[hash(key) % len(self.buckets)]  # Hash, then reduce to a bucket index.

    def put(self, key, value) -> None:
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:  # Existing key: overwrite the value.
                pair[1] = value
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):  # Keep the load factor bounded.
            self._resize(2 * len(self.buckets))

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def remove(self, key) -> bool:
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = bucket[-1]  # Swap with the last entry, then pop: O(1).
                bucket.pop()
                self.size -= 1
                return True
        return False

    def _resize(self, new_capacity: int) -> None:
        old = self.buckets
        self.buckets = [[] for _ in range(new_capacity)]
        for bucket in old:
            for k, v in bucket:
                self._bucket(k).append([k, v])  # Every key must be rehashed.


m = ChainedHashMap()
for i in range(100):
    m.put(i, i * i)
m.put(7, -1)
assert m.get(7) == -1 and m.get(99) == 9801 and m.get(100) is None
assert m.remove(5) and not m.remove(5) and m.size == 99

The three patterns that cover most hash-table interview questions: complement lookup, canonical-key grouping, and prefix sums.

from collections import Counter, defaultdict


def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    seen: dict[int, int] = {}  # value -> index of an earlier occurrence
    for i, x in enumerate(nums):
        if target - x in seen:  # Look up the complement before storing x.
            return seen[target - x], i
        seen[x] = i
    return None


def group_anagrams(words: list[str]) -> list[list[str]]:
    groups: defaultdict[tuple, list[str]] = defaultdict(list)
    for w in words:
        groups[tuple(sorted(w))].append(w)  # Canonical key: the sorted letters.
    return list(groups.values())


def count_subarrays_with_sum(nums: list[int], k: int) -> int:
    seen = Counter({0: 1})  # The empty prefix, so subarrays may start at index 0.
    prefix = answer = 0
    for x in nums:
        prefix += x
        answer += seen[prefix - k]  # Earlier prefixes p with prefix - p == k.
        seen[prefix] += 1
    return answer


assert two_sum([3, 2, 4], 6) == (1, 2) and two_sum([1, 2], 7) is None
assert sorted(map(sorted, group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))) == [
    ["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert count_subarrays_with_sum([1, 1, 1], 2) == 2
assert count_subarrays_with_sum([1, -1, 0], 0) == 3

The prefix-sum trick works because the sum of nums[i..j] equals prefix[j] - prefix[i-1]. For each right end, you ask "how many earlier prefixes equal prefix - k?", and the hash map answers in O(1). It also works with negative numbers, where a sliding window does not.

Complexity

• Insert, lookup and delete: O(1) on average, assuming a reasonable hash function and a bounded load factor. Resizing makes inserts O(1) amortized.
• Worst case: O(n) per operation if many keys collide (bad hash function or adversarial input).
• Space: O(n). Hash tables trade memory for speed; a dict of 10^6 small entries already takes on the order of 100 MB in Python.
• Hashing a key is not free: hashing a string of length L costs O(L), so a map keyed by long strings or big tuples is O(L) per operation.

Common pitfalls

• Unhashable keys. Lists, sets and dicts cannot be keys in Python. Convert to tuple(...) or frozenset(...) first.
• Using the same element twice. In two sum, check for the complement before inserting the current value.
• Forgetting the empty prefix. Prefix-sum counting must start with {0: 1}; otherwise subarrays that begin at index 0 are missed.
• defaultdict side effects. Reading d[k] on a defaultdict inserts k. Use k in d or d.get(k) when you only want to check. (Counter returns 0 for a missing key without inserting it.)
• Mutating while iterating. Adding or removing keys while looping over a dict raises an error; iterate over list(d) instead.
• Relying on order. Python dicts keep insertion order, but sets are unordered, and Java's HashMap and C++'s unordered_map have no meaningful order. Sort explicitly when output order matters.
• Anti-hash tests in OAs. Some contest-style judges include inputs that make many integers collide in C++ unordered_map (and occasionally in Python). If a hash-heavy solution times out, randomize keys (for example, XOR with a random salt) or switch to sorting.
• Floating-point keys. Values that should be equal may differ in the last bit; round or use exact representations (fractions, reduced integer pairs for slopes).

Interview variations

• Two sum, four sum II (count pairs of pair-sums), contains duplicate within distance k (map value to last index).
• Longest consecutive sequence: put everything in a set and only start counting from numbers whose predecessor is missing, which gives O(n).
• Subarray sum equals k, continuous subarray sum (remainder map), contiguous array (0/1 balance).
• Group anagrams, isomorphic strings, word pattern (bijection needs two maps).
• Randomized set: array plus value-to-index map; delete by swapping the target with the last element.
• Design a hash map / hash set without built-ins (chaining with resizing, as above).
• Top-k frequent elements: Counter plus a heap, or bucket sort by frequency for O(n).