Difficulty: Easy | Acceptance: 68.00% | Paid: No Topics: Array, Hash Table, Linked List, Design, Hash Function
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.
-
Examples
-
Constraints
Examples
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 <= 10^6
At most 10^4 calls will be made to add, remove, and contains.
Direct Addressing with Boolean Array
Intuition Use a boolean array where index represents the key and value indicates presence. This is the simplest approach since keys are bounded integers.
Steps
- Create a boolean array of size 1,000,001 to cover all possible keys.
- For add, set the index to true.
- For remove, set the index to false.
- For contains, return the boolean value at the index.
python
class MyHashSet:
def __init__(self):
self.size = 1000001
self.buckets = [False] * self.size
def add(self, key: int) -> None:
self.buckets[key] = True
def remove(self, key: int) -> None:
self.buckets[key] = False
def contains(self, key: int) -> bool:
return self.buckets[key]
Complexity
- Time: O(1) for all operations
- Space: O(10⁶) for the array
- Notes: Simple but uses fixed space regardless of actual elements stored.
Chaining with Linked List
Intuition Use an array of linked lists (buckets) where each bucket stores keys that hash to the same index. This handles collisions efficiently.
Steps
- Create an array of empty linked lists with a fixed number of buckets.
- Hash the key to find the bucket index.
- Traverse the linked list to check for existence, add, or remove.
python
class ListNode:
def __init__(self, key):
self.key = key
self.next = None
class MyHashSet:
def __init__(self):
self.size = 1000
self.buckets = [None] * self.size
def _hash(self, key):
return key % self.size
def add(self, key: int) -> None:
index = self._hash(key)
curr = self.buckets[index]
if not curr:
self.buckets[index] = ListNode(key)
return
prev = None
while curr:
if curr.key == key:
return
prev = curr
curr = curr.next
prev.next = ListNode(key)
def remove(self, key: int) -> None:
index = self._hash(key)
curr = self.buckets[index]
if not curr:
return
if curr.key == key:
self.buckets[index] = curr.next
return
prev = curr
curr = curr.next
while curr:
if curr.key == key:
prev.next = curr.next
return
prev = curr
curr = curr.next
def contains(self, key: int) -> bool:
index = self._hash(key)
curr = self.buckets[index]
while curr:
if curr.key == key:
return True
curr = curr.next
return False
Complexity
- Time: O(n) worst case, O(1) average case
- Space: O(n) where n is number of elements
- Notes: Handles collisions gracefully but requires pointer management.
Open Addressing with Linear Probing
Intuition Use a single array and handle collisions by finding the next available slot through linear probing. When a slot is occupied, check the next slot.
Steps
- Create an array with a fixed size larger than expected elements.
- Hash the key to find the initial index.
- If the slot is occupied by a different key, probe to the next slot.
- Use special markers for empty and deleted slots.
python
class MyHashSet:
def __init__(self):
self.size = 10009
self.buckets = [-1] * self.size
self.DELETED = -2
def _hash(self, key):
return key % self.size
def add(self, key: int) -> None:
index = self._hash(key)
while self.buckets[index] != -1 and self.buckets[index] != key:
index = (index + 1) % self.size
self.buckets[index] = key
def remove(self, key: int) -> None:
index = self._hash(key)
while self.buckets[index] != -1:
if self.buckets[index] == key:
self.buckets[index] = self.DELETED
return
index = (index + 1) % self.size
def contains(self, key: int) -> bool:
index = self._hash(key)
while self.buckets[index] != -1:
if self.buckets[index] == key:
return True
index = (index + 1) % self.size
return False
Complexity
- Time: O(n) worst case, O(1) average case
- Space: O(capacity) where capacity is the array size
- Notes: No pointer overhead but requires careful handling of deleted slots.
Bit Manipulation
Intuition Use bitset to optimize space by storing 64 boolean values in a single integer. Each bit represents whether a key exists.
Steps
- Calculate which bucket (integer) and which bit position the key belongs to.
- For add, set the bit using OR operation.
- For remove, clear the bit using AND with complement.
- For contains, check if the bit is set using AND operation.
python
class MyHashSet:
def __init__(self):
self.size = 1000001
self.bits = [0] * ((self.size + 63) // 64)
def add(self, key: int) -> None:
bucket = key // 64
bit = key % 64
self.bits[bucket] |= (1 << bit)
def remove(self, key: int) -> None:
bucket = key // 64
bit = key % 64
self.bits[bucket] &= ~(1 << bit)
def contains(self, key: int) -> bool:
bucket = key // 64
bit = key % 64
return (self.bits[bucket] & (1 << bit)) != 0
Complexity
- Time: O(1) for all operations
- Space: O(10⁶/64) = O(15625) integers
- Notes: Most space-efficient approach but limited to integer keys.