设计哈希集合

题目

题目来源：力扣（LeetCode

不使用任何内建的哈希表库设计一个哈希集合（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 ，（已移除）

思路分析

使用链地址法解决哈希冲突

1. 设哈希表的大小为 base，则可以设计一个简单的哈希函数：hash(x) = x mod base。
2. 我们开辟一个大小为 base的数组，数组的每个位置是一个链表。当计算出哈希值之后，就插入到对应 位置的链表当中。
3. 由于我们使用整数除法作为哈希函数，为了尽可能避免冲突，应当将 base 取为一个质数。在这里，我 们取 base = 769

/**
 * Initialize your data structure here.
 */
var MyHashSet = function() {
  // 由于使用整数除法作为哈希函数，为了尽可能避免冲突，应当将 BASE 取为一个质数
  // 在这里我们取 BASE 为 769
  this.BASE = 769;
  // 使用数组实现哈希集合
  // 开辟一个大小为 BASE 的数组，数组的每个位置是一个链表，当计算出哈希值之后，就插入到对应位置的链表当中
  this.data = new Array(this.BASE).fill(0).map(() => new Array())
};
/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function(key) {
  // 计算哈希值
  const h = this.hash(key);
  for(let element of this.data[h]) {
    if (element === key) {
      return;
    }
  }
  this.data[h].push(key);
};
/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function(key) {
  const h = this.hash(key);
  const it = this.data[h];
  for(let i = 0; i < it.length; ++i) {
    if (it[i] === key) {
      it.splice(i, 1);
      return;
    }
  }
}
/**
 * Returns true if this set contains the specified element 
 * @param {number} key
 * @return {boolean}
 */
MyHashSet.prototype.contains = function(key) {
  const h = this.hash(key);
  for(let element of this.data[h]) {
    if (element === key) {
      return true;
    }
  }
  return false;
};
MyHashSet.prototype.hash = function(key) {
  // 由于使用整数除法作为哈希函数，为了尽可能避免冲突，应当将 BASE 取为一个质数, BASE 取 769 
  return key % this.BASE;
}