Watch 10 video solutions for Design HashSet, a easy level problem involving Array, Hash Table, Linked List. This walkthrough by NeetCodeIO has 48,508 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.bool contains(key) Returns whether the value key exists in the HashSet or not.void remove(key) Removes the value key in the HashSet. If key does 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 <= 106104 calls will be made to add, remove, and contains.Problem Overview: Build a HashSet from scratch without using built‑in hash table libraries. The structure must support three operations: add(key), remove(key), and contains(key). Each operation should run efficiently while handling potential key collisions.
Approach 1: Direct Address Table (Time: O(1), Space: O(N))
The simplest design maps every possible key directly to an index in an array. Since the problem constraints limit keys to a known range (typically 0 ≤ key ≤ 10^6), you allocate a boolean array where the index represents the key itself. add(key) sets the slot to true, remove(key) sets it to false, and contains(key) checks the value at that index. Every operation becomes a constant-time array lookup or update. This approach avoids collisions entirely because each key has a unique slot. The tradeoff is memory usage: space complexity is O(N) for the full key range even if only a few keys are stored. It works well when the key range is small and predictable and relies purely on an array rather than a true hash structure.
Approach 2: Chaining Using Arrays for Collision Resolution (Average Time: O(1), Worst: O(N), Space: O(N))
A more realistic hash set uses a hash function and buckets. Create an array of buckets, then compute the bucket index with a simple hash = key % bucketSize. Each bucket stores multiple keys using a small list or linked list. When you call add, compute the hash index and append the key if it does not already exist in that bucket. remove searches the bucket and deletes the key, while contains scans the bucket to check membership. Average time remains O(1) if the hash function distributes keys evenly. In the worst case, when many keys collide into the same bucket, operations degrade to O(N). This design demonstrates how real hash tables handle collisions and is closer to production implementations.
Recommended for interviews: Interviewers typically expect the hashing approach with buckets because it shows you understand collision handling and the role of a hash function. The direct address table is still useful to mention first since it proves you recognize the constant-time lookup property. Moving from the direct mapping idea to a bucketed hash structure demonstrates stronger system design and data structure fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Address Table | O(1) | O(N) | When the key range is small and known in advance; simplest constant-time implementation |
| Hashing with Chaining (Bucket Array) | Average O(1), Worst O(N) | O(N) | General hash set design when keys may collide and memory must scale with stored elements |