题目描述
设不使用任何内建的哈希表库设计一个哈希集合（HashSet）。 实现 MyHashSet 类：
● void add(key) 向哈希集合中插入值 key 。
● bool contains(key) 返回哈希集合中是否存在这个值 key 。
● void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。
示例
MyHashSet hashSet = new MyHashSet();
hashSet.add(1);
hashSet.add(2);
hashSet.contains(1); // 返回 true
hashSet.remove(2);
hashSet.contains(2); // 返回 false
题解
我们使用一个二维容器 data，其中每个元素是一个链表，来解决哈希冲突。选择一个合适的哈希函数，这里使用 hash(key) = key % base，其中 base 是一个素数，可以减少哈希冲突的概率。
- 初始化哈希集合：创建一个大小为 base 的 vector，每个元素是一个空的 list。
- 添加元素：计算元素的哈希值，然后在对应的链表中添加元素。
- 移除元素：计算元素的哈希值，然后在对应的链表中移除元素。
- 检查元素：计算元素的哈希值，然后在对应的链表中检查元素是否存在。
代码实现
class MyHashSet {vector<list<int>>data; // 二维容器，表示一个动态数组，数组的每个元素是一个链表(list是一个双向链表)static const int base = 769; // 为什么答案要用静态变量static int hash(int x) { return x % base; }public:MyHashSet() : data(base) { // 初始化之后data就包含了769个list<int>}void add(int key) {int h = hash(key); // 得到地址，取出vector在这个地址上的数据，本质上是一个链表的头指针for (list<int>::iterator it = data[h].begin(); it != data[h].end();it++) { // it是链表的指针，一个list={1,2,3,4}长这个样子if ((*it) == key) { // 所有*it直接可以取出数据return;}}data[h].push_back(key); // 向哈希集合里面插入值}void remove(int key) {int h = hash(key);for (list<int>::iterator it = data[h].begin(); it != data[h].end();it++) {if ((*it) == key) {data[h].erase(it); // 或者是pop_back()return;}}}bool contains(int key) {int h = hash(key);for (list<int>::iterator it = data[h].begin(); it != data[h].end();it++) {if ((*it) == key) {return true;}}return false;}
};
复杂度分析
● 时间复杂度：
○ add 操作：平均情况下是 O(1)，最坏情况下是 O(n)，其中 n 是哈希桶中链表的长度。
○ remove 操作：平均情况下是 O(1)，最坏情况下是 O(n)。
○ contains 操作：平均情况下是 O(1)，最坏情况下是 O(n)。
● 空间复杂度：O(m)，其中 m 是哈希集合中存储的元素总数。这里使用了一个大小为 base 的 vector 和若干个 list。
这个实现利用了链地址法来解决哈希冲突，通过 vector 和 list 的组合提供了一个高效的哈希集合实现。