说在前面
🎈不知道大家对于算法的学习是一个怎样的心态呢？为了面试还是因为兴趣？不管是出于什么原因，算法学习需要持续保持。
题目描述
不使用任何内建的哈希表库设计一个哈希集合（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 <= 10^6- 最多调用
10^4次add、remove和contains
解题思路
这个 HashSet 包含了三个方法：
- add(key)：向 HashSet 中添加元素 key，如果元素已经存在则不会重复添加。
- remove(key)：从 HashSet 中移除元素 key，如果元素不存在则不会做任何操作。
- contains(key)：判断 HashSet 是否包含元素 key，如果包含则返回 true，否则返回 false。
这个 HashSet 的实现基于一个基数为 666 的哈希表。在 add() 方法中，首先计算元素 key 的哈希值，如果元素已经存在则不重复添加。在 remove() 方法中，首先计算元素 key 的哈希值，然后遍历对应的数组，如果找到了元素则将其移除。在 contains() 方法中也是同样的流程，首先计算元素 key 的哈希值，然后判断对应的数组中是否包含该元素。
AC代码
/** * 初始化一个 MyHashSet 实例 */ var MyHashSet = function () { this.BASE = 666; // 哈希表的基数 this.data = new Array(this.BASE).fill(0).map(() => new Array()); // 哈希表 }; /** * 向 HashSet 中添加元素 key * @param {number} key - 待添加的元素 */ MyHashSet.prototype.add = function (key) { const h = this.hash(key); // 计算 key 的哈希值 if (this.data[h].includes(key)) return; // 如果元素已经存在，则不重复添加 this.data[h].push(key); // 添加元素到哈希表中 }; /** * 从 HashSet 中移除元素 key * @param {number} key - 待移除的元素 */ MyHashSet.prototype.remove = function (key) { const h = this.hash(key); // 计算 key 的哈希值 const it = this.data[h]; for (let i = 0; i < it.length; ++i) { if (it[i] === key) { // 如果找到了元素，则移除之 it.splice(i, 1); return; } } }; /** * 判断 HashSet 是否包含元素 key * @param {number} key - 待检查的元素 * @returns {boolean} - 如果包含则返回 true，否则返回 false */ MyHashSet.prototype.contains = function (key) { const h = this.hash(key); // 计算 key 的哈希值 return this.data[h].includes(key); // 判断是否在哈希表中 }; /** * 计算元素 key 的哈希值 * @param {number} key - 元素 * @returns {number} - 哈希值 */ MyHashSet.prototype.hash = function (key) { return key % this.BASE; // 取余数作为哈希值 };
公众号
关注公众号『前端也能这么有趣』，获取更多有趣内容。
说在后面
🎉 这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打羽毛球 🏸 ，平时也喜欢写些东西，既为自己记录 📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解 🙇，写错的地方望指出，定会认真改进 😊，偶尔也会在自己的公众号『
前端也能这么有趣』发一些比较有趣的文章，有兴趣的也可以关注下。在此谢谢大家的支持，我们下文再见 🙌。
