705

705. Design HashSet (Easy)

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.

Companies: Microsoft

Related Topics: Array, Hash Table, Linked List, Design, Hash Function

Similar Questions:

• Design HashMap (Easy)
• Design Skiplist (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/design-hashset/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class MyHashSet {
    bitset<1000001> bs;
public:
    MyHashSet() {}
    void add(int key) { bs.set(key); }
    void remove(int key) { bs.reset(key); }
    bool contains(int key) { return bs.test(key); }
};

Separate Chaining

• hash function: the goal of the hash function is to assign an address to store a given value. Ideally, each unique value should have a unique hash value.

• collision handling: since the nature of a hash function is to map a value from a space A into a corresponding value in a smaller space B, it could happen that multiple values from space A might be mapped to the same value in space B. This is what we call collision. Therefore, it is indispensable for us to have a strategy to handle the collision.

Overall, there are several strategies to resolve the collisions:

• Separate Chaining: for values with the same hash key, we keep them in a bucket, and each bucket is independent of each other.

• Open Addressing: whenever there is a collision, we keep on probing on the main space with certain strategy until a free slot is found.

• 2-Choice Hashing: we use two hash functions rather than one, and we pick the generated address with fewer collision.

Here we focus on separate chaining.

Solution 2. Doubly-Linked List

// OJ: https://leetcode.com/problems/design-hashset/
// Author: github.com/lzl124631x
// Time:
//		MyHashSet: O(1)
//		add, remove, contains: O(N) in the worst case.
// Space: O(N)
const int keyRange = 769;
class Bucket {
    list<int> items;
public:
    Bucket() {}
    void add(int key) {
        if (!contains(key)) items.push_front(key);
    }
    void remove(int key) {
        auto it = find(begin(items), end(items), key);
        if (it != end(items)) items.erase(it);
    }
    bool contains(int key) {
        return find(begin(items), end(items), key) != end(items);
    }
};
class MyHashSet {
    Bucket buckets[keyRange] = {};
    int hash(int key) { return key % keyRange; };
public:
    MyHashSet() {}
    void add(int key) { buckets[hash(key)].add(key); }
    void remove(int key) { buckets[hash(key)].remove(key); }
    bool contains(int key) { return buckets[hash(key)].contains(key); }
};

Solution 3. Binary Search Tree

Note that we need to use AVL tree that auto-balance itself to achieve average O(logN) search time complexity.

// OJ: https://leetcode.com/problems/design-hashset/
// Author: github.com/lzl124631x
// Time:
//		MyHashSet: O(1)
//		add, remove, contains: O(logN) on average, O(N) in the worst case.
// Space: O(N)
const int keyRange = 769;
struct BSTreeNode {
    int val;
    BSTreeNode *left = nullptr, *right = nullptr;
    BSTreeNode(int val) : val(val) {}
};
class BSTree {
    BSTreeNode *root = nullptr;
    BSTreeNode* deleteNode(BSTreeNode* root, int key) {
        if (!root) return nullptr;
        if (root->val < key) {
            root->right = deleteNode(root->right, key);
            return root;
        } else if (root->val > key) {
            root->left = deleteNode(root->left, key);
            return root;
        }
        if (!root->left || !root->right) return root->left ? root->left : root->right;
        auto newRoot = root->right, left = newRoot->left, node = root->left;
        newRoot->left = root->left;
        while (node->right) node = node->right;
        node->right = left;
        return newRoot;
    }
public:
    void add(int key) {
        if (!root) {
            root = new BSTreeNode(key);
            return;
        }
        BSTreeNode *prev = nullptr, *n = root;
        while (n) {
            prev = n;
            if (key == n->val) return;
            if (key < n->val) n = n->left;
            else n = n->right;
        }
        if (key < prev->val) prev->left = new BSTreeNode(key);
        else prev->right = new BSTreeNode(key);
    }
    void remove(int key) {
        root = deleteNode(root, key);
    }
    bool contains(int key) {
        auto n = root;
        while (n) {
            if (n->val == key) return true;
            if (n->val < key) n = n->right;
            else n = n->left;
        }
        return false;
    }
};
class MyHashSet {
    BSTree buckets[keyRange] = {};
    int hash(int key) { return key % keyRange; };
public:
    MyHashSet() {}
    void add(int key) { buckets[hash(key)].add(key); }
    void remove(int key) { buckets[hash(key)].remove(key); }
    bool contains(int key) { return buckets[hash(key)].contains(key); }
};