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).
The most straightforward approach is to use a simple list or dynamic array to store the unique keys. When an operation is requested, we can iterate through the list to perform the necessary action.
Algorithm
- Data Structure: A
List<Integer>is used to store the elements of the set. add(key):- First, check if the key already exists by iterating through the list (
O(N)). - If the key is not found, append it to the end of the list (
O(1)amortized).
- First, check if the key already exists by iterating through the list (
remove(key):- Find the key in the list by linear search (
O(N)). - If found, remove it. Removing an element from an
ArrayListby value or index is also anO(N)operation as subsequent elements need to be shifted.
- Find the key in the list by linear search (
contains(key):- Perform a linear scan of the list (
O(N)). - Return
trueif the key is found, otherwisefalse.
- Perform a linear scan of the list (
Walkthrough
In this method, we use a java.util.List as the underlying data store.
- For the
add(key)operation, we must first ensure the key is not already present to maintain the uniqueness property of a set. This requires scanning the entire list. If the key is not found, we add it. - For the
contains(key)operation, we simply scan the list and returntrueif we find the key. - For the
remove(key)operation, we scan the list to find the key. If it exists, we remove it.
All these operations rely on a linear scan, making them slow.
import java.util.ArrayList;import java.util.List; class MyHashSet { private List<Integer> set; /** Initialize your data structure here. */ public MyHashSet() { set = new ArrayList<>(); } public void add(int key) { if (!this.contains(key)) { set.add(key); } } public void remove(int key) { // List.remove(Object) internally performs a search, which is O(N). set.remove(Integer.valueOf(key)); } /** Returns true if this set contains the specified element */ public boolean contains(int key) { // List.contains() is an O(N) operation. return set.contains(key); }}Complexity
Time
O(N) for `add`, `remove`, and `contains` operations, where N is the number of elements currently in the set. Each operation may require iterating through the entire list.
Space
O(N), where N is the number of unique keys inserted into the HashSet. We only store the keys that are actually added.
Trade-offs
Pros
Simple to understand and implement.
Space complexity is proportional to the number of elements stored, not the range of keys.
Cons
Very inefficient time complexity (
O(N)) for all operations.Does not scale well with the number of elements.
A classic and highly practical approach is to use hashing with a technique called 'separate chaining' to handle collisions. We maintain an array of 'buckets', and a hash function determines which bucket a key belongs to. Each bucket is typically a linked list containing all the keys that have hashed to that same bucket index.
Algorithm
- Data Structure: An array of lists (or another data structure like a balanced binary search tree), often called buckets.
- Hash Function: A function to map a key to a bucket index. A simple choice is
hash(key) = key % array_size. add(key):- Compute the index
i = hash(key). - Go to the bucket at
buckets[i]. - Search the list in this bucket for the key. If not found, add the key to this list.
- Compute the index
remove(key):- Compute the index
i = hash(key). - Go to the bucket at
buckets[i]. - Search for and remove the key from the list in this bucket.
- Compute the index
contains(key):- Compute the index
i = hash(key). - Go to the bucket at
buckets[i]. - Search the list in this bucket for the key and return the result.
- Compute the index
Walkthrough
This method balances time and space complexity. Instead of one long list, we use an array of smaller lists (buckets).
First, we choose a size for our bucket array, preferably a prime number to help with key distribution. Let's say SIZE = 1000. The hash function will map a key to an index within this array, e.g., index = key % SIZE.
When an operation on a key is requested, we first use the hash function to locate the bucket. Then, we perform the operation (add, remove, or search) only on the small list within that bucket. If the hash function distributes keys evenly, the lists in each bucket will be short, making operations very fast on average.
import java.util.LinkedList;import java.util.List; class MyHashSet { private final int BUCKET_SIZE = 1000; private List<Integer>[] buckets; /** Initialize your data structure here. */ public MyHashSet() { buckets = new LinkedList[BUCKET_SIZE]; for (int i = 0; i < BUCKET_SIZE; i++) { buckets[i] = new LinkedList<>(); } } private int hash(int key) { return key % BUCKET_SIZE; } public void add(int key) { int index = hash(key); List<Integer> bucket = buckets[index]; if (!bucket.contains(key)) { bucket.add(key); } } public void remove(int key) { int index = hash(key); List<Integer> bucket = buckets[index]; bucket.remove(Integer.valueOf(key)); } /** Returns true if this set contains the specified element */ public boolean contains(int key) { int index = hash(key); List<Integer> bucket = buckets[index]; return bucket.contains(key); }}Complexity
Time
Average Case: O(N/K), where N is the number of elements and K is the number of buckets. If K is proportional to N, this is O(1). Worst Case: O(N), if all keys hash to the same bucket.
Space
O(N + K), where N is the number of elements in the set and K is the number of buckets. This is efficient when the number of keys is much smaller than the key range.
Trade-offs
Pros
Excellent average-case time complexity, approaching O(1).
Space-efficient, as it uses memory proportional to the number of items stored plus the bucket array size (
O(N + K)).
Cons
Worst-case time complexity can be O(N) if many keys hash to the same bucket (high collisions).
Performance is sensitive to the hash function and the number of buckets (load factor).
Slightly more complex to implement than the direct addressing approach.
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); */class MyHashSet { public: bool data [ 1000001 ]; MyHashSet () { memset ( data , false , sizeof data ); } void add ( int key ) { data [ key ] = true ; } void remove ( int key ) { data [ key ] = false ; } bool 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); * bool param_3 = obj->contains(key); */class MyHashSet : def __init__ ( self ): self . data = [ False ] * 1000001 def add ( self , key : int ) -> None : self . data [ key ] = True def remove ( self , key : int ) -> None : self . data [ key ] = False def contains ( self , key : int ) -> bool : return self . data [ key ] # Your MyHashSet object will be instantiated and called as such: # obj = MyHashSet() # obj.add(key) # obj.remove(key) # param_3 = obj.contains(key) ############### class MyHashSet : # hash to bucket def __init__ ( self ): """ Initialize your data structure here. """ self . size = 1000 # Choosing a size for the outer list self . buckets = [[] for _ in range ( self . size )] # List of lists def _hash ( self , key : int ) -> int : """ Generate a hash for a given key. """ return key % self . size def add ( self , key : int ) -> None : """ Insert a value into the HashSet. """ hash_key = self . _hash ( key ) if key not in self . buckets [ hash_key ]: self . buckets [ hash_key ]. append ( key ) def remove ( self , key : int ) -> None : """ Remove a value in the HashSet. If the value does not exist, do nothing. """ hash_key = self . _hash ( key ) if key in self . buckets [ hash_key ]: self . buckets [ hash_key ]. remove ( key ) def contains ( self , key : int ) -> bool : """ Returns true if this set contains the specified element. """ hash_key = self . _hash ( key ) return key in self . buckets [ hash_key ] # Your MyHashSet object will be instantiated and called as such: # obj = MyHashSet() # obj.add(key) # obj.remove(key) # param_3 = obj.contains(key) ############ # Collision handling, optimized class MyHashSet : def __init__ ( self ): self . capacity = 1000 self . data = [ None ] * self . capacity self . load_factor = 0.7 self . size = 0 def _hash ( self , key ): return key % self . capacity def _resize ( self ): if self . size / self . capacity >= self . load_factor : self . capacity *= 2 old_data = self . data self . data = [ None ] * self . capacity self . size = 0 for item in old_data : if item is not None : self . add ( item ) def add ( self , key : int ) -> None : if self . contains ( key ): return self . _resize () idx = self . _hash ( key ) while self . data [ idx ] is not None : idx = ( idx + 1 ) % self . capacity # Collision handling self . data [ idx ] = key self . size += 1 def remove ( self , key : int ) -> None : idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] == key : self . data [ idx ] = "DEL" # Mark as deleted self . size -= 1 return idx = ( idx + 1 ) % self . capacity def contains ( self , key : int ) -> bool : idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] == key : return True idx = ( idx + 1 ) % self . capacity return FalseVideo 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.