创建一个简单的哈希表你会吗？｜刷题打卡

平时我们在编程的时候，经常会用到哈希表处理和储存数据，那么如果让你实现一个简单的哈希表，你会怎么实现呢？

原题链接705. 设计哈希集合

一、先看题

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

实现 MyHashSet 类：

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

示例：

提示：

• 0<=key<=106
• 最多调用 104 次 add、remove 和 contains

二、整理思路

在我们实现简易哈希表的数据结构之前，我们首先要分析，对于题中给出的简易哈希表应该要有哪些功能，以及初步的实现思路。

第一步：

确认输入输出：

输入： $0-10^6$0−106的数

输出： 由示例可知，只有contains方法有bool值返回，其他方法无需返回值

第二步

怎么实现这个数据结构？

作为一个哈希表，我们首先肯定要有存储数据的属性，我们将其命名为data。

除了data外，还有题干中给出的三种方法：add、contains、remove。

由于无法使用内建的哈希表库，因此我们可以采取数组来进行模拟。除了题中的三种方法，也没有其他的要求，因此我们可以采取一些优化措施，比如存储的时候将数进行分组，从而避免冲突。

在这里我们使用整数除法来作为哈希函数。为了尽量避免冲突，我们将除数BASE定为一个质数。

因此，得到了下面的算法：

/**
 * Initialize your data structure here.
 */
var MyHashSet = function () {
    this.BASE = 971;
    this.data = new Array(this.BASE).fill(0).map(() => new Array())
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.add = function (key) {
    const h = key % this.BASE
    for (let ele of this.data[h]) {
        if (ele === key) return
    }
    this.data[h].push(key)
};

/** 
 * @param {number} key
 * @return {void}
 */
MyHashSet.prototype.remove = function (key) {
    const h = key % this.BASE
    for (let i = 0; i < this.data[h].length; i++) {
        if (this.data[h][i] === key) {
            this.data[h].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 = key % this.BASE
    return this.data[h].includes(key)
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * var obj = new MyHashSet()
 * obj.add(key)
 * obj.remove(key)
 * var param_3 = obj.contains(key)
 */

对于为什么质数取模，采用leetcoder@果然翁的原话就是：

三、总结

对于平时用习惯的基础数据结构，我们也应该适当深入了解下实现原理，这样才能更好地使用这些工具，最大化他们的使用价值。

本文正在参与「掘金 2021 春招闯关活动」, 点击查看 活动详情