Hash Set

Hash Set, also known as a HashSet or a Set, is a data structure that stores a collection of unique elements. It is implemented using a Hash Table internally, where the elements are hashed to unique indices in an array.

Here's an example implementation of a Hash Set:

class HashSet:
    def __init__(self):
        self.size = 1000  # initial size of the hash set
        self.buckets = [[] for _ in range(self.size)]  # list of buckets

    def _hash(self, value):
        # Compute the hash value for the given value
        return hash(value) % self.size

    def add(self, value):
        # Add a value to the hash set
        hash_value = self._hash(value)
        bucket = self.buckets[hash_value]
        for element in bucket:
            if element == value:
                return
        bucket.append(value)

    def remove(self, value):
        # Remove a value from the hash set
        hash_value = self._hash(value)
        bucket = self.buckets[hash_value]
        for i, element in enumerate(bucket):
            if element == value:
                del bucket[i]
                return

    def contains(self, value):
        # Check if a value exists in the hash set
        hash_value = self._hash(value)
        bucket = self.buckets[hash_value]
        for element in bucket:
            if element == value:
                return True
        return False

# Example usage:
hash_set = HashSet()
hash_set.add(1)
hash_set.add(2)
print(hash_set.contains(1))  # Output: True
print(hash_set.contains(3))  # Output: False
hash_set.remove(1)
print(hash_set.contains(1))  # Output: False

In this implementation, we define a HashSet class with methods for add(), remove(), and contains(). The _hash() method computes the hash value for a given value using Python's built-in hash() function. We use the hash value to determine the bucket where the value will be stored.

The add() method adds a value to the hash set. It computes the hash value for the value and retrieves the corresponding bucket. It then iterates over the elements in the bucket and checks if the value already exists. If it does, the method returns without adding the value. If not, it appends the value to the bucket.

The remove() method removes a value from the hash set. It computes the hash value, retrieves the bucket, and iterates over the elements. If the value is found, it uses the del keyword to delete the value from the bucket.

The contains() method checks if a value exists in the hash set. It computes the hash value, retrieves the bucket, and iterates over the elements. If the value is found, it returns True. Otherwise, it returns False.

Now, let's solve a problem from LeetCode using the Hash Set concept.

Problem: Contains Duplicate Description: Given an array of integers, find if the array contains any duplicates.

Here's the solution using a Hash Set:

def contains_duplicate(nums):
    hash_set = set()
    for num in nums:
        if num in hash_set:
            return True
        hash_set.add(num)
    return False

# Example usage:
nums = [1, 2, 3, 1]
print(contains_duplicate(nums))  # Output: True

In this solution, we iterate over the array nums and check if each element already exists in the hash set. If it does, we return True since there is a duplicate. If not, we add the element to the hash set. If we reach the end of the loop without finding any duplicates, we return False.

The time complexity of this solution is O(n) since we iterate over the array once. The space complexity is also O(n) in the worst case if all elements are stored in the hash set.