Design HashMap

EasyDesign · Hashing · Separate Chaining🧩 Hashing & Counting LeetCode #706 ↗Updated Oct 30, 2026

Problem

Implement your own MyHashMap for integer keys and values without any built-in hash table. put(key, value) inserts or overwrites, get(key) returns the stored value or -1 if absent, and remove(key) deletes the key if it exists.

Inputput(1,10) put(2,20) get(1) get(3)Output10, -1

Inputput(2,5) get(2)Output5 (overwritten)

Inputremove(2) get(2)Output-1

0 ≤ key, value ≤ 10⁶ · at most 10⁴ calls in total · no built-in hash map / set

Try it yourself

Java

class MyHashMap {
    public MyHashMap() {
        
    }

    public void put(int key, int value) {
        
    }

    public int get(int key) {
        
    }

    public void remove(int key) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Hash the key to pick one of a small number of buckets, and keep a short list of entries in each bucket. With a good spread and resizing at a load factor, every list stays O(1) long on average.

PatternHashing & Counting

Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].

Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.

Open the Hashing & Counting guide →

Approaches

Brute ForceUnsorted List of Pairs

Time O(n) per opSpace O(n)

Store every (key, value) pair in an ArrayList. Each operation scans the list for the key: overwrite or append on put, return or -1 on get, delete on remove.

Java

class MyHashMap {
    private final List<int[]> entries = new ArrayList<>(); // each = {key, value}
    public MyHashMap() {}
    private int find(int key) {
        for (int i = 0; i < entries.size(); i++) if (entries.get(i)[0] == key) return i;
        return -1;
    }
    public void put(int key, int value) {
        int i = find(key);
        if (i >= 0) entries.get(i)[1] = value;
        else entries.add(new int[]{key, value});
    }
    public int get(int key) {
        int i = find(key);
        return i >= 0 ? entries.get(i)[1] : -1;
    }
    public void remove(int key) {
        int i = find(key);
        if (i >= 0) entries.remove(i);
    }
}

Correct and tiny, but every call is a linear scan — not a hash map at all.

BetterDirect-Address Array

Time O(1) per opSpace O(U), U = 10⁶+1

Keys are small non-negative integers, so the key itself can be the index. An int[1_000_001] pre-filled with -1 answers every call with one array access; remove just writes -1 back.

Java

class MyHashMap {
    private final int[] table = new int[1_000_001];
    public MyHashMap() {
        Arrays.fill(table, -1); // -1 = no mapping
    }
    public void put(int key, int value) { table[key] = value; }
    public int get(int key) { return table[key]; }
    public void remove(int key) { table[key] = -1; }
}

Worst-case O(1), but ~4 MB even for one key, and impossible for large or negative keys.

OptimalSeparate Chaining with Resizing

Time O(1) average per opSpace O(n)

An array of bucket heads; each bucket is a singly linked list of Node(key, value). The index is a mixed hash masked to the power-of-two capacity. When size exceeds 3/4 of the capacity, the array doubles and all nodes are re-linked, so chains stay short and memory grows only with n.

Java

class MyHashMap {
    private class Node {
        int key, val; Node next;
        Node(int k, int v, Node n) { key = k; val = v; next = n; }
    }
    private Node[] buckets = new Node[16]; // capacity is always a power of two
    private int size = 0;
    public MyHashMap() {}
    private int index(int key, int cap) {
        return (key ^ (key >>> 16)) & (cap - 1); // spread high bits, then mask
    }
    public void put(int key, int value) {
        int i = index(key, buckets.length);
        for (Node n = buckets[i]; n != null; n = n.next) {
            if (n.key == key) { n.val = value; return; } // overwrite
        }
        buckets[i] = new Node(key, value, buckets[i]); // insert at chain head
        if (++size > buckets.length * 3 / 4) resize();
    }
    public int get(int key) {
        for (Node n = buckets[index(key, buckets.length)]; n != null; n = n.next) {
            if (n.key == key) return n.val;
        }
        return -1;
    }
    public void remove(int key) {
        int i = index(key, buckets.length);
        Node prev = null, cur = buckets[i];
        while (cur != null && cur.key != key) { prev = cur; cur = cur.next; }
        if (cur == null) return;
        if (prev == null) buckets[i] = cur.next; // removing the head
        else prev.next = cur.next;
        size--;
    }
    private void resize() {
        Node[] old = buckets;
        buckets = new Node[old.length * 2];
        for (Node head : old) {
            Node n = head;
            while (n != null) { // move each node into its new bucket
                Node next = n.next;
                int i = index(n.key, buckets.length);
                n.next = buckets[i];
                buckets[i] = n;
                n = next;
            }
        }
    }
}

Memory proportional to the data and works for any key range — the real design answer.

Pro tip

Name the alternatives: open addressing (linear probing) needs tombstones for remove; chaining keeps deletion simple.

At a glance

Level	Approach	Time	Space
Brute Force	Unsorted List of Pairs	`O(n) per op`	`O(n)`
Better	Direct-Address Array	`O(1) per op`	`O(U), U = 10⁶+1`
Optimal	Separate Chaining with Resizing	`O(1) average per op`	`O(n)`

Common pitfalls

put on an existing key appending a second entry instead of overwriting.
Losing the rest of a chain when removing its head node.
Negative indexes from hashCode() % cap — mask or use Math.floorMod.

Interview tips

Clarify key range and call count first — it justifies or rules out direct addressing.
Talk about load factor and resizing; a fixed bucket count degrades to O(n).
Compare chaining with open addressing and their trade-offs.

Pattern

Hash table design → buckets + collision handling whenever you must build O(1) lookup yourself.

My notes saved in this browser