Design a HashMap from Scratch: DSA & System Design

A hashmap is an array of buckets plus a hash function that decides which bucket a key lands in.

The whole design in one line:

index = hash(key) % bucketCount — collisions are handled by chaining entries inside the bucket.

Focus on recognizing:

“Implement without built-in hash” = array of buckets + chain walk

Core Template

class MyHashMap {
    private static final int SIZE = 1009;   // prime-ish size spreads keys
    private List<int[]>[] buckets;

    public MyHashMap() {
        buckets = new List[SIZE];
    }

    private int hash(int key) {
        return key % SIZE;
    }

    public void put(int key, int value) {
        List<int[]> chain = buckets[hash(key)];
        if (chain == null) chain = buckets[hash(key)] = new ArrayList<>();

        for (int[] entry : chain)
            if (entry[0] == key) { entry[1] = value; return; }

        chain.add(new int[]{key, value});
    }

    public int get(int key) {
        List<int[]> chain = buckets[hash(key)];
        if (chain == null) return -1;

        for (int[] entry : chain)
            if (entry[0] == key) return entry[1];

        return -1;
    }

    public void remove(int key) {
        List<int[]> chain = buckets[hash(key)];
        if (chain == null) return;

        chain.removeIf(entry -> entry[0] == key);
    }
}

class MyHashMap:
    def __init__(self):
        self.size = 1009
        self.buckets = [[] for _ in range(self.size)]

    def _hash(self, key):
        return key % self.size

    def put(self, key: int, value: int) -> None:
        chain = self.buckets[self._hash(key)]
        for entry in chain:
            if entry[0] == key:
                entry[1] = value
                return
        chain.append([key, value])

    def get(self, key: int) -> int:
        for entry in self.buckets[self._hash(key)]:
            if entry[0] == key:
                return entry[1]
        return -1

    def remove(self, key: int) -> None:
        chain = self.buckets[self._hash(key)]
        for i, entry in enumerate(chain):
            if entry[0] == key:
                del chain[i]
                return

class MyHashMap {
    static constexpr int SIZE = 1009;
    vector<vector<pair<int, int>>> buckets{SIZE};

    int hash(int key) const { return key % SIZE; }

public:
    MyHashMap() {}

    void put(int key, int value) {
        auto& chain = buckets[hash(key)];
        for (auto& [k, v] : chain)
            if (k == key) { v = value; return; }
        chain.push_back({key, value});
    }

    int get(int key) {
        for (auto& [k, v] : buckets[hash(key)])
            if (k == key) return v;
        return -1;
    }

    void remove(int key) {
        auto& chain = buckets[hash(key)];
        for (auto it = chain.begin(); it != chain.end(); ++it)
            if (it->first == key) { chain.erase(it); return; }
    }
};

class MyHashMap {
  #size = 1009;
  #buckets = Array.from({ length: this.#size }, () => []);

  #hash(key) {
    return key % this.#size;
  }

  put(key, value) {
    const chain = this.#buckets[this.#hash(key)];
    const entry = chain.find(([k]) => k === key);
    if (entry) entry[1] = value;
    else chain.push([key, value]);
  }

  get(key) {
    const entry = this.#buckets[this.#hash(key)].find(
      ([k]) => k === key,
    );
    return entry ? entry[1] : -1;
  }

  remove(key) {
    const chain = this.#buckets[this.#hash(key)];
    const i = chain.findIndex(([k]) => k === key);
    if (i !== -1) chain.splice(i, 1);
  }
}

Store the full key in each entry — the hash alone can’t distinguish colliding keys.

Pattern: Resizing

Watch five puts fill four buckets, collide on 14, and resolve by chaining — then get(14) walks the chain. Press ▶ to animate.

HashMap with Buckets

Map keys to values using hash % buckets with chaining.

index = hash(key) % bucketCount. put walks the bucket's chain — overwrite if the key exists, else append; get walks comparing full keys and returns the value or a miss. Collisions live in the same row's chain.

HASH BUCKETS VISUALIZER

Steps –

bucket 0

∅

bucket 1

∅

bucket 2

∅

bucket 3

∅

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        index = hash(key) % bucketCount
                      
                        2
                        put: walk chain — overwrite if key exists, else append
                      
                        3
                        get: walk chain comparing full keys, return value or miss
                      
                        4
                        resize (rehash all) when size / buckets exceeds load factor

Chains grow → lookups degrade to O(n). Fix by doubling the bucket count when size / buckets crosses a load factor (~0.75):

resize(): re-hash EVERY entry into a bigger bucket array

Amortized O(1) per operation — same trick the built-ins use.

Hashmap = hash to bucket + chain + resize before chains get long.

Common Mistakes

Storing only values.

Two colliding keys would overwrite each other. Each entry must carry its original key for comparison.

Bucket count 0 or power-of-two-only patterns.

mod 0 crashes; poor sizes cluster keys. Pick a prime-ish constant (1009, 2069).

Forgetting update-in-place.

put on an existing key must overwrite, not duplicate the entry.

Complexity

Operation	Average	Worst (all collide)
put	O(1)	O(n)
get	O(1)	O(n)
remove	O(1)	O(n)

⚠️ Animation & Content Notice

Design a HashMap

Core Template

Pattern: Resizing

⚠️ Animation & Content Notice

HashMap with Buckets

Common Mistakes

Complexity

Premium Content

My Private Notes

Earn Premium with Referrals

Core Template

Pattern: Resizing

HashMap with Buckets

Common Mistakes

Complexity

Premium Content

My Private Notes