705. 设计哈希集合
705. 设计哈希集合
🟢 🔖 设计
数组
哈希表
链表
哈希函数
🔗 力扣
LeetCode
题目
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet
class:
void add(key)
Inserts the valuekey
into the HashSet.bool contains(key)
Returns whether the valuekey
exists in the HashSet or not.void remove(key)
Removes the valuekey
in the HashSet. Ifkey
does not exist in the HashSet, do nothing.
Example 1:
Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]
Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // return False,(already removed)
Constraints:
0 <= key <= 10^6
- At most
104
calls will be made toadd
,remove
, andcontains
.
题目大意
不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现 MyHashSet
类:
void add(key)
向哈希集合中插入值key
。bool contains(key)
返回哈希集合中是否存在这个值key
。void remove(key)
将给定值key
从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
解题思路
链地址法:
- 设哈希表的大小为
base
,则可以设计一个简单的哈希函数:hash(x) = x mod base
; - 开辟一个大小为
base
的数组,数组的每个位置是一个链表。当计算出哈希值之后,就插入到对应位置的链表当中; - 由于使用整数除法作为哈希函数,为了尽可能避免冲突,应当将
base
取为一个质数,如base = 769
;
复杂度分析
- 时间复杂度:
O(n / b)
。其中n
为哈希表中的元素数量,b
为链表的数量,假设哈希值是均匀分布的,则每个链表大概长度为n / b
; - 空间复杂度:
O(n+b)
。
代码
class MyHashSet {
constructor() {
this.base = 769;
this.data = new Array(this.base).fill(0).map(() => new Array());
}
// @param {number} key
// @return {number}
hash(key) {
return key % this.base;
}
// @param {number} key
// @return {void}
add(key) {
const h = this.hash(key);
for (let item of this.data[h]) {
if (item === key) return;
}
this.data[h].push(key);
}
// @param {number} key
// @return {void}
remove(key) {
const h = this.hash(key);
const hList = this.data[h];
for (let i = 0; i < hList.length; i++) {
if (hList[i] === key) {
hList.splice(i, 1);
return;
}
}
}
// @param {number} key
// @return {boolean}
contains(key) {
const h = this.hash(key);
for (let item of this.data[h]) {
if (item === key) return true;
}
return false;
}
}
/**
* 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)
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
706 | 设计哈希映射 | [✓] | 设计 数组 哈希表 2+ | 🟢 | 🀄️ 🔗 |
1206 | 设计跳表 | 设计 链表 | 🔴 | 🀄️ 🔗 |