Design HashSet
Design HashSet is a easy design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (separate chaining), runs in O(1) average per operation time and O(B + n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (one list of keys) up.
Problem
Build your own hash set for integer keys without using any built-in hash table or hash set library. Implement the class MyHashSet:
MyHashSet()creates an empty set.void add(int key)insertskey(adding a key that is already present has no effect).void remove(int key)deleteskeyif it is present; otherwise nothing happens.boolean contains(int key)returns whetherkeyis currently in the set.
Examples
Example 1
- Input
add(4), add(9), contains(4), contains(5), add(4), remove(4), contains(4), contains(9)- Output
true, false, false, true- Why
- Adding 4 a second time changes nothing, and after one remove it is gone while 9 stays.
Example 2
- Input
remove(0), add(0), contains(0), remove(0), remove(0), contains(0)- Output
true, false- Why
- Removing a key that is not in the set is allowed and does nothing; 0 is an ordinary key.
Constraints
0 <= key <= 10^6- At most
10^4calls in total toadd,removeandcontains. - Do not use a built-in hash set or hash table library.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (one list of keys) | O(n) per operation | O(n) |
| Better (direct addressing) | O(1) per operation | O(U), U = 10^6 + 1 |
| Optimal (separate chaining) | O(1) average per operation | O(B + n) |
1Brute force (one list of keys)
O(n) per operationA scan may visit all n stored keys.O(n)One slot per stored key.Store every key once in a single dynamic list. Each operation scans the whole list for the key.
- add: if the key is not already in the list, append it.
- remove: find the key and delete it if present.
- contains: scan the list and report whether the key was found.
class MyHashSet {
private final List<Integer> keys = new ArrayList<>();
public MyHashSet() {}
public void add(int key) {
if (!contains(key)) keys.add(key);
}
public void remove(int key) {
keys.remove(Integer.valueOf(key));
}
public boolean contains(int key) {
for (int k : keys) if (k == key) return true;
return false;
}
}class MyHashSet:
def __init__(self):
self.keys = []
def add(self, key: int) -> None:
if not self.contains(key):
self.keys.append(key)
def remove(self, key: int) -> None:
for i, k in enumerate(self.keys):
if k == key:
self.keys.pop(i)
return
def contains(self, key: int) -> bool:
for k in self.keys:
if k == key:
return True
return Falseclass MyHashSet {
vector<int> keys;
public:
MyHashSet() {}
void add(int key) {
if (!contains(key)) keys.push_back(key);
}
void remove(int key) {
for (size_t i = 0; i < keys.size(); i++) {
if (keys[i] == key) { keys.erase(keys.begin() + i); return; }
}
}
bool contains(int key) {
for (int k : keys) if (k == key) return true;
return false;
}
};class MyHashSet {
constructor() {
this.keys = [];
}
add(key) {
if (!this.contains(key)) this.keys.push(key);
}
remove(key) {
const i = this.keys.indexOf(key);
if (i !== -1) this.keys.splice(i, 1);
}
contains(key) {
for (const k of this.keys) if (k === key) return true;
return false;
}
}2Better (direct addressing)
O(1) per operationEach call is one array read or write.O(U), U = 10^6 + 1The array covers the whole key universe regardless of how many keys are stored.Keys are integers in [0, 10^6], so a boolean array with one slot per possible key answers every call with a single array access. The price is memory for all possible keys, even if only a few are ever stored.
- Allocate a boolean array of size 10^6 + 1, all false.
- add sets
present[key] = true; remove sets it to false. - contains returns
present[key].
class MyHashSet {
private final boolean[] present = new boolean[1_000_001];
public MyHashSet() {}
public void add(int key) { present[key] = true; }
public void remove(int key) { present[key] = false; }
public boolean contains(int key) { return present[key]; }
}class MyHashSet:
def __init__(self):
self.present = [False] * 1_000_001
def add(self, key: int) -> None:
self.present[key] = True
def remove(self, key: int) -> None:
self.present[key] = False
def contains(self, key: int) -> bool:
return self.present[key]class MyHashSet {
vector<bool> present;
public:
MyHashSet() : present(1000001, false) {}
void add(int key) { present[key] = true; }
void remove(int key) { present[key] = false; }
bool contains(int key) { return present[key]; }
};class MyHashSet {
constructor() {
this.present = new Uint8Array(1000001);
}
add(key) { this.present[key] = 1; }
remove(key) { this.present[key] = 0; }
contains(key) { return this.present[key] === 1; }
}3Optimal (separate chaining)
O(1) average per operationWith n keys over B buckets each bucket holds about n / B keys, which is constant when B is at least the number of keys.O(B + n)B bucket headers plus one entry per stored key.Keep a fixed number B of buckets (a prime such as 10007). Key k belongs to bucket k % B, which is a short list. Every call only scans that one bucket, so with keys spread evenly each call touches O(1) entries on average while memory grows with the number of stored keys rather than with the key range.
- Create B empty bucket lists.
- add: look in bucket
key % B; append the key only if it is not there. - remove: delete the key from bucket
key % Bif present. - contains: scan bucket
key % Bfor the key.
class MyHashSet {
private static final int B = 10007;
private final List<List<Integer>> buckets = new ArrayList<>();
public MyHashSet() {
for (int i = 0; i < B; i++) buckets.add(new LinkedList<>());
}
public void add(int key) {
List<Integer> bucket = buckets.get(key % B);
if (!bucket.contains(key)) bucket.add(key);
}
public void remove(int key) {
buckets.get(key % B).remove(Integer.valueOf(key));
}
public boolean contains(int key) {
return buckets.get(key % B).contains(key);
}
}class MyHashSet:
B = 10007
def __init__(self):
self.buckets = [[] for _ in range(self.B)]
def add(self, key: int) -> None:
bucket = self.buckets[key % self.B]
if key not in bucket:
bucket.append(key)
def remove(self, key: int) -> None:
bucket = self.buckets[key % self.B]
if key in bucket:
bucket.remove(key)
def contains(self, key: int) -> bool:
return key in self.buckets[key % self.B]class MyHashSet {
static const int B = 10007;
vector<list<int>> buckets;
public:
MyHashSet() : buckets(B) {}
void add(int key) {
if (!contains(key)) buckets[key % B].push_back(key);
}
void remove(int key) {
buckets[key % B].remove(key);
}
bool contains(int key) {
for (int k : buckets[key % B]) if (k == key) return true;
return false;
}
};class MyHashSet {
constructor() {
this.B = 10007;
this.buckets = Array.from({ length: this.B }, () => []);
}
add(key) {
const bucket = this.buckets[key % this.B];
if (!bucket.includes(key)) bucket.push(key);
}
remove(key) {
const bucket = this.buckets[key % this.B];
const i = bucket.indexOf(key);
if (i !== -1) bucket.splice(i, 1);
}
contains(key) {
return this.buckets[key % this.B].includes(key);
}
}Edge cases to test
- Adding the same key twice (the set must still hold it once)
- Removing a key that is not present
- Key 0 and key 10^6, the two ends of the range
- Keys that fall into the same bucket, such as k and k + B
- Adding a key again after it was removed
Hints
Hint 1
Start with the simplest structure that works: a plain list of the stored keys. How expensive is each call?
Hint 2
Since keys are small non-negative integers, you could index an array directly by the key. What does that cost in memory?
Hint 3
To use memory in proportion to the keys actually stored, split them into B buckets chosen by key % B and scan only one bucket per call.
FAQ
What is the best time complexity for Design HashSet?
Optimal (separate chaining) runs in O(1) average per operation time and O(B + n) extra space. With n keys over B buckets each bucket holds about n / B keys, which is constant when B is at least the number of keys.
Which pattern does Design HashSet use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Design HashSet?
Yes. Brute force (one list of keys) takes O(n) per operation time and O(n) space. Store every key once in a single dynamic list.
Which edge cases should I test for Design HashSet?
Adding the same key twice (the set must still hold it once); Removing a key that is not present; Key 0 and key 10^6, the two ends of the range; Keys that fall into the same bucket, such as k and k + B; Adding a key again after it was removed.