【Leetcode】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 <= 10^6$
最多调用 $10^4$ 次 add、remove 和 contains

思路分析

哈希集合HashSet 是指能以 O(1) 时间进行插入和删除，可以保存不重复元素的一种数据结构。（需要区别于HashMap，以 key : value 形式存储数据。Python中HashMap即为dict、collections.OrderedDict，可详见该篇底层实现原理分析）

本问题中由于key都是int类型，因此我们可以直接采用一个数组存放，即HashSet[key]=key。这样插入、删除和查找元素的时间复杂度都为O(1)。但空间复杂度为O(n)，当数据量特别大时，空间复杂度很高。我们需要设计一个更好的算法。

回顾数据结构知识。设计一个哈希集合，一般需要考虑这几个条件：

散列函数。将待存储的key映射到散列表中。常用的hash函数是取模运算，为了减少冲突，模一般为质数。
冲突处理。当不同的key被映射到散列表的同一位置，就需要处理冲突。常用的是链地址法，散列表的元素不直接存储元素而是会指向一个链表表头，链表中保存key及后续冲突的key。
可扩展性。当当前散列表已经不能满足继续存储元素时（例如每个位置都满了、冲突也已经很多），需要能够对散列表扩容。

我们依照实现即可。
（1）散列函数。数据规模最大为 $10^6$ ，我们考虑建一个长度为 $10^4$ 的散列表， $10^2$ 为容许的冲突个数。根据质数表，取一个接近的质数为10009。
（2）冲突处理。就使用最经典的链地址法。散列函数映射结果相同的key，存储在散列表同一位置指向的链表（或数组）中，追加在链表（或数组）末尾。
（3）散列表使用固定大小的数组，提前确定了长度并分配内存。若要扩容，需要增加数组长度，并重新计算每个元素的散列值重新排放。

Python中，散列表和链表均使用数组方便直接调用内置函数。

代码示例

class MyHashSet:def __init__(self):# 初始化时创建散列表（固定大小的数组），散列表的每个元素也是一个数组（存储哈希映射结果冲突的key，动态增删元素）。其实就是一个二维数组。self.buckets = 10009 # 散列表长度self.HashSet = [[] for _ in range(self.buckets)]  # 注意这里要用列表生成式创建n个为空的数组，否则用[[]*n]只会创建1个[]。def hashfunc(self, key):return key % self.bucketsdef add(self, key: int) -> None:hashedkey = self.hashfunc(key)if key in self.HashSet[hashedkey]:returnself.HashSet[hashedkey].append(key)def remove(self, key: int) -> None:hashedkey = self.hashfunc(key)if key not in self.HashSet[hashedkey]:return self.HashSet[hashedkey].remove(key)def contains(self, key: int) -> bool:hashedkey = self.hashfunc(key)if key in self.HashSet[hashedkey]:return Trueelse:return False

算法复杂度分析

时间复杂度： $O(\frac{n}{m})$ 。 n是待存储个数，m是散列表长度，寻找散列表中的元素位置只需找到下标为hashedvalue的元素即可，时间复杂度为 $O (1)$ ，因此时间复杂度取决于遍历存放hashedvalue冲突的元素的数组时的时间消耗，这里为元素个数最多为 $\frac{n}{m}$ ，故时间复杂度为 $O(\frac{n}{m})$ 。
空间复杂度： $O (n + m)$ 。空间消耗为散列表+冲突处理数组。