How do you solve Design HashMap?

Implement a fixed-size array of buckets (size is a prime number to reduce collisions). Use modulo hashing to map keys to buckets. Each bucket stores a list of key-value pairs. For put, search the bucket for the key and update or append. For get, search and return the value or -1. For remove, search and delete the pair if found. This yields average O(1) time per operation with O(n) space.

What pattern does Design HashMap use?

The Pattern: Hash Maps (Separate Chaining) The Heuristic: Use a fixed-size array of buckets and resolve collisions by storing all colliding key-value pairs in a list within each bucket; this transforms collision handling into a manageable linear search within a small subset.

Design HashMap | Hash Maps

Q: What is the time complexity of Design HashMap?

O(1) average per operation. With a good hash function and a sufficiently large number of buckets, the average number of elements per bucket remains low, making search, insert, and delete operations average O(1).

Problem

Design a HashMap without using any built-in hash table libraries. Implement the methods put(key, value), get(key), and remove(key) to store, retrieve, and delete key-value pairs respectively.

0 ≤ key, value ≤ 10⁶
At most 10⁴ calls will be made to put, get, and remove.

Example

Input: put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2)

Output: [null, null, 1, -1, null, 1, null, -1]

Initially, the map is empty. put(1,1) inserts key 1 with value 1. put(2,2) inserts key 2 with value 2. get(1) returns 1. get(3) returns -1 since key 3 does not exist. put(2,1) updates key 2's value to 1. get(2) returns 1. remove(2) deletes key 2. get(2) returns -1 since key 2 was removed.

Approach

Straightforward Solution

A naive approach uses a large array indexed by key, but this is infeasible due to memory constraints and sparse keys. Another naive approach is to store all pairs in a list and scan linearly, resulting in O(n) operations.

Core Observation

A HashMap stores key-value pairs and supports efficient insertion, retrieval, and deletion. Collisions occur when multiple keys hash to the same bucket, so a collision resolution strategy is necessary.

Path to Optimal

Preview

The key recognition signals are 'design a hash map', 'handle collisions', and 'efficient operations'. These indicate using an array of buckets combined with chaining (linked lists or arrays) to handle collisions…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement a fixed-size array of buckets (size is a prime number to reduce collisions). Use modulo hashing to map keys to buckets…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1) average per operation

With a good hash function and a sufficiently large number of buckets, the average number of elements per bucket remains low, making search, insert, and delete operations average O(1).

Space

O(n)

Space scales linearly with the number of stored key-value pairs, as each pair is stored exactly once in a bucket list.

Solution

Python

1class MyHashMap:
2
3    def __init__(self):
4        self.bucket_count = 1009
5        self.buckets = [[] for _ in range(self.bucket_count)]
6
7    def _get_bucket(self, key: int) -> list:
8        bucket_index = key % self.bucket_count
9        return self.buckets[bucket_index]
10
11    def put(self, key: int, value: int) -> None:
12        bucket = self._get_bucket(key)
13
14        for pair in bucket:
15            if pair[0] == key:
16                pair[1] = value
17                return
18
19        bucket.append([key, value])
20
21    def get(self, key: int) -> int:
22        bucket = self._get_bucket(key)
23
24        for stored_key, stored_value in bucket:
25            if stored_key == key:
26                return stored_value
27
28        return -1
29
30    def remove(self, key: int) -> None:
31        bucket = self._get_bucket(key)
32
33        for index, pair in enumerate(bucket):
34            if pair[0] == key:
35                bucket.pop(index)
36                return

Step-by-Step Solution

1

Initialize Buckets Array with Fixed Size for Hashing

4self.bucket_count = 1009
5self.buckets = [[] for _ in range(self.bucket_count)]

Objective

To create a fixed-size array of empty buckets to store key-value pairs and define the bucket count for hashing.

Key Insight

Choosing a prime number for bucket count reduces clustering and distributes keys more evenly across buckets. Initializing each bucket as an empty list prepares the structure for separate chaining, enabling efficient collision handling by storing multiple pairs in the same bucket.

Interview Quick-Check

Core Logic

Using a fixed-size array of buckets with separate chaining enables average O(1) operations by limiting collision scope.

Common Pitfalls & Bugs

Choosing a poor bucket count (e.g., a power of two) can increase collisions and degrade performance.

2

Map Keys to Buckets Using Modulo Hash Function

To compute the bucket index for any given key using modulo operation.

3

Insert or Update Key-Value Pair in Appropriate Bucket

To add a new key-value pair or update an existing key's value within the correct bucket.

4

Retrieve Value by Searching Bucket for Key

To find and return the value associated with a key by searching its bucket, or return -1 if not found.

5

Remove Key-Value Pair by Locating and Deleting from Bucket

To delete a key-value pair from the bucket by locating the key and removing its entry.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 9 Critical lines interviewers watch for.

Line 5 Critical

self.buckets = [[] for _ in range(self.bucket_count)]

Initialize the buckets as a list of empty lists for separate chaining.

Each bucket is an independent list that stores key-value pairs, enabling collision resolution by chaining multiple pairs in the same bucket.

Line 8 Critical

bucket_index = key % self.bucket_count

Calculate the bucket index by taking key modulo bucket count.

Modulo operation maps keys to valid bucket indices, ensuring keys are distributed within the fixed bucket array.

Line 15 Critical

if pair[0] == key:

Check if the current pair's key matches the input key.

Identifying the correct pair is necessary to update its value instead of appending a duplicate.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why is separate chaining with a fixed-size bucket array an effective collision resolution strategy for a hash map?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Design HashMap from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Design HashMap drill

or drill a free problem

1	`class MyHashMap:`
2
3	`def __init__(self):`
4	`self.bucket_count = 1009`
5	`self.buckets = [[] for _ in range(self.bucket_count)]`
6
7	`def _get_bucket(self, key: int) -> list:`
8	`bucket_index = key % self.bucket_count`
9	`return self.buckets[bucket_index]`
10
11	`def put(self, key: int, value: int) -> None:`
12	`bucket = self._get_bucket(key)`
13
14	`for pair in bucket:`
15	`if pair[0] == key:`
16	`pair[1] = value`
17	`return`
18
19	`bucket.append([key, value])`
20
21	`def get(self, key: int) -> int:`
22	`bucket = self._get_bucket(key)`
23
24	`for stored_key, stored_value in bucket:`
25	`if stored_key == key:`
26	`return stored_value`
27
28	`return -1`
29
30	`def remove(self, key: int) -> None:`
31	`bucket = self._get_bucket(key)`
32
33	`for index, pair in enumerate(bucket):`
34	`if pair[0] == key:`
35	`bucket.pop(index)`
36	`return`