Design HashSet

EASY

Description

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 <= 10⁶
At most 10⁴ calls will be made to add, remove, and contains.

Approaches

Checkout 3 different approaches to solve Design HashSet. Click on different approaches to view the approach and algorithm in detail.

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.

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];.

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).

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];
    }
}

Complexity Analysis

Time Complexity: O(1) for `add`, `remove`, and `contains`. Each operation is a single array access.Space Complexity: 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 and Cons

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).

Code Solutions

Checking out 3 solutions in different languages for Design HashSet. Click on different languages to view the code.

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); */

Video Solution

Watch the video walkthrough for Design HashSet

Patterns:

DesignHash Function

Data Structures:

ArrayHash TableLinked List

Companies:

Wix |