Hash maps

You’ll recognise it when

• You’re counting things: how often each word appears, which value is the majority, whether two strings use the same letters.
• You keep asking “have I seen this before?”, or “have I seen the value that would complete a pair?”
• You need to group items that share something: anagrams, the same sorted letters, the same row and column.
• A nested loop searches a list for a value, and n is large. Swapping the inner search for a map lookup usually turns O(n²) into O(n).

If you need the keys in order (the smallest key, the next key after 40, everything in a range), a hash map can’t help: it scatters keys on purpose. Reach for a sorted structure, or binary search on a sorted array.

The idea

Picture a cloakroom with 8 hooks. Instead of hanging coats in the first free spot and searching every hook later, the attendant uses a rule: take your ticket number, divide by 8, and hang the coat on the hook named by the remainder. Ticket 29 always goes on hook 5. When you come back, the attendant walks straight to hook 5. If a few coats share that hook, they flip through just those few.

A hash map is that cloakroom. A hash function turns any key into an integer, hash(key) % capacity picks the bucket, and each bucket keeps a short list of the keys that landed there. Two keys in the same bucket is a collision, and it’s normal: the map just checks each key in that list. As long as the lists stay short, every operation touches only a handful of keys, however many are stored.

How it works

We’ll build one from scratch: an array of buckets, where each bucket is a list of (key, value) pairs. This is separate chaining, the design used by Java’s HashMap. The keys in the graphic are small ints, which in Python hash to themselves (hash(29) == 29), so you can do the arithmetic in your head.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the keys: try many keys that are equal mod 8, like 3, 11, 19, 27.

Why it’s correct: a key is only ever stored in the bucket its hash picks for the current capacity. put and get compute the same bucket, and a resize moves every key to its new bucket before anything else happens, so the one chain a lookup reads is the only place the key could be.

class MyHashMap:
    """A hash map with separate chaining: each bucket is a list of [key, value] pairs."""

    MAX_LOAD = 0.75                   # resize when size / capacity passes this

    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0                                   # number of keys stored

    def _bucket(self, key):
        """The chain that key belongs in."""
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > self.MAX_LOAD * len(self.buckets):
            self._resize()

    def _resize(self):
        old = self.buckets
        self.buckets = [[] for _ in range(2 * len(old))]
        for chain in old:
            for key, value in chain:
                self._bucket(key).append([key, value])

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

    def remove(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

#include <functional>
#include <optional>
#include <utility>
#include <vector>
using namespace std;

// A hash map with separate chaining: each bucket is a vector of (key, value) pairs.
template <typename K, typename V>
class MyHashMap {
    static constexpr double MAX_LOAD = 0.75;   // resize when size / capacity passes this
    vector<vector<pair<K, V>>> buckets;

    // The chain that key belongs in.
    vector<pair<K, V>>& bucketFor(const K& key) {
        return buckets[hash<K>{}(key) % buckets.size()];
    }

    void resize() {
        vector<vector<pair<K, V>>> old = move(buckets);
        buckets.assign(2 * old.size(), {});
        for (auto& chain : old)
            for (auto& [key, value] : chain)
                bucketFor(key).push_back({key, value});
    }

public:
    size_t size = 0;                                       // number of keys stored

    explicit MyHashMap(size_t capacity = 8) : buckets(capacity) {}

    void put(const K& key, const V& value) {
        auto& bucket = bucketFor(key);
        for (auto& entry : bucket) {
            if (entry.first == key) {
                entry.second = value;
                return;
            }
        }
        bucket.push_back({key, value});
        size++;
        if (size > MAX_LOAD * buckets.size()) {
            resize();
        }
    }

    optional<V> get(const K& key) {
        auto& bucket = bucketFor(key);
        for (auto& [k, v] : bucket) {
            if (k == key) return v;
        }
        return nullopt;
    }

    bool remove(const K& key) {
        auto& bucket = bucketFor(key);
        for (size_t i = 0; i < bucket.size(); i++) {
            if (bucket[i].first == key) {
                bucket.erase(bucket.begin() + i);
                size--;
                return true;
            }
        }
        return false;
    }
};

import java.util.ArrayList;
import java.util.List;

// A hash map with separate chaining: each bucket is a list of key-value entries.
class MyHashMap<K, V> {
    static final double MAX_LOAD = 0.75;   // resize when size / capacity passes this

    static class Entry<K, V> {
        final K key;
        V value;
        Entry(K key, V value) { this.key = key; this.value = value; }
    }

    private List<List<Entry<K, V>>> buckets;
    int size = 0;                                          // number of keys stored

    MyHashMap() { this(8); }

    MyHashMap(int capacity) {
        buckets = newBuckets(capacity);
    }

    private static <K, V> List<List<Entry<K, V>>> newBuckets(int capacity) {
        List<List<Entry<K, V>>> list = new ArrayList<>(capacity);
        for (int i = 0; i < capacity; i++) list.add(new ArrayList<>());
        return list;
    }

    // The chain that key belongs in.
    private List<Entry<K, V>> bucketFor(K key) {
        return buckets.get(Math.floorMod(key.hashCode(), buckets.size()));
    }

    void put(K key, V value) {
        List<Entry<K, V>> bucket = bucketFor(key);
        for (Entry<K, V> e : bucket) {
            if (e.key.equals(key)) {
                e.value = value;
                return;
            }
        }
        bucket.add(new Entry<>(key, value));
        size++;
        if (size > MAX_LOAD * buckets.size()) {
            resize();
        }
    }

    private void resize() {
        List<List<Entry<K, V>>> old = buckets;
        buckets = newBuckets(2 * old.size());
        for (List<Entry<K, V>> chain : old)
            for (Entry<K, V> e : chain)
                bucketFor(e.key).add(e);
    }

    V get(K key) {
        List<Entry<K, V>> bucket = bucketFor(key);
        for (Entry<K, V> e : bucket) {
            if (e.key.equals(key)) return e.value;
        }
        return null;
    }

    boolean remove(K key) {
        List<Entry<K, V>> bucket = bucketFor(key);
        for (int i = 0; i < bucket.size(); i++) {
            if (bucket.get(i).key.equals(key)) {
                bucket.remove(i);
                size--;
                return true;
            }
        }
        return false;
    }
}

Using it in interviews

In an interview you use the built-in map (dict, unordered_map, HashMap) and spend your thinking on what the key is. Three patterns cover most problems.

Counting. The key is the item, the value is how many times you’ve seen it.

from collections import Counter
counts = Counter("mississippi")      # {'i': 4, 's': 4, 'p': 2, 'm': 1}
same_letters = Counter(a) == Counter(b)

“Have I seen the complement?” Walk the list once, and before storing each value, look for the one that would finish the job. For two sum, that’s target - x.

def two_sum(nums, target):
    seen = {}                        # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:       # check first...
            return [seen[target - x], i]
        seen[x] = i                  # ...then store, so x can't pair with itself

Grouping by a key. Compute a key that is equal for items that belong together, and collect each group in a list. Anagrams share their sorted letters.

from collections import defaultdict
groups = defaultdict(list)
for word in ["eat", "tea", "tan", "ate", "nat"]:
    groups["".join(sorted(word))].append(word)
# {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}

Why it’s O(1) on average

With a hash that spreads keys evenly, the n keys fall roughly evenly across the m buckets, so a chain holds about n / m keys on average. That ratio is the load factor, and resizing keeps it at most 0.75. A lookup hashes once and compares with about one key: O(1) on average.

Resizing costs O(n) when it happens, but it happens rarely. Starting from 8 buckets and doubling, the table rebuilds when it holds 7, 13, 25, 49, … keys, and the total work of all those rebuilds is less than 2n. Spread over n inserts, that’s O(1) extra per insert, amortised.

The worst case is O(n): if every key lands in the same bucket, one chain holds everything and each lookup walks all of it. That happens with a poor hash function, or when someone picks keys on purpose to collide (see hash flooding below).

Space is O(n): the keys and values, plus an array of buckets at most a constant factor bigger than n.

Common mistakes

groups[sorted(word)].append(word)          # ✗ TypeError: unhashable type: 'list'
groups[tuple(sorted(word))].append(word)   # ✓ tuples are hashable

seen[x] = i; if target - x in seen: ...    # ✗ finds x itself
if target - x in seen: ...; seen[x] = i    # ✓ only earlier elements

new[i] = old[i]                            # ✗ keys are now in the wrong buckets
new[hash(k) % len(new)].append((k, v))     # ✓ recompute every key's bucket

for k in d:
    if d[k] == 0: del d[k]                 # ✗ dictionary changed size during iteration
for k in list(d):
    if d[k] == 0: del d[k]                 # ✓ iterate over a snapshot

Variations

• Hash sets are hash maps with keys and no values. Use one for “have I seen it?” and for removing duplicates: seen = set(), x in seen.
• Composite keys. To key on several things at once, like a grid cell or a sorted letter count, use a tuple: (row, col) or tuple(sorted(word)). In C++ and Java, either encode the parts into one number or string, or give the map a hash function for your type.
• Counter and defaultdict. Counter counts; reading a missing key gives 0 and doesn’t insert it. defaultdict(list) builds groups; reading a missing key inserts an empty list, which can silently grow the map.
• Open addressing. Instead of chains, store every key in the array itself. On a collision, try the next slot (linear probing) until you find a free one. Python’s dict works this way, with a smarter probe order. Removing needs care: leave a “deleted” marker, or later lookups stop too early.
• Hash flooding. If an attacker knows your hash function, they can send keys that all collide, turning every operation into O(n). Python randomises string hashes per process for this reason, and Java turns long chains into balanced trees. On competitive programming judges, a plain unordered_map with integer keys can be forced into its worst case; a randomised custom hash fixes it.