055.md

705. Design HashSet

Difficulty: 🟢 Easy

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:

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 <= 106
• At most 104 calls will be made to add, remove, and contains.

Solutions

Example solution

Python 3

class ListNode:
    def __init__(self, key):
        self.key = key
        self.next = None

class MyHashSet:
    def __init__(self):
        self.capacity = 100
        self.bucket = [None] * self.capacity

    def _hash(self, key: int) -> int:
        prime = 97
        return (key * prime) % self.capacity

    def add(self, key: int) -> None:
        index = self._hash(key)
        if self.bucket[index] is None:
            self.bucket[index] = ListNode(key)
        else:
            curr = self.bucket[index]
            while curr:
                if curr.key == key:
                    return
                if curr.next is None:
                    break
                curr = curr.next
            curr.next = ListNode(key)

    def contains(self, key: int) -> bool:
        index = self._hash(key)
        curr = self.bucket[index]
        while curr:
            if curr.key == key:
                return True
            curr = curr.next
        return False

    def remove(self, key: int) -> None:
        index = self._hash(key)
        prev = None
        curr = self.bucket[index]
        while curr:
            if curr.key == key:
                if prev:
                    prev.next = curr.next
                else:
                    self.bucket[index] = curr.next
                return
            prev = curr
            curr = curr.next

# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

The given solution uses a simple implementation of a HashSet using a hash function and an array of linked lists.

Here is a step-by-step overview of the solution:

1. Define a ListNode class that represents a node in the linked list. Each node contains a key and a reference to the next node (next).
2. Initialize the MyHashSet class with a fixed capacity of 100 and an array called bucket of size capacity to store the linked lists.
3. Implement a private _hash function that takes a key as input and returns the hash value (index) based on a prime number and the capacity of the HashSet.
4. Implement the add method that adds a key to the HashSet:
   • Calculate the hash value using the _hash function.
   • If the bucket at the calculated index is None, create a new ListNode with the key and assign it to the bucket.
   • If the bucket at the calculated index is not None, iterate through the linked list at that index:
     • If the current node's key is equal to the key we want to add, return (no duplicates are allowed).
     • If the current node's next is None, break the loop and add a new ListNode with the key at the end of the linked list.
5. Implement the contains method that checks if a key exists in the HashSet:
   • Calculate the hash value using the _hash function.
   • Iterate through the linked list at the calculated index and check if any node's key matches the given key. If found, return True.
   • If the loop completes without finding a match, return False.
6. Implement the remove method that removes a key from the HashSet:
   • Calculate the hash value using the _hash function.
   • Iterate through the linked list at the calculated index:
     • If the current node's key is equal to the given key, update the previous node's next reference to skip the current node and remove it from the linked list.
7. The MyHashSet class is now ready to be instantiated and used.

Complexity Analysis

The time complexity for the add, contains, and remove methods is O(1) on average. In the worst case, when there are many collisions and all keys are hashed to the same index, the time complexity becomes O(n), where n is the number of elements in the HashSet. However, since the capacity of the HashSet is fixed at 100, the worst case is limited.

The space complexity is O(capacity), where capacity is the fixed size of the HashSet (100). The space is used to store the array of linked lists.

Summary

The given solution implements a HashSet without using built-in hash table libraries. It uses a hash function and an array of linked lists to store the keys. The time complexity of the add, contains, and remove methods is O(1) on average. The space complexity is O(capacity), where capacity is the fixed size of the HashSet.

NB: If you want to get community points please suggest solutions in other languages as merge requests.