哈希集合

实现

---

实现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 ，（已移除）

class MyHashSet {
  constructor(capacity) {
    this.capacity = capacity || 769;
    this.data = new Array(this.capacity).fill(0).map(() => new Array());
  }
  hash(key) {
    return key % this.capacity;
  }
  contains(key, hash) {
    if (hash == null) {
      hash = this.hash(key);
    }
    for (const item of this.data[hash]) {
      if (item === key) {
        return true;
      }
    }
    return false;
  }
  add(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item === key) {
        return;
      }
    }
    this.data[hash].push(key);
  }
  remove(key) {
    const hash = this.hash(key);
    const list = this.data[hash];
    for (let i = 0; i < list.length; i++) {
      if (list[i] === key) {
        list.splice(i, 1);
        return;
      }
    }
  }
}