How do you solve Design HashSet?

Implement the HashSet with a fixed number of buckets (a prime number to reduce collisions). Use the modulo of the key to determine the bucket index. For add, check if the key is already in the bucket; if not, append it. For remove, check if the key is in the bucket and remove it. For contains, check membership in the bucket. This design achieves average O(1) time per operation with O(n) space proportional to the number of keys stored.

What pattern does Design HashSet use?

The Pattern: Hash Maps (Separate Chaining with Buckets) The Heuristic: Use a fixed-size array of buckets indexed by a hash function (modulo) to distribute keys evenly, and store colliding keys in lists within each bucket to maintain efficient average-case operations.

Design HashSet | Hash Maps

Q: What is the time complexity of Design HashSet?

O(1) average per operation. Each operation computes the bucket index in O(1) time and performs a membership check or update in a small list. Assuming uniform distribution, bucket sizes remain small, making these operations average O(1).

Problem

Design a HashSet without using any built-in hash table libraries, supporting add, remove, and contains operations for integer keys.

0 ≤ key ≤ 10⁶
At most 10⁴ calls will be made to add, remove, and contains.

Example

Input: add(1), add(2), contains(1), contains(3), add(2), contains(2), remove(2), contains(2)

Output: [null, null, true, false, null, true, null, false]

Initially, the set is empty. After add(1) and add(2), contains(1) returns true because 1 was added. contains(3) returns false because 3 was never added. add(2) again does not change the set. contains(2) returns true. remove(2) deletes 2 from the set. Finally, contains(2) returns false because 2 was removed.

Approach

Straightforward Solution

A naive approach is to store keys in a list and perform linear scans for add, remove, and contains operations, resulting in O(n) time per operation, which is inefficient for large inputs.

Core Observation

A HashSet stores unique keys and supports fast insertion, deletion, and membership queries. The fundamental principle is to distribute keys uniformly across buckets using a hash function to achieve average O(1) time complexity for these operations.

Path to Optimal

Preview

The key recognition signals are 'store unique keys', 'support add/remove/contains', and 'no built-in hash table'. These indicate implementing a hash map with separate chaining using buckets…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Implement the HashSet with a fixed number of buckets (a prime number to reduce collisions). Use the modulo of the key to determine the bucket index…

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

Each operation computes the bucket index in O(1) time and performs a membership check or update in a small list. Assuming uniform distribution, bucket sizes remain small, making these operations average O(1).

Space

O(n)

Space grows linearly with the number of unique keys stored, as each key is stored exactly once in one of the buckets.

Solution

Python

1class MyHashSet:
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 add(self, key: int) -> None:
12        bucket = self._get_bucket(key)
13
14        if key not in bucket:
15            bucket.append(key)
16
17    def remove(self, key: int) -> None:
18        bucket = self._get_bucket(key)
19
20        if key in bucket:
21            bucket.remove(key)
22
23    def contains(self, key: int) -> bool:
24        bucket = self._get_bucket(key)
25        return key in bucket

Step-by-Step Solution

1

Initialize Buckets Array with Fixed Prime Size

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

Objective

To create a fixed-size array of empty buckets to store keys, enabling efficient hashing and collision handling.

Key Insight

Choosing a prime number for the bucket count helps distribute keys uniformly when using modulo hashing. Initializing each bucket as an empty list prepares the data structure for separate chaining, where each bucket handles collisions by storing multiple keys.

Interview Quick-Check

Core Logic

Buckets are initialized as a list of empty lists, each representing a chain to handle collisions.

Common Pitfalls & Bugs

Choosing a non-prime bucket count can lead to poor key distribution and increased collisions.

2

Compute Bucket Index Using Modulo Hash Function

To map any given key to its corresponding bucket index using a simple and fast hash function.

3

Add Key to Bucket if Not Present

To insert a key into its bucket only if it is not already present, maintaining set uniqueness.

4

Remove Key from Bucket if Present

To delete a key from its bucket if it exists, enabling efficient removal from the HashSet.

5

Check Key Membership in Bucket

To determine if a key exists in the HashSet by checking its bucket.

4 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical

bucket_index = key % self.bucket_count

Calculate the bucket index by taking key modulo bucket_count.

Modulo operation ensures the bucket index is within valid bounds and distributes keys evenly across buckets.

Line 14 Critical

if key not in bucket:

Check if the key is not already in the bucket before adding.

Preventing duplicates preserves the set property that each key appears only once.

Line 25 Critical

return key in bucket

Return whether the key is present in the bucket.

This membership test determines if the key exists in the HashSet, fulfilling the contains operation.

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

Test Your Understanding

Why does using a modulo operation with a prime number of buckets help maintain efficient average-case performance?

See the answer with Pro.

Don't just read it. Drill it.

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

Unlock the Design HashSet drill

or drill a free problem

1	`class MyHashSet:`
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 add(self, key: int) -> None:`
12	`bucket = self._get_bucket(key)`
13
14	`if key not in bucket:`
15	`bucket.append(key)`
16
17	`def remove(self, key: int) -> None:`
18	`bucket = self._get_bucket(key)`
19
20	`if key in bucket:`
21	`bucket.remove(key)`
22
23	`def contains(self, key: int) -> bool:`
24	`bucket = self._get_bucket(key)`
25	`return key in bucket`