Design HashSet
EasyPrompt
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key)Inserts the valuekeyinto the HashSet.bool contains(key)Returns whether the valuekeyexists in the HashSet or not.void remove(key)Removes the valuekeyin the HashSet. Ifkeydoes not exist in the HashSet, do nothing.
Example 1:
Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]
Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // return False, (already removed)
Constraints:
0 <= key <= 106- At most
104calls will be made toadd,remove, andcontains.
Approaches
3 approaches with complexity analysis and trade-offs.
Given the problem's constraint that keys are in the range [0, 10^6], the most time-efficient solution is to use a direct addressing table. We can use a large boolean array where the index of the array represents the key, and the value at that index indicates whether the key is present in the set.
Algorithm
- Data Structure: A boolean array of a fixed size, large enough to cover the entire range of possible key values.
- Initialization: Create a boolean array
dataof size10^6 + 1and initialize all its values tofalse. add(key): Set the element at the index corresponding to the key to true:data[key] = true;.remove(key): Set the element at the index corresponding to the key to false:data[key] = false;.contains(key): Return the boolean value at the index corresponding to the key:return data[key];.
Walkthrough
This approach leverages the constraint on the key's range to achieve constant time operations. We allocate a boolean array with a size equal to the maximum possible key value plus one (1000001).
Each index i in this array corresponds to the key i. If data[i] is true, it means key i is in our set. If it's false, it's not.
add(key)becomes a simple assignment:data[key] = true.remove(key)is also a simple assignment:data[key] = false.contains(key)is a direct lookup:return data[key].
All these are array access operations by index, which are O(1).
class MyHashSet { private boolean[] data; /** Initialize your data structure here. */ public MyHashSet() { // Constraint: 0 <= key <= 10^6 data = new boolean[1000001]; } public void add(int key) { data[key] = true; } public void remove(int key) { data[key] = false; } /** Returns true if this set contains the specified element */ public boolean contains(int key) { return data[key]; }}Complexity
Time
O(1) for `add`, `remove`, and `contains`. Each operation is a single array access.
Space
O(M), where M is the maximum value of the key. For this problem, it's O(10^6), which is a constant but large amount of space.
Trade-offs
Pros
Extremely fast with guaranteed O(1) time complexity for all operations.
Very simple to implement.
Cons
High space consumption. The memory usage depends on the maximum possible key value, not the number of elements stored.
Impractical if the range of keys is very large (e.g., all possible integer values).
Solutions
Solution
class MyHashSet { private boolean [] data = new boolean [ 1000001 ]; public MyHashSet () { } public void add ( int key ) { data [ key ] = true ; } public void remove ( int key ) { data [ key ] = false ; } public boolean contains ( int key ) { return data [ key ]; } } /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet obj = new MyHashSet(); * obj.add(key); * obj.remove(key); * boolean param_3 = obj.contains(key); */Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.