02、设计哈希Set

其实你完成之前的 hashmap 之后，再来完成这个题目就非常简单了，我们先来看一下题目描述

题目描述

不使用任何内建的哈希表库设计一个哈希集合（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 方法

解题思路

数组 + 链表法（拉链法）

与 HashMap 类似，HashSet 也需要处理哈希冲突。区别在于 HashSet 只存储键（key），不存储值（value）。

因为我们只需要返回 true 或者

核心设计

1. 哈希函数：使用取模运算 hash(key) = key % SIZE
2. 冲突解决：使用链表存储哈希到同一位置的多个键（key 不同，但是 hash(key）是有可能相同的，所以会有冲突的情况）
3. 数据结构：链表节点只存储 key，不存储 value

暂时无法在飞书文档外展示此内容

代码实现

class MyHashSet {
private:
    // 定义链表节点
    struct Node {
        int key;
        Node* next;
        Node(int k) : key(k), next(nullptr) {}
    };

    static const int SIZE = 1009; // 选择质数作为哈希表大小
    Node* table[SIZE];            // 哈希表数组

    // 哈希函数
    int hash(int key) {
        return key % SIZE;
    }

public:
    MyHashSet() {
        // 初始化所有链表头为空
        for (int i = 0; i < SIZE; i++) {
            table[i] = nullptr;
        }
    }

    void add(int key) {
        int idx = hash(key);
        Node* curr = table[idx];

        // 遍历链表检查是否已存在
        while (curr != nullptr) {
            if (curr->key == key) {
                return; // 已存在，不重复添加
            }
            curr = curr->next;
        }

        // 未找到，插入到链表头
        Node* newNode = new Node(key);
        newNode->next = table[idx];
        table[idx] = newNode;
    }

    void remove(int key) {
        int idx = hash(key);
        Node* curr = table[idx];
        Node* prev = nullptr;

        // 遍历链表查找并删除
        while (curr != nullptr) {
            if (curr->key == key) {
                if (prev == nullptr) {
                    // 删除的是链表头节点
                    table[idx] = curr->next;
                } else {
                    // 删除的是中间或尾部节点
                    prev->next = curr->next;
                }
                delete curr;
                return;
            }
            prev = curr;
            curr = curr->next;
        }
    }

    bool contains(int key) {
        int idx = hash(key);
        Node* curr = table[idx];

        // 遍历链表查找
        while (curr != nullptr) {
            if (curr->key == key) {
                return true;
            }
            curr = curr->next;
        }

        return false;
    }

    ~MyHashSet() {
        // 析构函数，释放所有节点内存
        for (int i = 0; i < SIZE; i++) {
            Node* curr = table[i];
            while (curr != nullptr) {
                Node* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
    }
};

复杂度分析

拉链法

时间复杂度：

• add 操作：平均 O(1)，最坏 O(n)
• contains 操作：平均 O(1)，最坏 O(n)
• remove 操作：平均 O(1)，最坏 O(n)

空间复杂度：O(SIZE + n)，其中 n 是集合中元素数量