Design Hashset - Leetcode Solution

Problem Statement: 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.

Constraints:

• 0 <= key <= 10^6
• At most 10^4 calls will be made to add, remove, and contains.

Solution:

The simplest way to implement a HashSet is by using an array and mapping the hash code of a key to the index of the array. In this solution, I am using an array with size 10^6. I am using the hash code of the given key as an index in the array. I will also be using a LinkedList to handle the collision scenarios where two keys have the same hash code.

MyHashSet class will have the following methods implemented:

1. init: Initialize the array with -1 at all the indexes. Initialize an empty list to handle collisions.

2. _hash: This method will return the hash code of the given key.

   The logic for finding the hash is straightforward: hash = key % 10^6 Here, I am using the modulo operation to restrict the hash value to a maximum of 10^6.

3. add: This method takes a key and adds it to the HashSet.

   Here, we will follow the following steps:

   • First, find the hash value of the given key.
   • If the index at hash is -1, then there is no existing key at that index. So add the key to the array at the hash index.
   • If the index at hash is not -1, then it means there is a key present at that index. So we need to check if the given key is already present or not. If it is already present, then do nothing. Otherwise, append the key to the list at that index.

4. remove: This method takes a key and removes it from the HashSet.

   Here, we need to follow the following steps:

   • First, find the hash value of the given key.
   • If the index at hash is -1, then it means there is no existing key at that index. So do nothing.
   • If the index at hash is not -1, then it means there is a key present at that index. If the key at that index matches the given key, then delete the key from the array. Otherwise, search for the key in the list at that index and delete it if found.

5. contains: This method takes a key and checks if it is present in the HashSet.

   Here, we need to follow the following steps:

   • First, find the hash value of the given key.
   • If the index at hash is -1, then it means there is no existing key at that index. So return False.
   • If the index at hash is not -1, then it means there is a key present at that index. If the key at that index matches the given key, return True. Otherwise, search for the key in the list at that index and return True if found, else False.

Implementing the above logic will give us the solution for the problem.

Code:

class MyHashSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = [-1] * (10**6)

    def _hash(self, key):
        return key % (10**6)
    
    def add(self, key: int) -> None:
        hash_val = self._hash(key)
        if self.data[hash_val] == -1:
            self.data[hash_val] = key
        else:
            if self.data[hash_val] == key:
                return
            if type(self.data[hash_val]) == list:
                if key in self.data[hash_val]:
                    return
                else:
                    self.data[hash_val].append(key)
            else:
                self.data[hash_val] = [self.data[hash_val], key]

    def remove(self, key: int) -> None:
        hash_val = self._hash(key)
        if self.data[hash_val] == -1:
            return
        elif self.data[hash_val] == key:
            self.data[hash_val] = -1
        elif type(self.data[hash_val]) == list:
            if key in self.data[hash_val]:
                self.data[hash_val].remove(key)
                if len(self.data[hash_val]) == 1:
                    self.data[hash_val] = self.data[hash_val][0]
            else:
                return
        else:
            return

    def contains(self, key: int) -> bool:
        hash_val = self._hash(key)
        if self.data[hash_val] == -1:
            return False
        elif self.data[hash_val] == key:
            return True
        elif type(self.data[hash_val]) == list:
            return key in self.data[hash_val]
        else:
            return False

Time Complexity: The time complexity of the above solution is O(1) for all operations add(), remove(), contains() on average. In the worst case, when there are a lot of collisions, the time complexity can become O(N) where N is the number of entries in the HashSet.

1