Community Problem

Design HashMap

Difficulty: Medium

Implement a HashMap from scratch using a fixed bucket array with separate chaining; support put / get / remove on integer keys.

Design HashMap

Implement a HashMap from scratch using a fixed bucket array with separate chaining; support put / get / remove on integer keys.

MEDIUM

Free

hash-map

hash-table

linked-list

By @chloekelly

May 11, 2026

Updated May 18, 2026

312 views

4.3 (9)

I had this on a Reddit infrastructure phone screen as the warm-up before a system-design round. The interviewer specifically said "don't use the language's built-in map, build it." The standard production-ready answer is a fixed bucket array with separate chaining (one list per bucket), and it's worth practicing the chaining idea before you ever touch consistent hashing or open addressing.

Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(int key) removes the key and its corresponding value if the map contains the mapping for the key.

Examples

Example 1:

MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1);    // map = {1=1}
myHashMap.put(2, 2);    // map = {1=1, 2=2}
myHashMap.get(1);       // returns 1
myHashMap.get(3);       // returns -1 (not found)
myHashMap.put(2, 1);    // map = {1=1, 2=1} (update existing)
myHashMap.get(2);       // returns 1
myHashMap.remove(2);    // map = {1=1}
myHashMap.get(2);       // returns -1 (now removed)

Constraints

0 <= key, value <= 10^6.
At most 10^4 calls will be made to put, get, and remove.

Follow-up

Why a fixed-size bucket array with chaining? It is the simplest correct design and decouples bucket count from element count. With 10^4 operations and 1000 buckets, average chain length stays around 10, well below O(n) worst case.

Solution

JavaScript

Python

Hints

0/3

Hint 1

Hint 2

Hint 3

Solution Walkthrough

Approach: Bucket Array + Separate Chaining (O(1) average per op, O(n) worst-case)

Use a fixed-size array of buckets, each holding a list of [key, value] pairs. The hash function maps a key to a bucket index by key % BUCKET_COUNT. Inside the bucket, scan linearly to find the matching key. Collisions are tolerated by storing multiple pairs in the same bucket (separate chaining).

Key Insight

Text

Layout for BUCKET_COUNT = 5 after put(1,a), put(6,b), put(2,c)
   bucket 0:  []
   bucket 1:  [[1, a], [6, b]]    <- 1 % 5 == 6 % 5 == 1, chain length 2
   bucket 2:  [[2, c]]
   bucket 3:  []
   bucket 4:  []

With BUCKET_COUNT = 1009 (a prime) and at most 10^4 operations, the average chain length is around 10 and worst-case ops stay well under the time limit.

Algorithm

For put(key, value):

Compute idx = key % BUCKET_COUNT.
Scan buckets[idx] for an existing pair with the same key; if found, overwrite and return.
Otherwise append [key, value] to the bucket.

For get(key):

Scan buckets[key % BUCKET_COUNT] for the key; return its value or -1.

For remove(key):

Scan buckets[key % BUCKET_COUNT]; if found, splice/pop the pair.

Why It Works

Separate chaining handles collisions cleanly: the bucket holds whatever pairs hash there, and the linear scan inside a bucket is correct as long as we treat each pair's first slot as the key. Choosing a prime BUCKET_COUNT (1009) reduces clustering for keys with regular patterns. Because each operation does one hash plus a bucket scan, average cost is O(n / BUCKET_COUNT) = O(1) under the stated constraints.

Complexity

Text

Metric         Value
Time (avg)     O(1) per op
Time (worst)   O(n) per op (all keys collide)
Space          O(BUCKET_COUNT + n)

Pitfalls

Using a JS Map keyed by a hash value. Defeats the exercise (Map is itself a hash table). Use a plain array of arrays.
Iterating buckets with for...of in JS Sandpack. for...of on plain arrays is safe; the trap is using Map or Set as your storage. Stay with arrays.
Forgetting the update path. put(2, 2); put(2, 1); should leave get(2) == 1, not 2. Always scan first and overwrite if the key exists.
Returning null or undefined from get. The contract is -1 when missing; that exact sentinel is what the tests check.
Resizing buckets. Out of scope for this problem. A real production map would track load factor and rehash, but the constraints don't require it.

Solution Code

All Problems