706. Design HashMap

easy

Implement a HashMap from scratch without using built-in hash-table libraries. The clean way to demonstrate hashing + collision resolution (chaining) in a 20-minute interview block.

By Sam K., Founder, InterviewChamp.AI · Last verified 2026-05-19

Problem

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.

Constraints

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

Examples

Example 1

Input

['MyHashMap','put','put','get','get','put','get','remove','get']
[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]

Output

[null, null, null, 1, -1, null, 1, null, -1]

Explanation: MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); myHashMap.put(2, 2); myHashMap.get(1) returns 1; myHashMap.get(3) returns -1; myHashMap.put(2, 1) (update); myHashMap.get(2) returns 1; myHashMap.remove(2); myHashMap.get(2) returns -1.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Pick a bucket count B (e.g., 1000). Use buckets[key % B] to find the right chain.

Hint 2

Each bucket is a list of (key, value) pairs. Walk it for get/remove; on put, update in place if key exists else append.

Hint 3

Tradeoff: bigger B = fewer collisions but more memory. For the constraint of 10^4 ops, B around 1000 is fine.

Solution approach

Reveal approach

Open chaining. Pick a bucket count B (1000 is a fine choice for the constraints). Maintain buckets: list of length B, each entry a list of [key, value] pairs. Hash function: index = key % B. put(k, v): walk buckets[hash(k)]; if k is found, update its value; else append [k, v]. get(k): walk buckets[hash(k)]; return v if found, else -1. remove(k): walk and splice. All operations are amortized O(N / B) where N is the number of stored keys — effectively O(1) if B is well-sized. Open addressing (linear probing) is the alternative; chaining is easier to reason about under deletion. Memory is O(B + N).

Complexity

Time: amortized O(1) per op
Space: O(B + N)

Related patterns

hash-table
design
linked-list

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

Amazon
Apple
Google
Microsoft