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.The direct address table approach is simple and efficient for this problem since the maximum key size is limited to 106. We can use a boolean array of size 106+1 where each index represents a key. The value stored at a given index indicates whether the key is present in the HashSet. This allows for O(1) time complexity for the 'add', 'remove', and 'contains' operations.
The solution creates a struct with a boolean array of size 1000001. Each index in this array corresponds to a potential key, and its boolean value represents whether that key is currently present in the set. Methods for adding, removing, and checking for keys simply modify or access this boolean array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) for all operations (add, remove, contains).
Space Complexity: O(MAX), which is O(10^6).
This approach simulates a hash set using a hash function to assign keys to buckets, dealing with potential collisions using chaining. We create an array of lists, where each list contains keys that hash to the same index. This way, operations require traversing these short lists upon collisions.
In C, we use an array of linked lists to manage collisions. A fixed-size hash-table ('BASE') is initialized, and the hash function determines which index (or 'bucket') a key belongs to. We handle collisions by adding new keys to the list at each bucket. The remove function deletes a node by updating links, and contains searches the linked list to find a key.
C++
Java
Python
C#
JavaScript
Time Complexity: O(1) average, O(n) worst-case for add, remove, and contains due to collision chains.
Space Complexity: O(n), where n is the number of keys actually added.
| Approach | Complexity |
|---|---|
| Approach 1: Direct Address Table | Time Complexity: O(1) for all operations (add, remove, contains). |
| Approach 2: Chaining using Arrays for Collision Resolution | Time Complexity: O(1) average, O(n) worst-case for add, remove, and contains due to collision chains. |
Design a Hashset - LeetCode Interview Coding Challenge [Java Brains] • Java Brains • 79,078 views views
Watch 9 more video solutions →Practice Design HashSet with our built-in code editor and test cases.
Practice on FleetCode