Skip to main content

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 Alex Chen, Founder, InterviewChamp.AI · Last verified

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

Related problems

Asked at

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

  • Amazon
  • Apple
  • Google
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Design HashMap and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →