We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design HashSet

Difficulty: Easy

Problem Description

Design a HashSet without using any built-in hash table libraries. Implement the MyHashSet class with methods to add, check for existence, and remove keys.

Key Insights

  • A HashSet allows for efficient storage and retrieval of unique keys.
  • The underlying data structure can be an array of linked lists to handle collisions.
  • A hash function will map keys to indices in the array.

Space and Time Complexity

Time Complexity:

  • add: O(1) on average, O(n) in the worst case due to collisions.
  • contains: O(1) on average, O(n) in the worst case due to collisions.
  • remove: O(1) on average, O(n) in the worst case due to collisions.

Space Complexity: O(n) for storing the keys, where n is the number of keys in the HashSet.

Solution

To design the MyHashSet, we will utilize an array of linked lists to store the keys. The keys will be hashed to find their corresponding index in the array. Each index will point to a linked list that handles collisions through chaining. The add method will insert keys into the appropriate linked list if they don't already exist. The contains method will check if a key exists by traversing the linked list at the hashed index. The remove method will delete the key from the linked list if it exists.

Code Solutions

class MyHashSet:
    def __init__(self):
        self.size = 1000  # size of the array
        self.buckets = [[] for _ in range(self.size)]  # initialize the buckets

    def _hash(self, key):
        return key % self.size  # simple hash function

    def add(self, key):
        hash_key = self._hash(key)
        if key not in self.buckets[hash_key]:
            self.buckets[hash_key].append(key)  # add key to the bucket

    def contains(self, key):
        hash_key = self._hash(key)
        return key in self.buckets[hash_key]  # check if key exists

    def remove(self, key):
        hash_key = self._hash(key)
        if key in self.buckets[hash_key]:
            self.buckets[hash_key].remove(key)  # remove key from the bucket
← Back to All Questions