705. 设计哈希集合
题目描述
不借助任何语言自带的哈希表库，自己实现一个整数集合类 MyHashSet。
MyHashSet()：创建空集合。add(key)：把 key 加入集合，已存在时不变，无返回值。remove(key)：把 key 从集合中删掉，不存在时什么也不做，无返回值。contains(key)：集合中有 key 时返回 true，否则返回 false。
测试数据以方法名序列和参数序列给出，输出数组是每次调用的返回值，无返回值的调用对应 null。
示例 1
输入：操作 = ["MyHashSet","add","add","add","remove","contains","add","add","add","remove","contains","add","add","add","remove","contains","add","add","add","remove","contains"] 参数 = [[],[1],[10001],[1],[1],[1],[7],[10007],[7],[7],[7],[123],[10123],[123],[123],[123],[5000],[15000],[5000],[5000],[5000]] 输出：[null,null,null,null,null,false,null,null,null,null,false,null,null,null,null,false,null,null,null,null,false]
解释：每组操作都先加入某个数（含重复加入），再把它删掉，所以随后的 contains 都返回 false。
数据范围
0 <= key <= 10^6add、remove、contains合计最多调用10^4次。
解题思路：链地址法
链地址法：开 base 个桶（取质数 769），key 放进第 key % base 个桶。每个桶是一个小链表/数组，冲突的 key 挤在同一个桶里。add 前先查桶里是否已有，避免重复；remove 只在桶里找到时删除；contains 只查一个桶。
为什么正确
任意时刻，每个已加入的 key 恰好出现一次，且只出现在第 key % base 个桶中。
复杂度分析
设 n 为元素个数，每次操作平均 O(1 + n / base)；空间 O(base + n)。
易错点
add 前一定要先判断是否已存在，否则重复 add 后 remove 一次仍然能查到。remove 一个不存在的 key 不能报错。桶数取质数可以让 key 分布更均匀。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class MyHashSet:
def __init__(self, base: int = 769):
self.base = base
self.buckets = [[] for _ in range(base)]
def add(self, key: int) -> None:
b = self.buckets[key % self.base]
if key not in b:
b.append(key)
def remove(self, key: int) -> None:
b = self.buckets[key % self.base]
if key in b:
b.remove(key)
def contains(self, key: int) -> bool:
b = self.buckets[key % self.base]
return key in bclass MyHashSet {
private int base;
private List<List<Integer>> buckets;
public MyHashSet() {
base = 769;
buckets = new ArrayList<>();
for (int i = 0; i < base; i++) buckets.add(new ArrayList<>());
}
public void add(int key) {
List<Integer> b = buckets.get(key % base);
if (!b.contains(key)) {
b.add(key);
}
}
public void remove(int key) {
List<Integer> b = buckets.get(key % base);
if (b.contains(key)) {
b.remove(Integer.valueOf(key));
}
}
public boolean contains(int key) {
List<Integer> b = buckets.get(key % base);
return b.contains(key);
}
}class MyHashSet {
public:
int base;
vector<list<int>> buckets;
MyHashSet() {
base = 769;
buckets.assign(base, list<int>());
}
void add(int key) {
auto& b = buckets[key % base];
if (find(b.begin(), b.end(), key) == b.end()) {
b.push_back(key);
}
}
void remove(int key) {
auto& b = buckets[key % base];
auto it = find(b.begin(), b.end(), key);
if (it != b.end()) {
b.erase(it);
}
}
bool contains(int key) {
auto& b = buckets[key % base];
return find(b.begin(), b.end(), key) != b.end();
}
};type MyHashSet struct {
base int
buckets [][]int
}
func Constructor() MyHashSet {
base := 769
return MyHashSet{base: base, buckets: make([][]int, base)}
}
func (this *MyHashSet) find(key int) int {
for i, x := range this.buckets[key%this.base] {
if x == key {
return i
}
}
return -1
}
func (this *MyHashSet) Add(key int) {
h := key % this.base
if this.find(key) < 0 {
this.buckets[h] = append(this.buckets[h], key)
}
}
func (this *MyHashSet) Remove(key int) {
h := key % this.base
if i := this.find(key); i >= 0 {
this.buckets[h] = append(this.buckets[h][:i], this.buckets[h][i+1:]...)
}
}
func (this *MyHashSet) Contains(key int) bool {
_ = key % this.base
return this.find(key) >= 0
}var MyHashSet = function() {
this.base = 769;
this.buckets = Array.from({ length: this.base }, () => []);
};
MyHashSet.prototype.add = function(key) {
const b = this.buckets[key % this.base];
if (!b.includes(key)) {
b.push(key);
}
};
MyHashSet.prototype.remove = function(key) {
const b = this.buckets[key % this.base];
const i = b.indexOf(key);
if (i >= 0) {
b.splice(i, 1);
}
};
MyHashSet.prototype.contains = function(key) {
const b = this.buckets[key % this.base];
return b.includes(key);
};class MyHashSet {
base: number;
buckets: number[][];
constructor() {
this.base = 769;
this.buckets = Array.from({ length: this.base }, () => []);
}
add(key: number): void {
const b = this.buckets[key % this.base];
if (!b.includes(key)) {
b.push(key);
}
}
remove(key: number): void {
const b = this.buckets[key % this.base];
const i = b.indexOf(key);
if (i >= 0) {
b.splice(i, 1);
}
}
contains(key: number): boolean {
const b = this.buckets[key % this.base];
return b.includes(key);
}
}其他解法
链地址法用取模把 key 分到少量桶里，内存随元素数增长；位图直接按值寻址，快但内存随值域增长。
解法 2：位图 时间 O(1)，空间 O(U / 32)
key 的范围是 0 到 10⁶，可以给每个可能的 key 分配一个二进制位。用 32 位整数数组存放，key 对应第 key / 32 个整数的第 key % 32 位。add 把该位置 1，remove 把该位清 0，contains 检查该位。
每次操作都是 O(1)，没有冲突。代价是内存取决于 key 的值域 U 而不是元素个数，值域很大时不可用。
class MyHashSet:
def __init__(self):
self.bits = [0] * (1000001 // 32 + 1)
def add(self, key: int) -> None:
self.bits[key >> 5] |= 1 << (key & 31)
def remove(self, key: int) -> None:
self.bits[key >> 5] &= ~(1 << (key & 31))
def contains(self, key: int) -> bool:
return self.bits[key >> 5] >> (key & 31) & 1 == 1class MyHashSet {
private final int[] bits = new int[1000001 / 32 + 1];
public MyHashSet() {}
public void add(int key) {
bits[key >> 5] |= 1 << (key & 31);
}
public void remove(int key) {
bits[key >> 5] &= ~(1 << (key & 31));
}
public boolean contains(int key) {
return (bits[key >> 5] >>> (key & 31) & 1) == 1;
}
}class MyHashSet {
vector<unsigned int> bits;
public:
MyHashSet() : bits(1000001 / 32 + 1, 0) {}
void add(int key) {
bits[key >> 5] |= 1u << (key & 31);
}
void remove(int key) {
bits[key >> 5] &= ~(1u << (key & 31));
}
bool contains(int key) {
return bits[key >> 5] >> (key & 31) & 1u;
}
};type MyHashSet struct {
bits []uint32
}
func Constructor() MyHashSet {
return MyHashSet{bits: make([]uint32, 1000001/32+1)}
}
func (this *MyHashSet) Add(key int) {
this.bits[key>>5] |= 1 << (key & 31)
}
func (this *MyHashSet) Remove(key int) {
this.bits[key>>5] &^= 1 << (key & 31)
}
func (this *MyHashSet) Contains(key int) bool {
return this.bits[key>>5]>>(key&31)&1 == 1
}class MyHashSet {
constructor() {
this.bits = new Uint32Array((1000001 >> 5) + 1);
}
add(key) {
this.bits[key >> 5] |= 1 << (key & 31);
}
remove(key) {
this.bits[key >> 5] &= ~(1 << (key & 31));
}
contains(key) {
return ((this.bits[key >> 5] >>> (key & 31)) & 1) === 1;
}
}class MyHashSet {
bits: Uint32Array;
constructor() {
this.bits = new Uint32Array((1000001 >> 5) + 1);
}
add(key: number): void {
this.bits[key >> 5] |= 1 << (key & 31);
}
remove(key: number): void {
this.bits[key >> 5] &= ~(1 << (key & 31));
}
contains(key: number): boolean {
return ((this.bits[key >> 5] >>> (key & 31)) & 1) === 1;
}
}