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]即最大值为 1000000操作总数[1, 10000]范围内库使用限制禁止使用内置的 HashSet 库注意题目英文原文给出的取值范围为[0, 1000000]中文转述中写为[1, 1000000]二者在数值上限上一致实现时按下限 0 处理即可完全覆盖。这三条约束意味着值域是有限且已知的最多 1000001 个不同取值而操作数最多只有 10000 次。正是这一特性让下文「布尔数组直查」的方案成为最优解。二、解题思路分析原文档的解题思路只有一句话「简单题设计一个 hashset 的数据结构要求有add(value)、contains(value)、remove(value)这 3 个方法。」但「简单」二字背后是建立在对约束条件的敏锐观察之上。我们可以把候选方案逐一推演2.1 方案一布尔数组直查本题最优解既然元素的取值范围被死死限制在[0, 1000000]那么最直接的思路就是把值本身当作数组下标用一个长度为1000001的布尔数组来记录某个值是否出现过。add(key)将data[key]置为trueremove(key)将data[key]置为falsecontains(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全覆盖。这里有两个值得注意的细节长度为什么是 1000001题目约束最大值为 1000000而切片下标从 0 开始因此需要1000000 1个位置避免下标越界。布尔零值即「不存在」Go 中bool的零值是false恰好天然表示「集合中不存在该值」因此无需额外初始化构造即就绪。Add/Remove/Containsfunc (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) }该测试覆盖了题目的三类典型场景添加后查询Add(7)之后Contains(7)应为true删除不存在的值Remove(10)、Remove(30)对不存在的键操作不应产生任何副作用删除后查询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)为 truecontains(3)为 falseremove(2)后contains(2)为 false逐一对应验证。五、与 706. Design HashMap 的实现对比同为「设计哈希数据结构」的姊妹题本仓库 0706.Design-HashMap 提供了另一种解题范式对照阅读有助于理解哈希集合与哈希映射的设计差异对比维度705. Design HashSet本题706. Design HashMap存储内容仅记录键是否存在存储键值对(key, value)底层结构布尔数组[]bool桶数组 链表*HashNode哈希函数无键直接作下标Hash(value) value % LenLen 10000冲突处理无冲突链地址法HashNode.next串联核心操作Add/Remove/ContainsPut/Get/Remove源码位置705. Design HashSet.go706. Design HashMap.go从 706 的实现可以看到当需要存储关联值时布尔数组方案失效必须引入HashNode链表在冲突时挂载新节点其Put、Get、Remove通过节点递归实现链表的插入、查找与摘除。二者对比恰好覆盖了哈希数据结构设计的两种典型思路直接寻址本题适合值域有限、密集、已知的场景实现最简单、常数因子最小散列 拉链706适合值域广阔、稀疏、未知的场景牺牲少量常数换取空间可扩展性。六、延伸思考如果题目约束变化基于原文档约束做边界推演可以帮助理解本题方案的适用前提若值域扩大比如键可达int32全范围直接分配数组将不可行此时应退化为 706 的「哈希函数 链表」方案或用 Go 内置map[int]struct{}作参照思考其内部实现若要求删除时回收空间布尔数组方案无法回收已用下标但本题操作数仅 10000 次、值域仅 1000001空间占用恒定为常数不存在回收压力若元素为字符串等非整数类型布尔数组方案彻底失效必须借助哈希函数将任意类型映射到桶下标链地址法或开放寻址法成为必然选择。可见本题之所以能用「一行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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考