Easy

题目描述

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

  • void add(key) 向哈希集合中插入值 key。
  • bool contains(key) 返回哈希集合中是否存在这个值 key。
  • void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

示例 1：

输入：
["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

解题思路

这道题要求我们不使用内建的哈希表实现一个哈希集合。有几种常见的实现方式：

解法一：直接数组（推荐）

由于题目限制 key 的范围是 0 到 10^6，我们可以直接使用一个布尔数组来存储每个 key 是否存在。这是最简单直观的方法，时间复杂度为 O(1)，但空间复杂度较高。

解法二：链表数组（哈希表 + 链表）

使用一个固定大小的数组，每个位置存储一个链表。通过哈希函数将 key 映射到数组索引，处理哈希冲突时使用链表。这种方法更节省空间，是真正的哈希表实现。

解法三：二维数组分桶

将大范围的数字分成多个桶，每个桶用一个数组表示。这是对解法一的优化，既保证了 O(1) 的时间复杂度，又减少了空间使用。

本题解采用解法一，因为它实现简单且效率最高。对于实际面试，也可以讨论解法二来展示对哈希表原理的理解。

代码实现

class MyHashSet {
private:
    vector<bool> data;
public:
    MyHashSet() {
        data.resize(1000001, false);
    }
    
    void add(int key) {
        data[key] = true;
    }
    
    void remove(int key) {
        data[key] = false;
    }
    
    bool contains(int key) {
        return data[key];
    }
};

class MyHashSet:

    def __init__(self):
        self.data = [False] * 1000001

    def add(self, key: int) -> None:
        self.data[key] = True

    def remove(self, key: int) -> None:
        self.data[key] = False

    def contains(self, key: int) -> bool:
        return self.data[key]

public class MyHashSet {
    private bool[] data;

    public MyHashSet() {
        data = new bool[1000001];
    }
    
    public void Add(int key) {
        data[key] = true;
    }
    
    public void Remove(int key) {
        data[key] = false;
    }
    
    public bool Contains(int key) {
        return data[key];
    }
}

var MyHashSet = function() {
    this.data = new Array(1000001).fill(false);
};

MyHashSet.prototype.add = function(key) {
    this.data[key] = true;
};

MyHashSet.prototype.remove = function(key) {
    this.data[key] = false;
};

MyHashSet.prototype.contains = function(key) {
    return this.data[key];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
addO(1)O(1)
removeO(1)O(1)
containsO(1)O(1)
总空间复杂度-O(10^6)

注：总空间复杂度为 O(10^6) 是因为我们预分配了一个大小为 1000001 的数组来覆盖所有可能的 key 值。

相关题目