LeetCode-Go 题解：706. Design HashMap 手写哈希表，用链地址法化解哈希冲突

LeetCode-Go 题解706. Design HashMap 手写哈希表用链地址法化解哈希冲突【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode-Go 仓库中 0706.Design-HashMap 一题的官方题解展开完整讲解不借助任何内建哈希表库从零手写一个 HashMap的设计思路与 Go 实现。读完本文你将掌握链地址法分离链表法解决哈希冲突的完整编码套路、定长桶数组 单链表的哈希表结构设计以及put / get / remove三个核心方法在插入、更新、删除头节点/链中节点等场景下的正确写法并能用仓库自带的测试用例验证实现正确性。一、题目原文与题意LeetCode 706 题要求设计一个 HashMap且不允许使用任何内建的哈希表库。具体来说需要实现三个方法put(key, value)向 HashMap 中插入 (key, value) 键值对如果该 key 已存在则更新对应的 value。get(key)返回指定 key 映射的 value如果映射中不存在该 key返回-1。remove(key)如果映射中存在该 key则删除这一键值对。题目给出的操作示例摘自 READMEMyHashMap hashMap new MyHashMap(); hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1 hashMap.get(3); // returns -1 (not found) hashMap.put(2, 1); // update the existing value hashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2 hashMap.get(2); // returns -1 (not found)题目的中文翻译对方法语义描述得更为直白put(key, value)向哈希映射中插入键值数值对。如果键对应的值已经存在更新这个值。get(key)返回给定的键所对应的值如果映射中不包含这个键返回-1。remove(key)如果映射中存在这个键删除这个数值对。二、约束条件与数据规模分析题目原文给出了三条关键约束它们直接决定了数据结构的设计取舍约束数值范围对设计的影响所有 key 与 value[0, 1000000]key 域有限且已知桶数组可以预先定长操作总次数[1, 10000]决定了链表的平均长度上限直接关联桶数量选取是否可用内建哈希库禁止必须手写哈希函数与冲突处理细节提醒英文原题中 key/value 的取值范围是[0, 1000000]含 0而 README 中文译文中写的是[1, 1000000]存在一处小出入。以英文原题为准实现中需要能正确处理 key 为 0 的情况。由于操作数上限只有 10000远小于 key 域的大小因此无需引入复杂的分层哈希或动态扩容机制一个定长桶数组 链表的静态哈希表就足够高效。三、解题思路冲突不可避免关键在如何解决哈希表的本质是把大范围的 key 通过哈希函数映射到小范围的桶bucket下标上。由于 key 域约 100 万个远大于桶的数量本例为 10000不同 key 映射到同一个桶是必然事件这就是哈希冲突。原 README 的解题思路明确指出设计一个 map 主要需要处理哈希冲突一般都是链表法解决冲突。业界处理冲突的主流方案有两种开放寻址法Open Addressing冲突时按探测序列线性探测、二次探测、双重哈希等在数组中继续寻找空位数据全部存在桶数组本身里。链地址法Separate Chaining每个桶不再存单个元素而是指向一条链表或红黑树的头节点所有哈希值相同的 key 都挂在这条链表上。LeetCode-Go 仓库对本题的实现选择的是链地址法content [Len]*HashNode定长桶数组 每条桶链上的HashNode单链表节点。链表法实现直观、删除操作无需像开放寻址那样处理墓碑tombstone标记非常适合本题这种操作规模有限的场景。四、数据结构设计定长桶数组 单链表节点实现位于 0706.Design-HashMap 目录下的源文件中核心数据结构如下const Len int 10000 type MyHashMap struct { content [Len]*HashNode } type HashNode struct { key int val int next *HashNode }这里有两个关键设计决策桶数量为什么取 10000因为操作总数上限是 10000而 key 域是 100 万。取桶数Len 10000后理论上每个桶平均只需承载 1 个 key即便发生碰撞单条链表的长度也被控制在可接受范围内详见下文复杂度分析。同时10000这个模数对 1000000 整除方便手算验证。为什么用*HashNode指针数组而不是存储链表头对象指针的零值是nil可以天然表达该桶为空的状态MyHashMap的零值MyHashMap{}即可直接使用构造函数无需额外初始化。这一点在下面的Constructor706中会再次体现。五、核心源码逐段精讲5.1 哈希函数取模定位桶func (this *MyHashMap) Hash(value int) int { return value % Len }哈希函数采用最简单的除留余数法key % 10000。key 与桶下标的映射关系为7→ 桶710007→ 桶7与 7 冲突20007→ 桶7与 7、10007 冲突1000000→ 桶0可见 key 与 10000 同余时必然落入同一桶这正是需要链表来承接的冲突。本题不做二次哈希、不引入随机化因子取模函数 O(1) 且无状态实现上最稳。5.2 HashNode单链表节点的递归三件套冲突的 key 在同一个桶里串成单链表链表节点自身实现了Put / Get / Remove三个递归方法func (N *HashNode) Put(key int, value int) { if N.key key { N.val value return } if N.next nil { N.next HashNode{key, value, nil} return } N.next.Put(key, value) } func (N *HashNode) Get(key int) int { if N.key key { return N.val } if N.next nil { return -1 } return N.next.Get(key) } func (N *HashNode) Remove(key int) *HashNode { if N.key key { p : N.next N.next nil return p } if N.next ! nil { N.next N.next.Remove(key) } return N }逐个方法看其逻辑分支Put若当前节点 key 相等 → 原地更新 value覆盖旧值若当前节点是链尾next nil→ 尾插新节点否则递归深入下一个节点。三种情况分别对应更新已有键追加新键沿链查找。Getkey 相等直接返回值链尾仍不匹配返回-1否则递归深入。-1作为未找到的哨兵值而由于题目保证 value 非负源码注释明确写了 value will always be non-negative-1不会与真实存储值混淆。Remove这是三个方法中最讲究的一个。它返回删除后该子链的新头节点若当前节点就是要删的节点先记下后继p断开N.next置 nil 帮助 GC把p返回给上层作为新的链头否则递归删除后继并用返回值回填N.next最后返回自身N。通过返回新头的递归约定删除链头节点时桶指针能被正确替换删除链中节点时链表也能无缝衔接。5.3 MyHashMap对外暴露的三个方法/** value will always be non-negative. */ func (this *MyHashMap) Put(key int, value int) { node : this.content[this.Hash(key)] if node nil { this.content[this.Hash(key)] HashNode{key: key, val: value, next: nil} return } node.Put(key, value) } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ func (this *MyHashMap) Get(key int) int { HashNode : this.content[this.Hash(key)] if HashNode nil { return -1 } return HashNode.Get(key) } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ func (this *MyHashMap) Remove(key int) { HashNode : this.content[this.Hash(key)] if HashNode nil { return } this.content[this.Hash(key)] HashNode.Remove(key) }对外方法统一遵循先取桶再委托给链表的模式Put先哈希定位桶桶为空则直接在此处新建头节点桶非空则委托HashNode.Put沿链更新或尾插。Get桶为空直接返回-1避免对 nil 指针调用方法否则委托链表查找。Remove桶为空直接返回删除不存在的键是幂等操作否则把HashNode.Remove返回的新链头重新写回桶数组。这一步至关重要——如果删掉的是桶链的头节点不写回就会导致桶指针仍指向一个已断链的旧节点后续Get将得到错误结果。注意Remove中两次调用this.Hash(key)虽然取模计算是廉价的但这里也可以看出实现保持了哈希函数无副作用的简洁性。5.4 构造函数零值即用/** Initialize your data structure here. */ func Constructor706() MyHashMap { return MyHashMap{} }构造函数直接返回零值结构体MyHashMap{}。因为桶数组的元素类型是指针零值下每个元素都是nil语义上恰好等于所有桶均为空。值得注意的是构造函数名为Constructor706而非Constructor——整个 LeetCode-Go 仓库把所有题目的代码收拢在各自目录下且包名统一为leetcode加题目编号后缀是为了避免不同题目的构造器在同包内重名冲突。这也是阅读仓库源码时一个值得留意的命名惯例。调用方式源码文件末尾的注释给出了使用协议obj : Constructor706() obj.Put(key, value) param_2 : obj.Get(key) obj.Remove(key)六、哈希冲突过程推演以 7、10007、20007 为例仓库测试用例精心挑选了7、10007、20007三个 key——它们对 10000 取模后全部落在桶7是验证链地址法最直观的一组数据。下面逐步推演这组 key 插入后的状态第 1 步Put(7, 1)桶7为空直接创建头节点7 → nil。第 2 步Put(10007, 2)桶7非空委托HashNode.Put头节点 key7 不匹配且next nil走尾插分支7 → 10007 → nil。第 3 步Put(20007, 3)沿链递归7不匹配 →10007不匹配且next nil尾插7 → 10007 → 20007 → nil。第 4 步Put(10007, 22)沿链递归7不匹配 →10007匹配命中更新分支value 覆盖为 22。链表结构不变7 → 10007(22) → 20007 → nil。第 5 步Get(30007)30007 % 10000 7同样进入桶7沿链遍历7、10007、20007均不匹配链尾返回-1。这验证了链上查找不存在的 key 会遍历整条链的行为。第 6 步Remove(10007)沿链递归到10007命中删除分支返回其后继20007回填给上一层节点的next链表变为7 → 20007 → nil。Get(10007)返回-1而Get(20007)仍能正常返回3证明链表衔接无误。第 7 步Remove(7)头节点命中删除分支返回新链头20007MyHashMap.Remove将其写回content[7]桶指针完成切换20007 → nil。通过这条推演可以看出链地址法下插入、查找、删除统一转化为对单链表的遍历操作而递归式Remove用返回新链头的约定优雅地处理了头节点删除这一特例。七、测试用例验证仓库为本题提供了完整的测试文件706. Design HashMap_test.go测试逻辑与上一节的推演一一对应覆盖了以下分支测试动作验证的分支Put(7, 10)→Put(7, 20)→Get(7)桶为空建头节点已存在 key 的原地更新Get(100)空桶HashNode nil返回-1Remove(100007)删除不存在的 key幂等、无副作用Put(7,1)、Put(10007,2)、Put(20007,3)构造冲突链尾插新节点、递归沿链查找Put(10007, 22)链中节点的 key 命中更新N.key key分支Get(30007)沿整条链遍历后未命中返回-1Remove(10007)递归删除链中非头节点并正确衔接链表Remove(7)删除链头节点桶指针被写回为新链头Remove(40007)/Remove(9999)删除链上不存在的 key / 删除空桶测试采用t.Fatalf对关键返回值做断言同时用fmt.Printf打印过程便于人工核对。该测试文件与源码同目录、同包package leetcode可直接运行验证go test ./leetcode/0706.Design-HashMap/ -v若想用与项目 CI 相同的覆盖率方式跑全量用例仓库根目录的 gotest.sh 提供了脚本入口go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...生成的覆盖率文件即仓库根目录的 coverage.txt。项目以100% test coverage为质量目标本题的测试对Put/Get/Remove的三态分支空桶、命中、未命中做到了逐分支覆盖。八、复杂度与边界分析时间复杂度哈希取模为 O(1)put/get/remove的核心开销在链表遍历上。设操作数 n桶数 Len则单次操作平均复杂度 O(n / Len)。本题 n ≤ 10000、Len 10000均匀分布下单桶期望链长 ≤ 1可视为平均 O(1)。最坏情况由于哈希函数是朴素取模且 key 域为[0, 1000000]与 10000 同余的 key 会全部挤进同一桶。以桶0为例0, 10000, 20000, …, 1000000共 101 个 key 会全部落入该桶最坏单条链长可达 101此时单次操作为 O(101)。但因为操作总数被限制在 10000这一最坏开销在本题约束下依然可接受这也是定长桶 链表方案能通过本题的原因。空间复杂度O(Len n)即定长桶数组加上所有链表节点占用的空间。边界情况盘点key 为 00 % 10000 0正常落入桶0value 为 0 时Get返回 0 而非-1因为未找到的判断依据是链尾哨兵nil而非值本身。value 非负源码注释明确value will always be non-negative因此-1作为未找到哨兵不会与真实值冲突若题目允许负值则需要改用是否存在标志位。重复 put 同一 key命中更新分支不会产生重复节点。删除不存在或已删除的 keyRemove在空桶上直接返回删除链上不存在的 key 时递归会原样回传整条链结构保持不变幂等安全。递归深度最坏链长 101递归深度远低于 Go 默认栈限制无栈溢出风险。九、同类题目对比705. Design HashSet 的直接定址方案同样是手写哈希结构系列仓库中 0705.Design-HashSet 一题的实现则走了完全不同的路线type MyHashSet struct { data []bool } 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 } func (this *MyHashSet) Contains(key int) bool { return this.data[key] }两个题目共享相同的 key 域约束[0, 1000000]但 705 选择了直接定址boolean 数组按下标映射而 706 选择了链地址法。两者对比如下维度705 Design HashSet706 Design HashMap底层结构[1000001]bool布尔数组[10000]*HashNode桶数组 链表冲突处理无冲突key 直接当数组下标链地址法取模 链表空间开销固定约 1MB1000001 个 bool10000 个桶指针 实际节点值语义只有存在/不存在每个 key 可携带任意非负 value适用前提key 域小且可枚举key 域大需要压缩映射对照阅读这两题可以直观体会到当 key 域小且密集时直接定址最简单当 key 域大或稀疏时哈希 冲突处理是空间与时间的最佳折中。这也是哈希表这一数据结构在工程中广泛应用的根本原因。十、总结LeetCode-Go 仓库对 706 题的实现是一个教科书级别的链地址法哈希表[10000]*HashNode定长桶数组负责 O(1) 定位HashNode单链表以三个递归方法承接插入、查找、删除用返回新链头的约定解决了头节点删除的指针更新问题。从 README 的题目解析到源码与测试的闭环读者可以完整学习到哈希冲突的两大解法开放寻址 vs 链地址法及本题的选型理由取模哈希函数、定长桶数组、单链表节点的组合设计put的空桶建头 / 更新 / 尾插三分支get的哨兵返回remove的链头回写用同余 key 组7、10007、20007构造冲突链的测试技巧与逐分支验证方法平均 O(1)、最坏 O(链长) 的复杂度边界以及操作数上限决定桶数的工程权衡。掌握这道题再配合 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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考