Problem statement

Build a set of integers without using your language's built-in hash table or set. Write the class MyHashSet:

• MyHashSet() creates an empty set.
• void add(int key) puts key into the set (adding a key that is already there changes nothing).
• void remove(int key) takes key out of the set; if it is not there, nothing happens.
• boolean contains(int key) returns whether key is in the set.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.

Example 1

Input: ["MyHashSet","add","add","contains","contains","add","contains","remove","contains"]
[[],[3],[8],[3],[5],[8],[8],[8],[8]]
Output: [null,null,null,true,false,null,true,null,false]
Explanation: 3 and 8 go in; 5 never did. Adding 8 a second time changes nothing, and once 8 is removed it is gone.

Example 2

Input: ["MyHashSet","contains","remove","add","add","contains","contains"]
[[],[0],[0],[1000000],[0],[1000000],[0]]
Output: [null,false,null,null,null,true,true]
Explanation: Removing a key that was never added is allowed and does nothing. 0 and 1000000 are the smallest and largest keys.

Constraints

• 0 <= key <= 10^6
• At most 10^4 calls are made to add, remove and contains

Hints for Design HashSet

1. Hint 1

   With keys up to 10^6 a boolean array would work, but the point is the general technique: map each key to one of a fixed number of buckets.

2. Hint 2

   Use key % B for a prime B such as 769 as the bucket index. Different keys can land in the same bucket — that is a collision.

3. Hint 3

   Make each bucket a small list (separate chaining): add appends only if the key is not already in that bucket's list, remove deletes it from there, contains scans that one list.

How to solve Design HashSet

Separate chaining: an array of B buckets, each a short list of keys. A key lives in bucket key % B, so every operation only looks at one bucket's list instead of the whole set.

Approach

1. Create B = 769 empty buckets (a prime spreads keys evenly).
2. add(key): look in bucket key % B; append key if it is not already there.
3. remove(key): look in bucket key % B; delete key if it is there.
4. contains(key): report whether bucket key % B holds key.

Why it works

Every key is only ever stored in, searched in and removed from the one bucket its hash picks, so a key is in the set exactly when it is in that bucket's list, and the duplicate check on add keeps each key there at most once.

Complexity

• Time — O(n / B) per operation on average, where n is the number of keys stored
• Space — O(B + n)

Pitfalls

• Appending without checking first lets a key appear twice in a bucket; one remove would then leave a copy behind.
• In Java, list.remove(key) with an int removes by index — remove Integer.valueOf(key).

Reference solution

Python

class MyHashSet:

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

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

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

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

Java

class MyHashSet {
    private static final int SIZE = 769;
    private List<List<Integer>> buckets = new ArrayList<>();

    public MyHashSet() {
        for (int i = 0; i < SIZE; i++) buckets.add(new LinkedList<>());
    }

    public void add(int key) {
        List<Integer> b = buckets.get(key % SIZE);
        if (!b.contains(key)) b.add(key);
    }

    public void remove(int key) {
        buckets.get(key % SIZE).remove(Integer.valueOf(key)); // by value, not by index
    }

    public boolean contains(int key) {
        return buckets.get(key % SIZE).contains(key);
    }
}

C++

class MyHashSet {
    static const int SIZE = 769;
    vector<list<int>> buckets;
public:
    MyHashSet() : buckets(SIZE) {}

    void add(int key) {
        list<int>& b = buckets[key % SIZE];
        if (find(b.begin(), b.end(), key) == b.end()) b.push_back(key);
    }

    void remove(int key) {
        buckets[key % SIZE].remove(key);
    }

    bool contains(int key) {
        list<int>& b = buckets[key % SIZE];
        return find(b.begin(), b.end(), key) != b.end();
    }
};

JavaScript

var MyHashSet = function() {
    this.size = 769;
    this.buckets = [];
    for (var i = 0; i < this.size; i++) this.buckets.push([]);
};

MyHashSet.prototype.add = function(key) {
    var b = this.buckets[key % this.size];
    if (b.indexOf(key) < 0) b.push(key);
};

MyHashSet.prototype.remove = function(key) {
    var b = this.buckets[key % this.size];
    var i = b.indexOf(key);
    if (i >= 0) b.splice(i, 1);
};

MyHashSet.prototype.contains = function(key) {
    return this.buckets[key % this.size].indexOf(key) >= 0;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Brightest String of Diyas Easy
• Design Neighbor Sum Service Easy
• Design an Ordered Stream Easy
• Design HashMap Easy
• Range Sum Query - Immutable Easy
• Convert Sorted Array to Binary Search Tree Easy