🥉705. 设计哈希集合@

不使用任何内建的哈希表库设计一个哈希集合（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 <= key <=

• 最多调用次 add、remove 和 contains

  
  进阶：你可以不使用内建的哈希集合库解决此问题吗？

题解

HashSet 是指能 时间内进行插入和删除，可以保存不重复元素的一种数据结构。

HashSet 是在时间和空间上做权衡的经典例子：如果不考虑空间，可以直接设计一个超大的数组，使每个key 都有单独的位置，则不存在冲突；如果不考虑时间，我们可以直接用一个无序的数组保存输入，每次查找的时候遍历一次数组。

为了时间和空间上的平衡，HashSet 基于数组实现，并通过 hash 方法求键 key 在数组中的位置，当 hash 后的位置存在冲突的时候，再解决冲突。

设计 hash 函数需要考虑两个问题：

通过 hash 方法把键 key 转成数组的索引：设计合适的 hash 函数，一般都是对分桶数取模 % 。
处理碰撞冲突问题：拉链法 和 线性探测法。
下面我用了两个方法：

超大数组：通过空间换时间。
拉链法：大多数编程语言选择的方法。