705. Design HashSet

解題思路

昨天的 leetcode daily 也是 hash map ，但已經偷懶用 single array 來解了，今天不能再偷懶下去，不然就失去解題意義(其實是看到discussion裡面有人說：「你確定你會在面試時用這種解法嗎？」)。

hash 通常會搭配 linked-list，而 list 這個 stl 容器就是用 double-linked list 實現的。

另外 vector 的 resize 可以用來動態改變大小。

至於 prime 數字大小怎麼選擇暫時沒想到，這裡的數字是抄別人的。

程式碼

class MyHashSet {
public:
    int size;
    vector<list<int>> table;
    MyHashSet() {
        size = 10007;
        table.resize(size);
    }
    
    void add(int key) {
        int hash = key % size;
        table[hash].push_back(key);
    }
    
    void remove(int key) {
        int hash = key % size;
        table[hash].remove(key);
    }
    
    bool contains(int key) {
        int hash = key % size;
        return find(table[hash].begin(), table[hash].end(), key) != table[hash].end();
    }
};