Design HashSet
Easy · Arrays & Hashing · Array · Hash Table · Linked List · Design · Hash Function
Problem
Build your own hash set without using any built-in hash table library.
Implement MyHashSet:
- MyHashSet() creates an empty set.
- void add(int key) inserts key. Adding a key that is already present has no effect.
- bool contains(int key) returns whether key is in the set.
- void remove(int key) deletes key. If it is not present, nothing happens.
The tests call the class through a list of operation names and a list of their arguments; each call's return value is collected, with None for the constructor and the void methods.
Examples
Input: ops = ["MyHashSet","add","add","contains","contains","remove","contains"], args = [[],[4],[9],[4],[5],[4],[4]] Output: [null,null,null,true,false,null,false]
4 is found until it is removed; 5 was never added.
Input: ops = ["MyHashSet","remove","add","add","contains"], args = [[],[3],[3],[3],[3]] Output: [null,null,null,null,true]
Removing a missing key does nothing, and adding 3 twice still stores it once.
Input: ops = ["MyHashSet","add","add","remove","contains","contains"], args = [[],[7],[1016],[7],[7],[1016]] Output: [null,null,null,null,false,true]
7 and 1016 share a bucket of 1009; removing 7 must leave 1016 in place.
Constraints
- 0 <= key <= 10^6
- At most 10^4 calls are made to add, remove and contains
Approaches
- Baseline: one list of keys — time O(k) per call, space O(k)
Follow-up
If the number of keys were not known in advance, track the load factor (keys per bucket) and, when it passes about 0.75, double the bucket array and re-insert every key, so each add stays O(1) amortized. Open addressing is the other classic design: one flat array, and on a collision you probe the next slots; deletions then need a "deleted" marker so later searches do not stop early.
Related problems
Start free on Cariara · Coding problems · System design studio
