LeetCode 705. 设计哈希集合

2024-11-03 HGNULB 约 11 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 705. 设计哈希集合

题意分析

不借助任何内建的哈希表库，自己实现一个只装非负整数的集合，支持三个操作：add(key) 插入（已存在则无效果）、remove(key) 删除（不存在则无效果）、contains(key) 查询是否存在。

要什么：一个满足集合语义的数据结构。集合语义的核心是幂等——重复 add 同一个 key 不应产生第二份，重复 remove 不应报错。这一点决定了内部表示必须是「每个 key 对应一个唯一的存在位」，而不是可追加的列表。

约束透露的信号极其关键：0 <= key <= 10^6，调用次数最多 $10^4$。键的值域有限且很小，这是整道题最重要的一句话。值域封闭意味着我们可以为每一个可能的键预留一个专属位置，从而把「哈希」这个动作退化成「直接用键当下标」——恒等映射本身就是一个完美哈希，零冲突。$10^6 + 1$ 个 boolean 在 Java 中占约 1 MB，完全在内存限制之内。

反过来说，如果题目把值域放开到整个 int 范围甚至任意对象，直接寻址就不可行了，那时才必须回到真正的哈希设计：取模分桶 + 冲突处理 + 负载因子扩容。识别出「值域是否封闭」，就是识别出该走哪条路。

边界：key = 0 和 key = 10^6 都是合法输入，数组长度必须开到 $10^6 + 1$ 而不是 $10^6$；对不存在的 key 调用 remove 必须静默成功而不是抛异常；contains 在从未 add 过的 key 上必须返回 false，这要求数组初值全为 false（Java 与 Go 的数组/切片默认零值恰好满足）。

解法：固定域布尔数组

核心思路

先看一个显然可行但很差的做法：用一个动态数组存所有已插入的键，contains 线性扫描、add 先扫描去重再追加、remove 扫描后删除。三个操作都是 $O(S)$（$S$ 为当前元素个数），$10^4$ 次调用下最坏约 $10^8$ 次比较，而且 remove 还要处理元素搬移。瓶颈很清楚：每次操作都在「查找 key 在哪」上花线性时间。

真正的哈希表用「哈希函数把 key 映射到桶下标」来把查找压到均摊 $O(1)$，代价是要处理两个 key 撞进同一个桶的冲突。但冲突本身是「值域比桶数大得多」被迫压缩的产物。本题的值域只有 $10^6 + 1$ 个取值，而我们完全开得起 $10^6 + 1$ 个桶——于是可以选择最朴素的哈希函数：
\[h(key) = key\]
这个恒等映射是单射，不同的 key 永远落在不同的下标上，冲突率恒为 0。冲突处理、负载因子、扩容重哈希这三大块复杂度直接消失。这种技巧叫直接寻址表（direct-address table），它是哈希表在「值域可枚举」这一特例下的退化形态。

于是内部表示定为一个长度 $10^6 + 1$ 的布尔数组 data，不变量是：

对任意 $0 \le key \le 10^6$，data[key] == true 当且仅当 key 当前在集合中。

三个操作在这个不变量下都退化成一行：add 是把对应位置为 true，remove 是置为 false，contains 是直接读取。集合的幂等性也是白送的——把一个已经是 true 的位置再置 true，值不变；对已经是 false 的位置再置 false，同样不变。这正是「用布尔位而非计数器/列表」的好处：赋值天然幂等，而 count++ 或 list.add 都不是。

唯一的代价是空间：无论集合里实际只有 1 个元素还是 $10^4$ 个元素，都固定占用 $10^6 + 1$ 字节。这是一次明确的空间换时间且换简洁的交易，在值域已知且不大时非常划算。

解题步骤

构造函数中分配长度为 1_000_001 的布尔数组。为什么是 1_000_001 而不是 1_000_000：题面的键范围是闭区间 $[0, 10^6]$，两端都取得到，共 $10^6 + 1$ 个合法值；开成 $10^6$ 会在 key = 10^6 时越界。为什么可以在构造时一次性分配：调用次数有限而值域固定，预分配避免了运行期任何扩容判断，也让三个操作彻底无分支。

数组不需要显式初始化。为什么：Java 的 new boolean[n] 保证全部元素为 false，Go 的 make([]bool, n) 同样是零值 false，而 false 恰好就是「不在集合中」的正确初始语义。若把存在性用 int 的 0/1 表示也可以，但布尔更贴合语义且省内存。

add(key) 执行 data[key] = true。为什么不先判断是否已存在：赋值是幂等的，重复插入不会破坏不变量；多一次判断只会增加分支预测失败的机会，没有任何收益。

remove(key) 执行 data[key] = false。为什么删除不存在的 key 也安全：同样是幂等赋值，把 false 写成 false 不改变任何状态，天然满足「不存在则无效果」的要求，不需要任何特判或异常。

contains(key) 直接返回 data[key]。为什么不需要边界检查：题面已保证 key 落在合法范围内，数组长度覆盖了整个范围；如果是工程代码而非竞赛代码，这里应当补上范围校验。

data 声明为 final（Java）。为什么：数组引用在对象生命周期内不再改变，标记 final 既表达了「这个表不会被替换或扩容」的设计意图，也让 JIT 可以更激进地优化字段访问。

以 具体用例 走一遍完整的调用序列：
MyHashSet(); add(1); add(2); contains(1); contains(3); add(2); contains(2); remove(2); contains(2);
MyHashSet()：分配 data，长度 $10^6 + 1$，全部为 false。此时集合为空，不变量成立（所有位置都是 false，集合里确实没有任何元素）。
add(1)：data[1] = true。集合内容 {1}。
add(2)：data[2] = true。集合内容 {1, 2}。
contains(1)：读 data[1]，得 true，返回 true。正确。
contains(3)：读 data[3]，从未被写过，仍是初始的 false，返回 false。正确——这里体现了「零值即默认语义」的价值，不需要任何「是否被初始化过」的额外判断。
add(2)：data[2] 本已是 true，再赋 true 值不变。集合仍是 {1, 2} 而不是 {1, 2, 2}。这一步验证了集合的幂等性——如果内部改用「计数器 +1」或「链表追加」，这里就会错误地产生第二份 2。
contains(2)：返回 true。正确。
remove(2)：data[2] = false。集合内容 {1}。
contains(2)：读 data[2]，得 false，返回 false。正确。

再补一个边界调用 remove(999999)：该位置从未被写过、本就是 false，赋 false 后依然是 false，函数正常返回，没有异常，集合内容不变。这验证了「删除不存在的元素必须静默成功」。

代码实现

class MyHashSet {
    // 这类题不是考察散列冲突方案，而是考察“在固定值域里如何用最少复杂度实现常量操作”。
    private final boolean[] data;

    public MyHashSet() {
        data = new boolean[1_000_001];
    }

    public void add(int key) {
        data[key] = true;
    }

    public void remove(int key) {
        data[key] = false;
    }

    public boolean contains(int key) {
        return data[key];
    }
}

type MyHashSet struct {
    // 这类题不是考察散列冲突方案，而是考察“在固定值域里如何用最少复杂度实现常量操作”。
    data []bool
}

func ConstructorMyHashSet() MyHashSet {
    return MyHashSet{data: make([]bool, 1_000_001)}
}

func (this *MyHashSet) Add(key int) {
    this.data[key] = true
}

func (this *MyHashSet) Remove(key int) {
    this.data[key] = false
}

func (this *MyHashSet) Contains(key int) bool {
    return this.data[key]
}

复杂度分析

时间复杂度：三个操作均为最坏 $O(1)$。凭什么：恒等哈希是单射，不存在冲突，因此没有任何探测循环或链表遍历；每个操作只是一次数组下标读或写，是真正的最坏情况常数而非均摊常数——这一点强于工业级哈希表，后者在扩容重哈希那一次调用上是 $O(n)$。构造函数是 $O(V)$，$V = 10^6 + 1$ 为值域大小。

空间复杂度：$O(V)$，即 $10^6 + 1$ 个布尔值，Java 中约 1 MB。凭什么不是 $O(1)$ 也不是 $O(n)$：占用量既与实际元素个数 $n$ 无关（存 1 个和存 $10^4$ 个一样大），也不是常数（它随题目给定的值域上界线性增长）。这正是直接寻址表的本质代价：用与值域成正比的空间，换取零冲突的常数时间。

关键点总结

先看值域，再选结构。「键的取值范围有限且不大」是直接寻址表的准入条件；一旦满足，哈希函数取恒等映射即可，冲突处理、负载因子、扩容三大块复杂度全部消失。这个判断在位图去重、计数排序、桶排序、字符频次统计里反复出现，是同一条原则的不同外衣。

幂等的表示天然给出幂等的操作。用布尔位表达「在/不在」，add 与 remove 都是赋值，重复调用零副作用；若改用计数器或链表追加，就必须额外写去重逻辑。设计数据结构时，让不变量把边界情况吃掉，比事后打补丁可靠得多。

让语言的零值承担默认语义。false 恰好等于「不在集合中」，于是构造函数一行不写也能保证初始状态正确；反之若用 -1 表示空、0 表示某个合法状态，就必须显式填充整个数组。选表示法时优先让零值有意义。

空间换时间是一次要说清代价的交易。这里固定花 1 MB，无论集合里有几个元素。当值域扩大到 $10^9$ 或键是任意对象时，这笔交易立刻不成立，必须换方案。

同样的思路可以再压缩 8 倍：用 long[] bits = new long[(1_000_001 >> 6) + 1]，把每个键映射到 bits[key >> 6] 的第 key & 63 位，add 是 |= 1L << (key & 63)，remove 是 &= ~(1L << (key & 63))，contains 是 (bits[key >> 6] >>> (key & 63) & 1) == 1。空间从 1 MB 降到 128 KB，时间仍是 $O(1)$。这就是位图（bitset），面试中主动提出往往是加分项。

面试视角：这道题挂着「设计」标签，面试官很可能不满足于直接寻址表，会追问「如果 key 是任意 32 位整数，或者内存只有 64 KB 呢」。标准答案是回到真正的哈希设计：开一个质数大小（如 769）的桶数组，hash(key) = key % 769，每个桶挂一条链表（或用 ArrayList），add 先在桶内查重再头插，remove 在桶内删除，contains 在桶内线性查找；元素数超过 桶数 × 负载因子 时扩容并重哈希。回答时要能说清「链地址法 vs 开放寻址法」的取舍、「桶数取质数是为了让低位分布更均匀」、以及「均摊 $O(1)$ 与最坏 $O(n)$ 的区别」。把直接寻址表当作「值域封闭时的特例优化」讲出来，而不是当作唯一解法，才是这题该有的答法。

易错点总结

错误写法：data = new boolean[1_000_000]（少开一格） → 用例 add(1000000)，题面允许 key 取到 $10^6$，此时下标等于数组长度，直接抛 ArrayIndexOutOfBoundsException。闭区间 $[0, N]$ 需要 $N + 1$ 个格子。

错误写法：在 add 里写 if (!data[key]) data[key] = true; → 逻辑正确但毫无收益，多出的分支在 $10^4$ 次调用里纯属浪费；更糟的是这种写法容易被顺手改成 count++ 之类的副作用，破坏幂等性。

错误写法：用 int[] count 记录出现次数，add 时 count[key]++、remove 时 count[key]-- → 用例 add(1); add(1); remove(1); contains(1)，计数从 0 加到 2 再减到 1，contains 返回 true；集合语义下正确答案是 false，因为集合里 1 只应存在一份。

错误写法：用 ArrayList<Integer> 存元素，add 直接 list.add(key) 不查重 → 用例 add(1); add(1); remove(1); contains(1)，列表里有两个 1，删掉一个还剩一个，返回 true，错误；同时三个操作都退化成 $O(S)$。

错误写法：remove 里先判断存在性，不存在就抛异常或返回错误 → 用例 remove(5) 在空集合上调用，题面要求静默无效果，抛异常会直接判错。删除操作在集合语义下必须容忍不存在的键。

错误写法：把数组声明成静态字段 private static boolean[] data → 用例是判题程序连续构造两个 MyHashSet 实例时，第二个实例会继承第一个实例残留的所有元素，contains 返回莫名其妙的 true。实例状态必须是实例字段。

错误写法：为了省内存改用 HashSet<Integer> 或 Set 接口的内建实现 → 逻辑上能过，但题面明确要求「不使用任何内建的哈希库」，这是直接绕开考点，面试中等同于没答。

错误写法：改用取模分桶 int idx = key % 1000 却把桶里存成单个 int 而非链表 → 用例 add(1); add(1001); contains(1)，两个键都映射到桶 1，后者覆盖前者，contains(1) 返回 false。一旦哈希函数不是单射，就必须配套冲突处理。

错误写法：改用位图但把移位量写成 1 << (key & 63)（用 int 字面量 1） → 用例 add(64)，key & 63 = 0 尚且正常，但 add(127) 时 key & 63 = 63，1 << 63 在 int 下按 63 % 32 = 31 处理，得到 Integer.MIN_VALUE 再符号扩展成 long，把整个高 32 位全部置 1，污染了 32 个不相关的键。移位必须写成 1L << ...。

错误写法：Go 中把接收者写成值类型 func (this MyHashSet) Add(key int) → 用例 add(1); contains(1)，虽然切片底层数组是共享的所以本题侥幸能过，但一旦结构体里增加了 size 之类的标量字段，对它的修改就会作用在副本上而丢失。设计类题目的所有方法应统一用指针接收者。

相似题目

题目	难度	考察点
706. 设计哈希映射	简单	从「存在性」升级到「键值对」，直接寻址表要存值且需要一个哨兵表示「无此键」
217. 存在重复元素	简单	集合的最直接应用，元素值域不受限，只能用真正的哈希集合或先排序
349. 两个数组的交集	简单	用集合做去重与求交，考的是把「查存在性」这个 $O(1)$ 能力用在双数组上
380. O(1) 时间插入、删除和获取随机元素	中等	集合外还要支持等概率随机取，必须「数组 + 哈希表」双向索引并用尾部交换做删除
146. LRU 缓存	中等	哈希表提供 $O(1)$ 定位，双向链表维护访问顺序，考的是两种结构的组合
208. 实现 Trie (前缀树)	中等	同样是「值域有限（26 个字母）所以直接用下标」，但按字符逐层展开成树
1206. 设计跳表	困难	键值域无限且要求有序，只能靠随机化的多层链表做到期望 $O(\log n)$
622. 设计循环队列	中等	同为定长数组的设计题，难点在用取模复用空间以及区分「队满」与「队空」
155. 最小栈	中等	设计题的另一类范式：靠辅助栈把「查询极值」也压到 $O(1)$