LeetCode-Go 题解：705. Design HashSet 不使用内置库的哈希集合设计与实现

LeetCode-Go 题解：705. Design HashSet 不使用内置库的哈希集合设计与实现

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go

导读

本文围绕 LeetCode 第 705 题「Design HashSet」展开，讲解在不借助任何内置哈希表库的前提下，如何用 Go 语言从零实现一个支持add、remove、contains三个操作的哈希集合（HashSet）。文章以 leetcode/0705.Design-HashSet/README.md 的题目与解题思路为主体，结合本仓库 705. Design HashSet.go 的实际实现与 705. Design HashSet_test.go 测试用例，逐步推导出基于「布尔数组直查」的最简方案，并对比 706. Design HashMap 的链地址法实现，帮助读者掌握哈希集合设计的两类经典思路及其适用边界。读完本文，你将能够独立写出可在 LeetCode 上通过全部用例、运行时间击败 100% 提交的 Go 版 HashSet，并理解其背后的取舍逻辑。

一、题目背景与核心约束

1.1 题目原文（原题简述）

LeetCode 705. Design HashSet 要求设计一个哈希集合，不可以使用任何内置的哈希表库。具体来说，需要包含以下三个函数：

• add(value)：向哈希集合中插入一个值；
• contains(value)：返回该值是否存在于哈希集合中；
• remove(value)：将给定值从哈希集合中删除，如果集合中不存在该值，则什么都不做。

1.2 题目大意（中文转述）

题目本质上是要求手写一个最简单的集合（Set）数据结构：元素唯一、支持增删查。与哈希映射（HashMap）不同，集合只关心「键是否存在」，不存储任何关联值，因此实现可以更加精简。

1.3 关键约束条件

原文档明确给出了三条约束，它们是选择实现方案的决定性因素：

注意：题目英文原文给出的取值范围为[0, 1000000]，中文转述中写为[1, 1000000]，二者在数值上限上一致，实现时按下限 0 处理即可完全覆盖。

这三条约束意味着：值域是有限且已知的（最多 1000001 个不同取值），而操作数最多只有 10000 次。正是这一特性，让下文「布尔数组直查」的方案成为最优解。

二、解题思路分析

原文档的解题思路只有一句话：「简单题，设计一个 hashset 的数据结构，要求有add(value)、contains(value)、remove(value)，这 3 个方法。」但「简单」二字背后，是建立在对约束条件的敏锐观察之上。我们可以把候选方案逐一推演：

2.1 方案一：布尔数组直查（本题最优解）

既然元素的取值范围被死死限制在[0, 1000000]，那么最直接的思路就是：把值本身当作数组下标，用一个长度为1000001的布尔数组来记录某个值是否出现过。

• add(key)：将data[key]置为true；
• remove(key)：将data[key]置为false；
• contains(key)：返回data[key]的值。

三个操作的时间复杂度均为O(1)，空间复杂度为 O(1000001)，即常数级约 1 MB（布尔数组按字节计）。对于本题「操作总数 ≤ 10000」的量级，这一空间开销完全可以接受，而时间开销则达到理论最优。

2.2 方案二：哈希函数 + 链地址法（通用解法）

如果值域未知或极大，就需要引入哈希函数将键映射到有限个桶（bucket）中，再用链表解决哈希冲突。这正是本仓库 706. Design HashMap 一题采用的思路：定义长度为Len = 10000的桶数组，Hash(value) = value % Len作为哈希函数，每个桶用链表（HashNode）串联冲突元素，Put/Get/Remove均沿链表递归查找。该方案是通用、可扩展的，但实现复杂度更高，且平均性能依赖于哈希函数的散列质量。

2.3 为什么本题选数组直查

对比可见：链地址法解决的是「值域大、冲突多」的场景；而本题值域固定且不大，哈希函数退化为恒等映射（hash(key) = key）即可，冲突天然为零。因此从源码结构看，705. Design HashSet.go 选择了比 706 更极致的简化：连哈希函数都不需要，用数组下标直接定位。

三、仓库源码实现详解

3.1 完整代码

仓库中 705. Design HashSet.go 给出了完整实现：

package leetcode type MyHashSet struct { data []bool } /** Initialize your data structure here. */ func Constructor705() MyHashSet { return MyHashSet{ data: make([]bool, 1000001), } } func (this *MyHashSet) Add(key int) { this.data[key] = true } func (this *MyHashSet) Remove(key int) { this.data[key] = false } /** Returns true if this set contains the specified element */ func (this *MyHashSet) Contains(key int) bool { return this.data[key] } /** * Your MyHashSet object will be instantiated and called as such: * obj := Constructor(); * obj.Add(key); * obj.Remove(key); * param_3 := obj.Contains(key); */

3.2 逐方法拆解

构造方法Constructor705()

func Constructor705() MyHashSet { return MyHashSet{ data: make([]bool, 1000001), } }

一次性分配1000001个布尔元素（下标0到1000000全覆盖）。这里有两个值得注意的细节：

1. 长度为什么是 1000001：题目约束最大值为 1000000，而切片下标从 0 开始，因此需要1000000 + 1个位置，避免下标越界。
2. 布尔零值即「不存在」：Go 中bool的零值是false，恰好天然表示「集合中不存在该值」，因此无需额外初始化，构造即就绪。

Add/Remove/Contains

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] }

三个方法均为数组的直接读写：

• Add与Remove是幂等操作——重复添加、删除一个不存在的值都不会出错，这正符合题目「删除不存在的值则什么都不做」的要求；
• Contains直接返回布尔值，天然满足「存在返回 true，否则返回 false」的语义。

由于每个操作都只有一次数组寻址，时间复杂度均为 O(1)，这也是该实现能够在运行时击败 100% 提交的原因所在。

3.3 命名说明：构造函数的 705 后缀

仓库遵循「每题独立包内命名不冲突」的约定，构造函数命名为Constructor705而非题目示例中的Constructor。在 LeetCode 在线评测环境中，可直接将其替换为题目要求的Constructor名称；在本仓库的本地测试与批量测试脚本（见 gotest.sh）中，705后缀用于避免与 0706.Design-HashMap 等其他题目的构造函数重名。

四、测试用例验证

仓库在 705. Design HashSet_test.go 中提供了针对该实现的单元测试：

package leetcode import ( "fmt" "testing" ) func Test_Problem705(t *testing.T) { obj := Constructor705() obj.Add(7) fmt.Printf("Contains 7 = %v\n", obj.Contains(7)) obj.Remove(10) fmt.Printf("Contains 10 = %v\n", obj.Contains(10)) obj.Add(20) fmt.Printf("Contains 20 = %v\n", obj.Contains(20)) obj.Remove(30) fmt.Printf("Contains 30 = %v\n", obj.Contains(30)) obj.Add(8) fmt.Printf("Contains 8 = %v\n", obj.Contains(8)) obj.Remove(8) fmt.Printf("Contains 8 = %v\n", obj.Contains(8)) param1 := obj.Contains(7) fmt.Printf("param1 = %v\n", param1) }

该测试覆盖了题目的三类典型场景：

1. 添加后查询：Add(7)之后Contains(7)应为true；
2. 删除不存在的值：Remove(10)、Remove(30)对不存在的键操作不应产生任何副作用；
3. 删除后查询：Add(8)再Remove(8)之后，Contains(8)应回到false。

运行方式（在仓库根目录执行）：

go test -v -run Test_Problem705 ./leetcode/0705.Design-HashSet/ go test -cover ./leetcode/0705.Design-HashSet/

本仓库的项目描述中声明了「100% test coverage」的工程目标，即每道题均配有与 go.mod 中模块约定一致的独立测试文件，705 题也不例外。读者可以自行将测试中的断言与题目示例（add(1)→contains(1)为 true，contains(3)为 false，remove(2)后contains(2)为 false）逐一对应验证。

五、与 706. Design HashMap 的实现对比

同为「设计哈希数据结构」的姊妹题，本仓库 0706.Design-HashMap 提供了另一种解题范式，对照阅读有助于理解哈希集合与哈希映射的设计差异：

从 706 的实现可以看到，当需要存储关联值时，布尔数组方案失效，必须引入HashNode链表在冲突时挂载新节点，其Put、Get、Remove通过节点递归实现链表的插入、查找与摘除。二者对比恰好覆盖了哈希数据结构设计的两种典型思路：

• 直接寻址（本题）：适合值域有限、密集、已知的场景，实现最简单、常数因子最小；
• 散列 + 拉链（706）：适合值域广阔、稀疏、未知的场景，牺牲少量常数换取空间可扩展性。

六、延伸思考：如果题目约束变化

基于原文档约束做边界推演，可以帮助理解本题方案的适用前提：

1. 若值域扩大：比如键可达int32全范围，直接分配数组将不可行，此时应退化为 706 的「哈希函数 + 链表」方案，或用 Go 内置map[int]struct{}作参照思考其内部实现；
2. 若要求删除时回收空间：布尔数组方案无法回收已用下标，但本题操作数仅 10000 次、值域仅 1000001，空间占用恒定为常数，不存在回收压力；
3. 若元素为字符串等非整数类型：布尔数组方案彻底失效，必须借助哈希函数将任意类型映射到桶下标，链地址法（或开放寻址法）成为必然选择。

可见，本题之所以能用「一行data[key] = true」解决，正是充分吃透了「值域固定且有限」这一题眼。这也是算法题解中非常典型的思维方式：先看约束，再定方案。

七、小结

本文以 705. Design HashSet 题目文档为核心，完整梳理了题目要求、三条约束条件与解题思路，并结合仓库源码逐行解析了布尔数组实现、构造函数命名约定与单元测试用例，最后通过与 706 题链地址法实现的对比，总结了两种哈希数据结构设计思路的适用场景。

一句话概括本题解法：利用值域[0, 1000000]的已知上界，用make([]bool, 1000001)开辟直查表，让 add / remove / contains 三个操作都退化为 O(1) 的数组读写。当你在面试或竞赛中再次遇到「设计一个集合/映射」类题目时，请先问自己一个问题——键的值域是否已知且有限？如果是，布尔数组（或数组 + 哨兵值）就是最优答案。

【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go