【C++刷题】力扣-#705-设计哈希集合

题目描述

设不使用任何内建的哈希表库设计一个哈希集合（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 是一个素数，可以减少哈希冲突的概率。

1. 初始化哈希集合：创建一个大小为 base 的 vector，每个元素是一个空的 list。
2. 添加元素：计算元素的哈希值，然后在对应的链表中添加元素。
3. 移除元素：计算元素的哈希值，然后在对应的链表中移除元素。
4. 检查元素：计算元素的哈希值，然后在对应的链表中检查元素是否存在。

代码实现

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 的组合提供了一个高效的哈希集合实现。