Daily LeetCode Problems: Problem 705. Design HashSet

Building Your Own Hashset: Customized Data Structure for Efficient Storage

Introduction:

Welcome to today’s problem-solving article! In this edition, we’ll dive into problem 705 from LeetCode: “Design Hashset”. This problem challenges us to create our own hashset implementation without using any built-in hash table libraries. We’ll explore the problem statement, design a customized data structure, explain the underlying concepts, and provide a step-by-step solution.

Problem Statement:

The task at hand is to design a hashset from scratch. The implementation should consist of the following methods:

• 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 from the hashset. If key does not exist in the hashset, no action is required.

Approach:

To solve this problem, we’ll design a hashset using an array and a hashing function. We’ll use the modulo operator to calculate the index where each value should be stored. Each index will hold a linked list to handle potential collisions.

Pseudocode:

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]

    def add(self, key: int) -> None:
        index = key % self.size
        if key not in self.buckets[index]:
            self.buckets[index].append(key)

    def remove(self, key: int) -> None:
        index = key % self.size
        if key in self.buckets[index]:
            self.buckets[index].remove(key)

    def contains(self, key: int) -> bool:
        index = key % self.size
        return key in self.buckets[index]

Complexity Analysis:

Let’s analyze the complexity of our solution:

• Time complexity:
• The add operation has an average time complexity of O(1), as we expect constant time for inserting an element into the linked list at the respective index.
• The remove operation also has an average time complexity of O(1), assuming a constant time removal from the linked list.
• The contains operation has an average time complexity of O(1) as well, due to the constant time lookup in the linked list.
• Space complexity:
• The space complexity is O(n), where n represents the number of elements stored in the hashset. We use an array of fixed size to store the linked lists.

Step-by-Step Solution:

1. Initialize the hashset with a fixed size and create an array of empty lists.
2. To add an element, calculate the index using the modulo operator on the key. If the key does not already exist in the linked list at that index, append it.
3. To remove an element, calculate the index using the modulo operator on the key. If the key exists in the linked list at that index, remove it.
4. To check if an element exists, calculate the index using the modulo operator on the key and check if the key exists in the linked list at that index.
5. Handle collisions by using separate chaining: multiple elements with the same index are stored in a linked list.

Full Solution:

Python

class MyHashSet:
  def __init__(self):
    self.set = [False] * 1000001

  def add(self, key: int) -> None:
    self.set[key] = True

  def remove(self, key: int) -> None:
    self.set[key] = False

  def contains(self, key: int) -> bool:
    return self.set[key]

Java

class MyHashSet {
  /** Initialize your data structure here. */
  public MyHashSet() {
    set = new boolean[1000001];
  }

  public void add(int key) {
    set[key] = true;
  }

  public void remove(int key) {
    set[key] = false;
  }

  /** Returns true if this set contains the specified element */
  public boolean contains(int key) {
    return set[key];
  }

  private boolean[] set = new boolean[1000001];
}

C++

class MyHashSet {
 public:
  /** Initialize your data structure here. */
  MyHashSet() : set(1000001) {}

  void add(int key) {
    set[key] = true;
  }

  void remove(int key) {
    set[key] = false;
  }

  /** Returns true if this set contains the specified element */
  bool contains(int key) {
    return set[key];
  }

 private:
  vector<bool> set;
};

Conclusion:

In this article, we explored problem 705, “Design Hashset,” and designed a customized data structure to efficiently store and retrieve values. By implementing our own hashset using an array and a hashing function, we demonstrated the underlying concepts of hashing and collision handling. Understanding the problem statement and implementing our approach will enable you to build your own hashset for efficient storage needs. Happy coding!