# Design HashSet
**Difficulty:** EASY
[External](https://leetcode.com/problems/design-hashset)
Canonical: https://scaleengineer.com/dsa/problems/design-hashset
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Algorithms:** [Bloom Filter](https://scaleengineer.com/algorithms/bloom-filter), [Consistent Hashing](https://scaleengineer.com/algorithms/consistent-hashing)
**Data structures:** Array, Hash Table, Linked List
**Companies:** [Wix](https://scaleengineer.com/companies/wix)
---
## Problem
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.

**Example 1:**

**Input**
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
**Output**
[null, null, null, true, false, null, true, null, false]

**Explanation**
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

**Constraints:**

* `0 <= key <= 106`
* At most `104` calls will be made to `add`, `remove`, and `contains`.

# Approaches
## Brute Force using a List
The most straightforward approach is to use a simple list or dynamic array to store the unique keys. When an operation is requested, we can iterate through the list to perform the necessary action.
**Time:** O(N) for `add`, `remove`, and `contains` operations, where N is the number of elements currently in the set. Each operation may require iterating through the entire list. · **Space:** O(N), where N is the number of unique keys inserted into the HashSet. We only store the keys that are actually added.
**Pros:** Simple to understand and implement.; Space complexity is proportional to the number of elements stored, not the range of keys.
**Cons:** Very inefficient time complexity (`O(N)`) for all operations.; Does not scale well with the number of elements.
### Explanation
In this method, we use a `java.util.List` as the underlying data store. 

- For the `add(key)` operation, we must first ensure the key is not already present to maintain the uniqueness property of a set. This requires scanning the entire list. If the key is not found, we add it.
- For the `contains(key)` operation, we simply scan the list and return `true` if we find the key.
- For the `remove(key)` operation, we scan the list to find the key. If it exists, we remove it. 

All these operations rely on a linear scan, making them slow.

```java
import java.util.ArrayList;
import java.util.List;

class MyHashSet {
    private List<Integer> set;

    /** Initialize your data structure here. */
    public MyHashSet() {
        set = new ArrayList<>();
    }

    public void add(int key) {
        if (!this.contains(key)) {
            set.add(key);
        }
    }

    public void remove(int key) {
        // List.remove(Object) internally performs a search, which is O(N).
        set.remove(Integer.valueOf(key));
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        // List.contains() is an O(N) operation.
        return set.contains(key);
    }
}
```
### Algorithm
- **Data Structure**: A `List<Integer>` is used to store the elements of the set.
- **`add(key)`**: 
  1. First, check if the key already exists by iterating through the list (`O(N)`).
  2. If the key is not found, append it to the end of the list (`O(1)` amortized).
- **`remove(key)`**: 
  1. Find the key in the list by linear search (`O(N)`).
  2. If found, remove it. Removing an element from an `ArrayList` by value or index is also an `O(N)` operation as subsequent elements need to be shifted.
- **`contains(key)`**: 
  1. Perform a linear scan of the list (`O(N)`).
  2. Return `true` if the key is found, otherwise `false`.

## Hashing with Separate Chaining
A classic and highly practical approach is to use hashing with a technique called 'separate chaining' to handle collisions. We maintain an array of 'buckets', and a hash function determines which bucket a key belongs to. Each bucket is typically a linked list containing all the keys that have hashed to that same bucket index.
**Time:** Average Case: O(N/K), where N is the number of elements and K is the number of buckets. If K is proportional to N, this is O(1). Worst Case: O(N), if all keys hash to the same bucket. · **Space:** O(N + K), where N is the number of elements in the set and K is the number of buckets. This is efficient when the number of keys is much smaller than the key range.
**Pros:** Excellent average-case time complexity, approaching O(1).; Space-efficient, as it uses memory proportional to the number of items stored plus the bucket array size (`O(N + K)`).
**Cons:** Worst-case time complexity can be O(N) if many keys hash to the same bucket (high collisions).; Performance is sensitive to the hash function and the number of buckets (load factor).; Slightly more complex to implement than the direct addressing approach.
### Explanation
This method balances time and space complexity. Instead of one long list, we use an array of smaller lists (buckets). 

First, we choose a size for our bucket array, preferably a prime number to help with key distribution. Let's say `SIZE = 1000`. The hash function will map a key to an index within this array, e.g., `index = key % SIZE`. 

When an operation on a key is requested, we first use the hash function to locate the bucket. Then, we perform the operation (add, remove, or search) only on the small list within that bucket. If the hash function distributes keys evenly, the lists in each bucket will be short, making operations very fast on average.

```java
import java.util.LinkedList;
import java.util.List;

class MyHashSet {
    private final int BUCKET_SIZE = 1000;
    private List<Integer>[] buckets;

    /** Initialize your data structure here. */
    public MyHashSet() {
        buckets = new LinkedList[BUCKET_SIZE];
        for (int i = 0; i < BUCKET_SIZE; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(int key) {
        return key % BUCKET_SIZE;
    }

    public void add(int key) {
        int index = hash(key);
        List<Integer> bucket = buckets[index];
        if (!bucket.contains(key)) {
            bucket.add(key);
        }
    }

    public void remove(int key) {
        int index = hash(key);
        List<Integer> bucket = buckets[index];
        bucket.remove(Integer.valueOf(key));
    }

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        int index = hash(key);
        List<Integer> bucket = buckets[index];
        return bucket.contains(key);
    }
}
```
### Algorithm
- **Data Structure**: An array of lists (or another data structure like a balanced binary search tree), often called buckets.
- **Hash Function**: A function to map a key to a bucket index. A simple choice is `hash(key) = key % array_size`.
- **`add(key)`**:
  1. Compute the index `i = hash(key)`.
  2. Go to the bucket at `buckets[i]`.
  3. Search the list in this bucket for the key. If not found, add the key to this list.
- **`remove(key)`**:
  1. Compute the index `i = hash(key)`.
  2. Go to the bucket at `buckets[i]`.
  3. Search for and remove the key from the list in this bucket.
- **`contains(key)`**:
  1. Compute the index `i = hash(key)`.
  2. Go to the bucket at `buckets[i]`.
  3. Search the list in this bucket for the key and return the result.

## Direct Addressing with a Boolean Array
Given the problem's constraint that keys are in the range `[0, 10^6]`, the most time-efficient solution is to use a direct addressing table. We can use a large boolean array where the index of the array represents the key, and the value at that index indicates whether the key is present in the set.
**Time:** O(1) for `add`, `remove`, and `contains`. Each operation is a single array access. · **Space:** O(M), where M is the maximum value of the key. For this problem, it's O(10^6), which is a constant but large amount of space.
**Pros:** Extremely fast with guaranteed O(1) time complexity for all operations.; Very simple to implement.
**Cons:** High space consumption. The memory usage depends on the maximum possible key value, not the number of elements stored.; Impractical if the range of keys is very large (e.g., all possible integer values).
### Explanation
This approach leverages the constraint on the key's range to achieve constant time operations. We allocate a boolean array with a size equal to the maximum possible key value plus one (`1000001`). 

Each index `i` in this array corresponds to the key `i`. If `data[i]` is `true`, it means key `i` is in our set. If it's `false`, it's not. 

- `add(key)` becomes a simple assignment: `data[key] = true`.
- `remove(key)` is also a simple assignment: `data[key] = false`.
- `contains(key)` is a direct lookup: `return data[key]`.

All these are array access operations by index, which are O(1).

```java
class MyHashSet {
    private boolean[] data;

    /** Initialize your data structure here. */
    public MyHashSet() {
        // Constraint: 0 <= key <= 10^6
        data = new boolean[1000001];
    }

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

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

    /** Returns true if this set contains the specified element */
    public boolean contains(int key) {
        return data[key];
    }
}
```
### Algorithm
- **Data Structure**: A boolean array of a fixed size, large enough to cover the entire range of possible key values.
- **Initialization**: Create a boolean array `data` of size `10^6 + 1` and initialize all its values to `false`.
- **`add(key)`**: Set the element at the index corresponding to the key to true: `data[key] = true;`.
- **`remove(key)`**: Set the element at the index corresponding to the key to false: `data[key] = false;`.
- **`contains(key)`**: Return the boolean value at the index corresponding to the key: `return data[key];`.

# Solutions
### Java

```java
class MyHashSet { private boolean [] data = new boolean [ 1000001 ]; public MyHashSet () { } public void add ( int key ) { data [ key ] = true ; } public void remove ( int key ) { data [ key ] = false ; } public boolean contains ( int key ) { return data [ key ]; } } /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet obj = new MyHashSet(); * obj.add(key); * obj.remove(key); * boolean param_3 = obj.contains(key); */
```

### CPP

```cpp
class MyHashSet { public: bool data [ 1000001 ]; MyHashSet () { memset ( data , false , sizeof data ); } void add ( int key ) { data [ key ] = true ; } void remove ( int key ) { data [ key ] = false ; } bool contains ( int key ) { return data [ key ]; } }; /** * Your MyHashSet object will be instantiated and called as such: * MyHashSet* obj = new MyHashSet(); * obj->add(key); * obj->remove(key); * bool param_3 = obj->contains(key); */
```

### Python

```python
class MyHashSet : def __init__ ( self ): self . data = [ False ] * 1000001 def add ( self , key : int ) -> None : self . data [ key ] = True def remove ( self , key : int ) -> None : self . data [ key ] = False def contains ( self , key : int ) -> bool : return self . data [ key ] # Your MyHashSet object will be instantiated and called as such: # obj = MyHashSet() # obj.add(key) # obj.remove(key) # param_3 = obj.contains(key) ############### class MyHashSet : # hash to bucket def __init__ ( self ): """ Initialize your data structure here. """ self . size = 1000 # Choosing a size for the outer list self . buckets = [[] for _ in range ( self . size )] # List of lists def _hash ( self , key : int ) -> int : """ Generate a hash for a given key. """ return key % self . size def add ( self , key : int ) -> None : """ Insert a value into the HashSet. """ hash_key = self . _hash ( key ) if key not in self . buckets [ hash_key ]: self . buckets [ hash_key ]. append ( key ) def remove ( self , key : int ) -> None : """ Remove a value in the HashSet. If the value does not exist, do nothing. """ hash_key = self . _hash ( key ) if key in self . buckets [ hash_key ]: self . buckets [ hash_key ]. remove ( key ) def contains ( self , key : int ) -> bool : """ Returns true if this set contains the specified element. """ hash_key = self . _hash ( key ) return key in self . buckets [ hash_key ] # Your MyHashSet object will be instantiated and called as such: # obj = MyHashSet() # obj.add(key) # obj.remove(key) # param_3 = obj.contains(key) ############ # Collision handling, optimized class MyHashSet : def __init__ ( self ): self . capacity = 1000 self . data = [ None ] * self . capacity self . load_factor = 0.7 self . size = 0 def _hash ( self , key ): return key % self . capacity def _resize ( self ): if self . size / self . capacity >= self . load_factor : self . capacity *= 2 old_data = self . data self . data = [ None ] * self . capacity self . size = 0 for item in old_data : if item is not None : self . add ( item ) def add ( self , key : int ) -> None : if self . contains ( key ): return self . _resize () idx = self . _hash ( key ) while self . data [ idx ] is not None : idx = ( idx + 1 ) % self . capacity # Collision handling self . data [ idx ] = key self . size += 1 def remove ( self , key : int ) -> None : idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] == key : self . data [ idx ] = "DEL" # Mark as deleted self . size -= 1 return idx = ( idx + 1 ) % self . capacity def contains ( self , key : int ) -> bool : idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] == key : return True idx = ( idx + 1 ) % self . capacity return False
```