LOW LEVEL DESIGN · MACHINE CODING · MEDIUM · 25 OF 42

Design a HashMap from Scratch: Hashing, Resizing, Java Code

The build-your-own-HashMap machine coding question, solved end to end: buckets and chaining, why capacity is a power of two, spreading the hash, put, get and remove, the equals and hashCode contract, resizing at a load factor, bad hash codes, and a thread-safe version with lock striping, with a full Java 17 solution.

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 7
  8. 8
  9. 9
  10. 10
  11. 11
  12. 12
  13. 13
  14. 14
  15. 15
  16. 16
  17. 17
  18. 18
  19. 19
  20. 20
  21. 21
  22. 22
  23. 23
  24. 24
  25. 25
  26. 26
  27. 27
  28. 28
  29. 29
  30. 30
  31. 31
  32. 32
  33. 33
  34. 34
  35. 35
  36. 36
  37. 37
  38. 38
  39. 39
  40. 40
  41. 41
  42. 42
1 / 16

Press play to hear the narration, or step through at your own pace. The full Java code is below.

Full Java solution

One file, Java 17, 263 lines, with a small main() demo. Save it as HashMapDesign.java, then run javac HashMapDesign.java && java HashMapDesign.

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.ReentrantLock;
import java.util.function.BiFunction;
import java.util.function.Function;

/** A hash map from scratch: buckets, hashing, chaining, resizing, and a thread-safe striped version. */
public class HashMapDesign {

    /** The interface both maps implement, so callers do not care which one they hold. */
    interface SimpleMap<K, V> {
        V put(K key, V value);

        V get(K key);

        V remove(K key);

        int size();
    }

    // ---------- single-threaded map with separate chaining ----------
    static final class MyHashMap<K, V> implements SimpleMap<K, V> {
        static final class Node<K, V> {
            final int hash;
            final K key;
            V value;
            Node<K, V> next;

            Node(int hash, K key, V value, Node<K, V> next) {
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
        }

        private Node<K, V>[] table;
        private int size;
        private int resizes;
        private final float loadFactor;

        MyHashMap(int capacity, float loadFactor) {
            this.table = newTable(tableSizeFor(capacity));
            this.loadFactor = loadFactor;
        }

        MyHashMap() { this(16, 0.75f); }

        /** Mix the high bits into the low bits: the index only uses the low bits. */
        static int spread(Object key) {
            int h = key == null ? 0 : key.hashCode();
            return h ^ (h >>> 16);
        }

        /** Capacity is a power of two, so hash % n is just hash & (n - 1). */
        static int indexFor(int hash, int n) { return hash & (n - 1); }

        static int tableSizeFor(int c) {
            int n = 1;
            while (n < c) n <<= 1;
            return n;
        }

        @SuppressWarnings("unchecked")
        private static <K, V> Node<K, V>[] newTable(int n) { return (Node<K, V>[]) new Node<?, ?>[n]; }

        @Override
        public V put(K key, V value) {
            int h = spread(key);
            int i = indexFor(h, table.length);
            for (Node<K, V> e = table[i]; e != null; e = e.next) {
                if (e.hash == h && Objects.equals(e.key, key)) {
                    V old = e.value;
                    e.value = value;                      // same key: replace, size unchanged
                    return old;
                }
            }
            table[i] = new Node<>(h, key, value, table[i]);  // new key: push at the head of the chain
            if (++size > table.length * loadFactor) resize();
            return null;
        }

        @Override
        public V get(K key) {
            int h = spread(key);
            for (Node<K, V> e = table[indexFor(h, table.length)]; e != null; e = e.next) {
                if (e.hash == h && Objects.equals(e.key, key)) return e.value;
            }
            return null;
        }

        @Override
        public V remove(K key) {
            int h = spread(key);
            int i = indexFor(h, table.length);
            Node<K, V> prev = null;
            for (Node<K, V> e = table[i]; e != null; prev = e, e = e.next) {
                if (e.hash == h && Objects.equals(e.key, key)) {
                    if (prev == null) table[i] = e.next;
                    else prev.next = e.next;
                    size--;
                    return e.value;
                }
            }
            return null;
        }

        V merge(K key, V value, BiFunction<V, V, V> fn) {
            V old = get(key);
            V next = old == null ? value : fn.apply(old, value);
            put(key, next);
            return next;
        }

        /** Double the table. Each node either stays at i or moves to i + oldN: one extra hash bit decides. */
        private void resize() {
            Node<K, V>[] old = table;
            Node<K, V>[] next = newTable(old.length * 2);
            for (int i = 0; i < old.length; i++) {
                Node<K, V> e = old[i];
                while (e != null) {
                    Node<K, V> after = e.next;
                    int j = indexFor(e.hash, next.length);
                    e.next = next[j];
                    next[j] = e;
                    e = after;
                }
            }
            table = next;
            resizes++;
        }

        @Override public int size() { return size; }

        int capacity() { return table.length; }

        int resizes() { return resizes; }

        int longestChain() {
            int best = 0;
            for (Node<K, V> head : table) {
                int n = 0;
                for (Node<K, V> e = head; e != null; e = e.next) n++;
                best = Math.max(best, n);
            }
            return best;
        }
    }

    // ---------- thread-safe map: lock striping ----------
    /** N independent maps, each with its own lock; a key always goes to the same stripe. */
    static final class StripedHashMap<K, V> implements SimpleMap<K, V> {
        private final List<MyHashMap<K, V>> stripes = new ArrayList<>();
        private final List<ReentrantLock> locks = new ArrayList<>();

        StripedHashMap(int stripeCount) {
            for (int i = 0; i < stripeCount; i++) {
                stripes.add(new MyHashMap<>());
                locks.add(new ReentrantLock());
            }
        }

        private int stripe(Object key) { return Math.floorMod(MyHashMap.spread(key) >>> 8, stripes.size()); }

        private <R> R locked(Object key, Function<MyHashMap<K, V>, R> fn) {
            int s = stripe(key);
            locks.get(s).lock();
            try {
                return fn.apply(stripes.get(s));
            } finally {
                locks.get(s).unlock();
            }
        }

        @Override public V put(K key, V value) { return locked(key, m -> m.put(key, value)); }

        @Override public V get(K key) { return locked(key, m -> m.get(key)); }

        @Override public V remove(K key) { return locked(key, m -> m.remove(key)); }

        /** Read-modify-write as one step under the stripe lock: safe for counters. */
        V merge(K key, V value, BiFunction<V, V, V> fn) { return locked(key, m -> m.merge(key, value, fn)); }

        @Override
        public int size() {
            int n = 0;
            for (int i = 0; i < stripes.size(); i++) {
                locks.get(i).lock();
                try {
                    n += stripes.get(i).size();
                } finally {
                    locks.get(i).unlock();
                }
            }
            return n;
        }
    }

    // ---------- demo ----------
    /** A key with a terrible hashCode: every instance lands in the same bucket. */
    record BadKey(int id) {
        @Override public int hashCode() { return 42; }

        @Override public boolean equals(Object o) { return o instanceof BadKey b && b.id == id; }
    }

    /** A key whose hashCode changes after it is stored: the classic contract bug. */
    static final class MutableKey {
        String name;

        MutableKey(String name) { this.name = name; }

        @Override public int hashCode() { return name.hashCode(); }

        @Override public boolean equals(Object o) { return o instanceof MutableKey m && m.name.equals(name); }
    }

    public static void main(String[] args) throws InterruptedException {
        MyHashMap<String, Integer> m = new MyHashMap<>();
        for (int i = 0; i < 1000; i++) m.put("user-" + i, i);
        System.out.println("1000 keys: size " + m.size() + ", capacity " + m.capacity()
                + ", resizes " + m.resizes() + ", longest chain " + m.longestChain());
        System.out.println("get(user-777) = " + m.get("user-777")
                + ", put same key: old " + m.put("user-777", 0) + ", size still " + m.size());
        System.out.println("remove(user-1) = " + m.remove("user-1") + ", get after = " + m.get("user-1")
                + ", null key: " + m.put(null, -1) + " then " + m.get(null));

        MyHashMap<BadKey, Integer> bad = new MyHashMap<>();
        for (int i = 0; i < 200; i++) bad.put(new BadKey(i), i);
        System.out.println("bad hashCode: 200 keys, longest chain " + bad.longestChain()
                + " (every lookup is a list scan)");

        MyHashMap<MutableKey, String> lost = new MyHashMap<>();
        MutableKey k = new MutableKey("alpha");
        lost.put(k, "stored");
        k.name = "beta";
        System.out.println("mutated key after put: get(k) = " + lost.get(k) + ", size " + lost.size());

        // 8 threads x 5000 increments over 100 keys: the striped map loses none.
        StripedHashMap<String, Integer> counts = new StripedHashMap<>(16);
        ExecutorService pool = Executors.newFixedThreadPool(8);
        CountDownLatch go = new CountDownLatch(1);
        for (int t = 0; t < 8; t++) {
            pool.submit(() -> {
                go.await();
                for (int i = 0; i < 5000; i++) counts.merge("page-" + (i % 100), 1, Integer::sum);
                return null;
            });
        }
        go.countDown();
        pool.shutdown();
        pool.awaitTermination(10, TimeUnit.SECONDS);
        long total = 0;
        for (int i = 0; i < 100; i++) total += counts.get("page-" + i);
        System.out.println("striped map: 8 threads x 5000 increments = " + total + " (expected 40000)");
        if (total != 40000) throw new AssertionError("lost updates");
    }
}

Notes

Requirements

Agree the contract first. Put adds a key or replaces its value. Get returns the value or null. Remove deletes and returns the old value. All three should take constant time on average. Keys can be any type with sensible equals and hash code, and one null key is allowed. The map grows on its own. The usual follow-up is to make it safe for many threads, so leave room for that. Iteration order is out of scope.

Requirements
  • put(key, value): add or replace
  • get(key): value or null
  • remove(key): value or null
  • size()
  • average O(1) for all three
  • any key type with equals and
  • hashCode, null key allowed
  • grow automatically
  • then: make it thread-safe
  • out of scope: iteration order

Structure

The structure is an array of buckets. A key's hash picks a bucket, and each bucket holds a short linked list of nodes, called a chain, because different keys can land in the same bucket. Each node stores the hash, the key, the value and a pointer to the next node. To find a key, compute its bucket and walk that short chain comparing keys. If chains stay short, every operation is constant time on average.

Separate chaining
  • table: Node[16]
  • [0] -> null
  • [1] -> (user-7,7) -> (user-9,9)
  • [2] -> null
  • [3] -> (user-1,1)
  • ...
  • key -> hash -> index -> walk
  • the short chain, compare keys

Hashing

How does a key become a bucket index? Take its hash code and reduce it to the table size. Keep the capacity a power of two, and hash modulo n becomes hash and n minus one, a single fast bit mask. The catch is that the mask only looks at the lowest bits, and many hash codes differ only in their high bits. So first spread the hash by mixing the top sixteen bits into the bottom sixteen with an exclusive or.

From key to bucket
static int spread(Object key) {
  int h = key == null
      ? 0 : key.hashCode();
  return h ^ (h >>> 16);
}
static int indexFor(int h, int n) {
  return h & (n - 1);  // n = 2^k
}

n = 16: index = last 4 bits

put

Put works like this. Spread the hash, find the bucket and walk its chain. If a node has the same hash and an equal key, replace its value and return the old one; the size does not change. Otherwise push a new node at the head of the chain, increase the size, and if the map is now more than three quarters full, resize. Comparing the stored hash first is a cheap filter before calling equals.

put(key, value)
int h = spread(key);
int i = indexFor(h, table.length);
for (e = table[i]; e != null; e = e.next)
  if (e.hash == h &&
      Objects.equals(e.key, key)) {
    V old = e.value; e.value = value;
    return old;
  }
table[i] = new Node(h, key, value,
                    table[i]);
if (++size > cap * 0.75) resize();

get and remove

Get is the same walk, returning the value or null. Remove walks while remembering the previous node. When it finds the key, it links the previous node straight to the next one, or moves the bucket head if the match was first, then decreases the size. Using Objects equals instead of key dot equals means the one null key works without a special case.

remove(key)
Node prev = null;
for (e = table[i]; e != null;
     prev = e, e = e.next)
  if (e.hash == h &&
      Objects.equals(e.key, key)) {
    if (prev == null) table[i] = e.next;
    else prev.next = e.next;
    size--; return e.value;
  }
return null;

The contract

The map is only correct if keys keep Java's contract. Rule one: if two keys are equal, their hash codes must be equal, otherwise get searches the wrong bucket and misses a key that is there. Rule two: never change a key after putting it. Its hash changes, but the node stays in the old bucket, so the entry becomes unreachable. The demo shows exactly this: get returns null while the size is still one. That is why good keys are immutable.

equals and hashCode
  • rule 1: a.equals(b) means
  • a.hashCode() == b.hashCode()
  • else get() looks in the
  • wrong bucket
  • rule 2: never mutate a key
  • after put(): its hash moves,
  • the node does not
  • demo: put(k), k.name = "beta"
  • get(k) = null, size still 1

Resizing

As the map fills, chains get longer, so at a load factor of three quarters we double the table and move every node. Because the size is a power of two, doubling adds exactly one bit to the mask, so each node either stays at the same index or moves up by the old size. A single resize costs time proportional to the size, but it happens so rarely that the average cost of a put stays constant. A thousand keys need only seven resizes.

resize()
new table = 2 x old length
for each node in each old bucket:
  j = hash & (newN - 1)
  push node onto new[j]

one more hash bit decides:
  j == i  or  j == i + oldN
1000 keys: capacity 2048,
  7 resizes, longest chain 4

Bad hash codes

Now the worst case. If a key class returns the same hash code for everything, every key lands in one bucket, the chain grows to the full size of the map, and constant time quietly becomes linear. The real Java map defends against this by turning any chain longer than eight into a balanced tree, giving logarithmic time even in the worst case. Mention it: attackers can choose keys that collide on purpose to slow a server down.

When every key collides
  • hashCode() { return 42; }
  • 200 keys, longest chain 200
  • every get is a list scan: O(n)
  • Java 8+ fix: a chain longer
  • than 8 turns into a red-black
  • tree, so O(log n) worst case
  • attackers can force collisions
  • with chosen keys: hash flooding

Concurrency

Our map is not safe for many threads. If two threads put different keys into the same empty bucket, both read the head as empty and both write their own node as the new head, so one key silently disappears. A put during a resize can lose nodes, and size plus plus is a read, add and write that can drop updates. Just saying synchronized on every method fixes it, but then only one thread can use the map at a time.

Why it is not thread-safe
  • thread A and B: put into the
  • same empty bucket
  • both read head = null
  • both write their node as head
  • one key silently vanishes
  • resize during put: nodes moved
  • twice or lost
  • size++ is read-modify-write:
  • counts drift

Lock striping

A better design is lock striping. Keep sixteen independent maps, each with its own lock, and send each key to one stripe by its hash. Two threads only wait for each other when their keys share a stripe, so up to sixteen can work at once. A merge method does the read and the write under one lock, which is what a counter needs. In the demo, eight threads add five thousand each and the total is exactly forty thousand.

StripedHashMap
List<MyHashMap> stripes (16)
List<ReentrantLock> locks (16)

int s = stripe(key);
locks.get(s).lock();
try { return fn.apply(stripes.get(s)); }
finally { locks.get(s).unlock(); }

merge(): read + write in one lock
8 x 5000 increments = 40000

Real world

Interviewers like to hear what the real libraries do. Java's hash map uses chaining, a power-of-two table, a load factor of three quarters, and turns long chains into trees. The concurrent hash map goes further than our stripes: it fills an empty bucket with a single compare-and-set, locks only the head node of a busy bucket, lets several threads help with a resize, and keeps the size in striped counters. The old Hashtable uses one lock for everything.

How Java really does it
  • HashMap: chaining, treeify at 8,
  • power-of-two table, 0.75
  • ConcurrentHashMap (Java 8+):
  • CAS to fill an empty bucket
  • lock only the bucket head
  • when it is not empty
  • resize helped by many threads
  • size kept in striped counters
  • Hashtable: one lock, avoid

Extensibility

Follow-ups build on the same core. Open addressing stores entries directly in the array and probes the next slot on a collision, which is friendlier to the CPU cache. A map can shrink when mostly empty. Thread a doubly linked list through the nodes and you get insertion order; move a node to the front on every get and you have an LRU cache. Add an expiry to each node and it becomes a cache with time to live.

Extension points
  • open addressing: no nodes,
  • probe the next free slot
  • (linear, Robin Hood hashing)
  • shrink when mostly empty
  • iteration in insert order:
  • a doubly linked list of nodes
  • LRU cache: that list + move
  • to front on get
  • TTL: an expiry on each node

Testing

The full code is below the player. The demo inserts a thousand keys and prints the capacity, the number of resizes and the longest chain; replaces a value and checks the size did not change; removes a key and stores a null key; shows the two hundred long chain from a bad hash code; shows a mutated key going missing; and runs eight threads of counter updates on the striped map without losing a single one.

Run it
1000 keys: capacity 2048,
  resizes 7, longest chain 4
put same key: old 777, size 1000
remove(user-1) = 1, then null
null key: put then get = -1
bad hashCode: longest chain 200
mutated key: get(k) = null, size 1
striped: 8 x 5000 = 40000

Say it like this

Here is the short version to say out loud. An array of buckets whose size is a power of two, each a chain of nodes. Spread the hash, mask it to an index, compare the stored hash and then equals. Double the table at three quarters full, so put is constant time amortised. Keys must keep the equals and hash code contract and never change. For many threads, use lock striping or compare-and-set per bucket.

In the interview
  • "An array of buckets, size 2^k,
  • each a chain of nodes. Spread
  • the hash, mask to an index,
  • compare hash then equals.
  • Double at 0.75 full, so put is
  • O(1) amortised. Keys must keep
  • the equals and hashCode contract
  • and never change. For threads,
  • lock striping or CAS per bucket."

Interview questions

Why is the table size kept a power of two?

Then hash modulo n equals hash AND (n minus 1), a single fast bit operation, and doubling the table adds exactly one bit, so each node either stays at its index or moves up by the old size during a resize.

Why spread the hash with h ^ (h >>> 16)?

The index uses only the low bits of the hash. Many hash codes differ mostly in their high bits, so mixing the high half into the low half makes keys spread across buckets instead of piling into a few.

What happens if two equal keys return different hash codes?

They land in different buckets. A get with one key searches the wrong bucket and misses the entry stored with the other, and put can store a duplicate. Equal objects must have equal hash codes.

Why should map keys be immutable?

If a key changes after put, its hash changes but its node stays in the old bucket, so get with the same object looks in the new bucket and finds nothing. The entry is stuck and leaks.

Why resize at a load factor of 0.75 and why is put still O(1)?

Below about 0.75 full, chains stay very short. Doubling costs O(n) but happens after n more inserts, so the cost spread over every put is constant on average.

What is the worst case and how does Java limit it?

If every key collides, one bucket holds all n keys and operations become O(n). Java 8 and later turn a chain longer than eight into a red-black tree, so the worst case is O(log n).

How would you make the map thread-safe without one big lock?

Lock striping: split it into N small maps with N locks and route each key by hash, so threads only contend when keys share a stripe. ConcurrentHashMap goes further with compare-and-set on empty buckets and a lock per bucket.

What is the difference between chaining and open addressing?

Chaining keeps a list per bucket. Open addressing stores entries in the array itself and probes for the next free slot on a collision. It is more cache-friendly but needs a lower load factor and careful deletes.