一、题目

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

void add(key) 向哈希集合中插入值 key 。
bool contains(key) 返回哈希集合中是否存在这个值 key 。
void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例：

输入：
[“MyHashSet”, “add”, “add”, “contains”, “contains”, “add”, “contains”, “remove”, “contains”]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
输出：
[null, null, null, true, false, null, true, null, false]

解释：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

提示：

0 ≤ k e y ≤ 1 0 6 0 \le key \le 10^6 0≤key≤106
最多调用 1 0 4 10^4 104次 add、remove 和 contains 。

二、代码

2.1 解法1：

class MyHashSet {
private:
    const int SIZE=997;
    vector<list<int>> hashset;
    int hash(int key){
        return key%SIZE;
    }

public:
    /** Initialize your data structure here. */
    MyHashSet():hashset(SIZE,list<int>()){

    }
    
    void add(int key) {
        if(!contains(key)){
            hashset[hash(key)].push_back(key);
        }
    }
    
    void remove(int key) {
        int i=hash(key);
        for(auto ite=hashset[i].begin();ite!=hashset[i].end();++ite){
            if((*ite)==key){
                hashset[i].erase(ite);break;
            }
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        int i=hash(key);
        for(auto ite=hashset[i].begin();ite!=hashset[i].end();++ite){
            if((*ite)==key) return true;
        }
        return false;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

思路：

• 用一个长度为SIZE的数组，哈希函数是简单的key%SIZE，数组元素是列表
• 若发生冲突，则将元素插入到列表中
• erase()函数可以删除列表中的特定一项（迭代器形式），且不影响列表完整性
• SIZE最好是一个质数，可以最大程度减少冲突的可能性

2.2 解法2：

class MyHashSet {
private:
    bool exist[1000001];

public:
    /** Initialize your data structure here. */
    MyHashSet(){
        memset(exist,false,sizeof(exist));
    }
    
    void add(int key) {
        exist[key]=true;
    }
    
    void remove(int key) {
        exist[key]=false;
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        return exist[key];
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */

思路：

• 直接用一个bool类型（大小为1）的数组，因为注意到key都是正数且有最大值。