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 <= 106104 次 add、remove 和 contains相似题目
原站题解
python3 解法, 执行用时: 94 ms, 内存消耗: 21.1 MB, 提交时间: 2024-04-14 14:29:22
class MyHashSet:
def __init__(self):
self.buckets = 1009
self.table = [[] for _ in range(self.buckets)]
def hash(self, key):
return key % self.buckets
def add(self, key):
hashkey = self.hash(key)
if key in self.table[hashkey]:
return
self.table[hashkey].append(key)
def remove(self, key):
hashkey = self.hash(key)
if key not in self.table[hashkey]:
return
self.table[hashkey].remove(key)
def contains(self, key):
hashkey = self.hash(key)
return key in self.table[hashkey]
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
python3 解法, 执行用时: 176 ms, 内存消耗: 28.8 MB, 提交时间: 2024-04-14 14:29:04
class MyHashSet:
def __init__(self):
self.buckets = 1000
self.itemsPerBucket = 1001
self.table = [[] for _ in range(self.buckets)]
def hash(self, key):
return key % self.buckets
def pos(self, key):
return key // self.buckets
def add(self, key):
hashkey = self.hash(key)
if not self.table[hashkey]:
self.table[hashkey] = [0] * self.itemsPerBucket
self.table[hashkey][self.pos(key)] = 1
def remove(self, key):
hashkey = self.hash(key)
if self.table[hashkey]:
self.table[hashkey][self.pos(key)] = 0
def contains(self, key):
hashkey = self.hash(key)
return (self.table[hashkey] != []) and (self.table[hashkey][self.pos(key)] == 1)
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
python3 解法, 执行用时: 200 ms, 内存消耗: 42.7 MB, 提交时间: 2024-04-14 14:28:45
class MyHashSet:
def __init__(self):
self.set = [False] * 1000001
def add(self, key):
self.set[key] = True
def remove(self, key):
self.set[key] = False
def contains(self, key):
return self.set[key]
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
javascript 解法, 执行用时: 148 ms, 内存消耗: 60.9 MB, 提交时间: 2024-04-14 14:27:59
var MyHashSet = function() {
this.BASE = 769;
this.data = new Array(this.BASE).fill(0).map(() => new Array());
};
MyHashSet.prototype.add = function(key) {
const h = this.hash(key);
for (const element of this.data[h]) {
if (element === key) {
return;
}
}
this.data[h].push(key);
};
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;
}
}
};
MyHashSet.prototype.contains = function(key) {
const h = this.hash(key);
for (const element of this.data[h]) {
if (element === key) {
return true;
}
}
return false;
};
MyHashSet.prototype.hash = function(key) {
return key % this.BASE;
}
/**
* 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)
*/
java 解法, 执行用时: 16 ms, 内存消耗: 49.4 MB, 提交时间: 2024-04-14 14:27:37
class MyHashSet {
private static final int BASE = 769;
private LinkedList[] data;
/** Initialize your data structure here. */
public MyHashSet() {
data = new LinkedList[BASE];
for (int i = 0; i < BASE; ++i) {
data[i] = new LinkedList<Integer>();
}
}
public void add(int key) {
int h = hash(key);
Iterator<Integer> iterator = data[h].iterator();
while (iterator.hasNext()) {
Integer element = iterator.next();
if (element == key) {
return;
}
}
data[h].offerLast(key);
}
public void remove(int key) {
int h = hash(key);
Iterator<Integer> iterator = data[h].iterator();
while (iterator.hasNext()) {
Integer element = iterator.next();
if (element == key) {
data[h].remove(element);
return;
}
}
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
int h = hash(key);
Iterator<Integer> iterator = data[h].iterator();
while (iterator.hasNext()) {
Integer element = iterator.next();
if (element == key) {
return true;
}
}
return false;
}
private static int hash(int key) {
return key % BASE;
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
cpp 解法, 执行用时: 82 ms, 内存消耗: 44.3 MB, 提交时间: 2024-04-14 14:27:22
class MyHashSet {
private:
vector<list<int>> data;
static const int base = 769;
static int hash(int key) {
return key % base;
}
public:
/** Initialize your data structure here. */
MyHashSet(): data(base) {}
void add(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
return;
}
}
data[h].push_back(key);
}
void remove(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
data[h].erase(it);
return;
}
}
}
/** Returns true if this set contains the specified element */
bool contains(int key) {
int h = hash(key);
for (auto it = data[h].begin(); it != data[h].end(); it++) {
if ((*it) == key) {
return true;
}
}
return false;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
golang 解法, 执行用时: 92 ms, 内存消耗: 8.6 MB, 提交时间: 2021-06-23 18:16:06
const base = 769
type MyHashSet struct {
data []list.List
}
/** Initialize your data structure here. */
func Constructor() MyHashSet {
return MyHashSet{make([]list.List, base)}
}
func (this *MyHashSet) hash(key int) int {
return key % base
}
func (this *MyHashSet) Add(key int) {
if !this.Contains(key) {
h := this.hash(key)
this.data[h].PushBack(key)
}
return
}
func (this *MyHashSet) Remove(key int) {
h := this.hash(key)
for e := this.data[h].Front(); e != nil; e = e.Next() {
if e.Value.(int) == key {
this.data[h].Remove(e)
return
}
}
}
/** Returns true if this set contains the specified element */
func (this *MyHashSet) Contains(key int) bool {
h := this.hash(key)
for e := this.data[h].Front(); e != nil; e = e.Next() {
if e.Value.(int) == key {
return true
}
}
return false
}
/**
* Your MyHashSet object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(key);
* obj.Remove(key);
* param_3 := obj.Contains(key);
*/