705. Design HashSet

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

2. Example

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)

3. Constraints

• 0 <= key <= $10^6$
• At most $10^4$ calls will be made to add, remove, and contains.

4. Solutions

Prime

class MyHashSet {
public:
    MyHashSet() {}

    void add(int key) {
        auto& data_bucket = data_[key % data_.size()];
        if (find(data_bucket.begin(), data_bucket.end(), key) == data_bucket.end()) {
            data_bucket.push_front(key);
        }
    }

    void remove(int key) {
        auto& data_bucket = data_[key % data_.size()];
        auto key_iter = find(data_bucket.begin(), data_bucket.end(), key);
        if (key_iter != data_bucket.end()) {
            data_bucket.erase(key_iter);
        }
    }

    bool contains(int key) {
        auto data_bucket = data_[key % data_.size()];
        return find(data_bucket.begin(), data_bucket.end(), key) != data_bucket.end();
    }

private:
    array<list<int>, 768> data_; // any prime
};