Design HashSet
Problem Statement
Design a MyHashSet without using any built-in hash table libraries. It must support add(key), remove(key), and contains(key). add stores a key if it is not already present, remove deletes it if present, and contains reports whether the key is currently stored.
Input
A sequence of calls to MyHashSet, add(key), remove(key), and contains(key).
Output
For the constructor, add, and remove, output null. For contains, output true or false.
Constraints
- •
0 <= key <= 10^6 - •
At most 10^4 calls will be made to add, remove, and contains - •
Do not use built-in hash table libraries
Examples
Example 1
operations = [MyHashSet, add, add, contains, contains, add, contains, remove, contains], arguments = [[], [1], [2], [1], [3], [2], [2], [2], [2]]
[null, null, null, true, false, null, true, null, false]Example 2
operations = [MyHashSet, contains, add, contains, remove, contains, remove], arguments = [[], [42], [42], [42], [42], [42], [42]]
[null, false, null, true, null, false, null]Learning Objectives
- Implement set membership with a bucket array and separate chaining.
- Prevent duplicate keys from being inserted into the same set.
- Handle collisions by searching a linked list inside one bucket.
- Delete keys from a chain while preserving other keys that share the bucket.
Intuition
Pattern Recognition
A set only needs membership, not associated values. The hashing signal is the same as a map: keys come from a large range, operations must be fast, and built-in hash tables are disallowed. Use a hash function to route each key to one bucket, then handle collisions inside that bucket.
Compared with MyHashMap, each node stores only a key. That makes the design simpler, but the invariants are the same: no duplicate keys in a bucket chain, and every remove must unlink only the matching key.
Common mistakes
- ×Adding the same key multiple times and creating duplicate nodes.
- ×Assuming two keys with the same bucket index are the same key.
- ×Removing a key by clearing the whole bucket and deleting unrelated colliding keys.
- ×Forgetting that removing an absent key should be a no-op.
Algorithm Explanation
Key idea
Use an array of bucket heads. Compute key % bucketCount to choose a bucket. Each bucket is a linked list of keys that hash to that index. Membership, insertion, and deletion only inspect that one chain.
Walkthrough
With bucket count 1009, add(1) puts key 1 into bucket 1. add(1010) also lands in bucket 1, so it is linked next to key 1 instead of overwriting it. contains(1) scans bucket 1 and finds 1. remove(1010) unlinks only 1010, leaving key 1 in the same bucket. A later contains(1010) returns false.
Algorithm
- Create a fixed-size array of bucket heads.
- For every operation, compute bucketIndex = key % bucketCount.
- For contains, scan the selected bucket chain for the key.
- For add, first call the same search logic; if the key already exists, stop.
- If the key is new, prepend a node to the selected bucket.
- For remove, scan with previous and current pointers and unlink the matching node if found.
Solutions
Solution: Separate chaining hash set
The bucket array provides the first level of lookup, and each bucket chain stores keys that collide. Before adding, the chain is searched to preserve set semantics: one key appears at most once.
Step-by-step
- Hash the key to choose its bucket.
- For contains, walk that bucket's nodes until the key is found or the chain ends.
- For add, reuse membership search and return immediately if the key already exists.
- If absent, create a new node and link it at the bucket head.
- For remove, walk the chain with a previous pointer and unlink only the matching node.
Expected O(1) per operation, O(k) within one bucket
O(B + n)
B is the bucket count and n is the number of stored keys.
Java implementation
Dry Run
Sample input
Use separate chaining. Operations: add(1), add(1010), contains(1), remove(1010), contains(1010).
| operation | argument | structure state | result |
|---|---|---|---|
| add | 1 | bucket 1 contains 1 | null |
| add | 1010 | bucket 1 contains 1010 -> 1 | null |
| contains | 1 | scan bucket 1 and find 1 | true |
| remove | 1010 | unlink head, bucket 1 contains 1 | null |
| contains | 1010 | scan bucket 1 and do not find 1010 | false |
Colliding keys share a bucket but remain distinct because every node stores the original key and comparisons use equality.
Interview Tips
State that this is the key-only form of a hash table. The main edge cases are duplicate add, absent remove, and removing the first node in a bucket chain. If the interviewer asks why not allocate a huge boolean array, explain that direct addressing is constraint-specific, while hashing and chaining is the reusable implementation strategy.
Likely follow-ups
- How would you resize the set when too many keys collide?
- How would open addressing change contains and remove?
- How would you implement iteration over all keys in the set?
- How would you adapt this set to store generic object keys?
Similar Problems
Key Takeaways
- A hash set stores keys only; no value field is needed.
- Collisions require searching a bucket chain by actual key equality.
- Add must be idempotent: adding an existing key does not create another node.
- Remove should change only the matching node and leave colliding keys intact.