algoadvance

Design a HashSet without using any built-in hash table libraries. Implement the 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.

Clarifying Questions

1. Range of Values: What are the possible ranges of input values for key?
   • Typically, keys could be within a certain range, e.g., 0 to 1,000,000.
2. Operations Frequency: Are there any constraints on the number of operations to be performed?
   • Typically, assumptions are based on performance needs to handle in average O(1) time for each operation using hashing.
3. Concurrency: Should we design this to handle concurrent operations?
   • Generally, not required unless specified.

Given these constraints, we will use a simplistic yet effective approach to designing the HashSet.

Strategy

We can simulate the behavior of a hash set using a list of lists (also known as buckets). The approach involves:

1. Each element hashing to a particular bucket.
2. Each bucket maintaining a list of keys inserted.

Key steps and design:

1. Hashing Function: We will implement a simple modulo operation for hashing.
2. Buckets Array: We create an array of a fixed size, each element is an empty list for chaining.
3. Operations:
   • Add: Compute hash, navigate to bucket, check if element exists, otherwise append.
   • Contains: Compute hash, navigate to bucket, check for the element.
   • Remove: Compute hash, navigate to bucket, remove the element if found.

Time Complexity

• Add: Average O(1), Worst case O(n) in case of hash collisions (n is the number of keys)
• Contains: Average O(1), Worst case O(n)
• Remove: Average O(1), Worst case O(n)

Code

class MyHashSet:
    
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.bucket_count = 1000
        self.buckets = [[] for _ in range(self.bucket_count)]

    def _hash(self, key: int) -> int:
        """
        Hashing function to compute bucket index.
        """
        return key % self.bucket_count

    def add(self, key: int) -> None:
        """
        Add a key into the HashSet.
        """
        bucket_index = self._hash(key)
        if key not in self.buckets[bucket_index]:
            self.buckets[bucket_index].append(key)

    def remove(self, key: int) -> None:
        """
        Remove a key from the HashSet.
        """
        bucket_index = self._hash(key)
        if key in self.buckets[bucket_index]:
            self.buckets[bucket_index].remove(key)

    def contains(self, key: int) -> bool:
        """
        Returns true if this set contains the specified element
        """
        bucket_index = self._hash(key)
        return key in self.buckets[bucket_index]

Example Execution

# Initialize a new HashSet
hashSet = MyHashSet()

# Add elements
hashSet.add(1)
hashSet.add(2)

# Check for elements
print(hashSet.contains(1))  # Returns True
print(hashSet.contains(3))  # Returns False

# Remove an element
hashSet.remove(2)

# Check again
print(hashSet.contains(2))  # Returns False

Summary

This solution provides a simple and effective way of implementing a HashSet using a fixed bucket array and basic list operations, focusing on constant time complexity for average-case scenarios.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?