从零实现哈希表基于 LeetCode 706 的 MyHashMap 两种经典方案直接定址与拉链法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇指南基于仓库中的 articles/design-hashmap.md 展开完整讲解 LeetCode 706「设计哈希映射」题目的两条实现路线利用 key 值域做直接定址数组以及用 1000 个桶加单链表拉链法处理哈希冲突。读完后你将掌握两种方案的算法步骤、十种语言的完整实现、时间与空间复杂度推导、常见错误陷阱并能对照仓库中其他语言的实现变体理解桶数量、哈希函数这两个关键参数的实际影响。问题背景与前置知识题目要求在不使用任何内置哈希库的前提下设计一个哈希表支持三个操作put(key, value)插入或更新键值对value恒为非负数get(key)返回 key 对应的 value若 key 不存在则返回-1remove(key)若映射存在则删除。关键约束是 key 的取值范围为[0, 1000000]这一上限正是两种方案取舍的核心依据。按照原文档的说明动手前建议先熟悉三个前置概念哈希函数——理解 key 如何通过取模运算映射到下标链表——实现基于节点的冲突处理结构拉链法数组——固定大小数组的直接定址访问。方案一直接定址数组核心思想由于 key 被约束在[0, 1000000]区间内可以直接用数组做“直接定址表”数组下标就是 key该位置存的就是 value用-1表示该 key 不存在。这样所有操作都是 O(1) 时间代价是无论实际存了多少个 key都要付出固定的内存开销。算法步骤初始化一个大小为1000001的数组全部元素置为-1put(key, value)执行map[key] valueget(key)返回map[key]从未写入或已被删除时返回-1remove(key)执行map[key] -1。各语言实现Pythonclass MyHashMap: def __init__(self): self.map [-1] * 1000001 def put(self, key: int, value: int) - None: self.map[key] value def get(self, key: int) - int: return self.map[key] def remove(self, key: int) - None: self.map[key] -1Javapublic class MyHashMap { private int[] map; public MyHashMap() { map new int[1000001]; Arrays.fill(map, -1); } public void put(int key, int value) { map[key] value; } public int get(int key) { return map[key]; } public void remove(int key) { map[key] -1; } }Cclass MyHashMap { private: vectorint map; public: MyHashMap() : map(1000001, -1) {} void put(int key, int value) { map[key] value; } int get(int key) { return map[key]; } void remove(int key) { map[key] -1; } };JavaScriptclass MyHashMap { constructor() { this.map new Array(1000001).fill(-1); } /** * param {number} key * param {number} value * return {void} */ put(key, value) { this.map[key] value; } /** * param {number} key * return {number} */ get(key) { return this.map[key]; } /** * param {number} key * return {void} */ remove(key) { this.map[key] -1; } }C#public class MyHashMap { private int[] map; public MyHashMap() { map new int[1000001]; for (int i 0; i map.Length; i) { map[i] -1; } } public void Put(int key, int value) { map[key] value; } public int Get(int key) { return map[key]; } public void Remove(int key) { map[key] -1; } }Gotype MyHashMap struct { data []int } func Constructor() MyHashMap { data : make([]int, 1000001) for i : range data { data[i] -1 } return MyHashMap{data: data} } func (this *MyHashMap) Put(key int, value int) { this.data[key] value } func (this *MyHashMap) Get(key int) int { return this.data[key] } func (this *MyHashMap) Remove(key int) { this.data[key] -1 }Kotlinclass MyHashMap() { private val map IntArray(1000001) { -1 } fun put(key: Int, value: Int) { map[key] value } fun get(key: Int): Int { return map[key] } fun remove(key: Int) { map[key] -1 } }Swiftclass MyHashMap { private var map: [Int] init() { map Int } func put(_ key: Int, _ value: Int) { map[key] value } func get(_ key: Int) - Int { return map[key] } func remove(_ key: Int) { map[key] -1 } }Ruststruct MyHashMap { map: Veci32, } impl MyHashMap { fn new() - Self { Self { map: vec![-1; 1_000_001] } } fn put(mut self, key: i32, value: i32) { self.map[key as usize] value; } fn get(self, key: i32) - i32 { self.map[key as usize] } fn remove(mut self, key: i32) { self.map[key as usize] -1; } }时间与空间复杂度时间复杂度每个函数调用均为 $O(1)$空间复杂度$O(1000000)$因为 key 的范围是 $[0, 1000000]$。适用性讨论从源码结构看这一方案的所有语言版本都依赖同一个前提——0 key 1000000是题目给定的硬性约束。如果 key 范围扩大比如 32 位整数直接定址表将不可行而即便在此约束下1000001 个 int 的固定开销约 4MB 量级也是必须付出的代价。因此该方案本质上是“以固定内存换绝对常数时间”的极端做法适合 key 密集且值域可控的场景。方案二哈希表 拉链法链表处理冲突核心思想为了降低内存占用采用拉链法separate chaining创建一个桶数量远小于 key 范围的数组用哈希函数key % 桶数决定 key 落在哪个桶每个桶是一条链表存放完整的键值对。冲突的键就串联在同一个桶的链表里。算法步骤初始化一个1000个桶的数组每个桶包含一个哑头节点dummy head定义hash(key) key % 1000put(key, value)遍历hash(key)处的链表。若存在 key 相同的节点则更新其 value否则在链表尾部追加一个新节点get(key)遍历hash(key)处的链表。找到 key 则返回其 value否则返回-1remove(key)遍历hash(key)处的链表。找到 key 则通过修改前驱节点的next指针将其摘除。各语言实现Pythonclass ListNode: def __init__(self, key -1, val -1, next None): self.key key self.val val self.next next class MyHashMap: def __init__(self): self.map [ListNode() for _ in range(1000)] def hash(self, key: int) - int: return key % len(self.map) def put(self, key: int, value: int) - None: cur self.map[self.hash(key)] while cur.next: if cur.next.key key: cur.next.val value return cur cur.next cur.next ListNode(key, value) def get(self, key: int) - int: cur self.map[self.hash(key)].next while cur: if cur.key key: return cur.val cur cur.next return -1 def remove(self, key: int) - None: cur self.map[self.hash(key)] while cur.next: if cur.next.key key: cur.next cur.next.next return cur cur.nextJavaclass ListNode { int key, val; ListNode next; public ListNode(int key, int val, ListNode next) { this.key key; this.val val; this.next next; } public ListNode() { this(-1, -1, null); } } public class MyHashMap { private ListNode[] map; public MyHashMap() { map new ListNode[1000]; for (int i 0; i 1000; i) { map[i] new ListNode(); } } private int hash(int key) { return key % map.length; } public void put(int key, int value) { ListNode cur map[hash(key)]; while (cur.next ! null) { if (cur.next.key key) { cur.next.val value; return; } cur cur.next; } cur.next new ListNode(key, value, null); } public int get(int key) { ListNode cur map[hash(key)].next; while (cur ! null) { if (cur.key key) { return cur.val; } cur cur.next; } return -1; } public void remove(int key) { ListNode cur map[hash(key)]; while (cur.next ! null) { if (cur.next.key key) { cur.next cur.next.next; return; } cur cur.next; } } }Cclass MyHashMap { private: struct ListNode { int key, val; ListNode* next; ListNode(int key -1, int val -1, ListNode* next nullptr) : key(key), val(val), next(next) {} }; vectorListNode* map; int hash(int key) { return key % map.size(); } public: MyHashMap() { map.resize(1000); for (auto bucket : map) { bucket new ListNode(0); } } void put(int key, int value) { ListNode* cur map[hash(key)]; while (cur-next) { if (cur-next-key key) { cur-next-val value; return; } cur cur-next; } cur-next new ListNode(key, value); } int get(int key) { ListNode* cur map[hash(key)]-next; while (cur) { if (cur-key key) { return cur-val; } cur cur-next; } return -1; } void remove(int key) { ListNode* cur map[hash(key)]; while (cur-next) { if (cur-next-key key) { ListNode* tmp cur-next; cur-next cur-next-next; delete tmp; return; } cur cur-next; } } };JavaScriptclass ListNode { /** * param {number} key * param {number} val * param {ListNode} next */ constructor(key -1, val -1, next null) { this.key key; this.val val; this.next next; } } class MyHashMap { constructor() { this.map Array.from({ length: 1000 }, () new ListNode()); } /** * param {number} key * return {number} */ hash(key) { return key % this.map.length; } /** * param {number} key * param {number} value * return {void} */ put(key, value) { let cur this.map[this.hash(key)]; while (cur.next) { if (cur.next.key key) { cur.next.val value; return; } cur cur.next; } cur.next new ListNode(key, value); } /** * param {number} key * return {number} */ get(key) { let cur this.map[this.hash(key)].next; while (cur) { if (cur.key key) { return cur.val; } cur cur.next; } return -1; } /** * param {number} key * return {void} */ remove(key) { let cur this.map[this.hash(key)]; while (cur.next) { if (cur.next.key key) { cur.next cur.next.next; return; } cur cur.next; } } }C#public class ListNode { public int key; public int val; public ListNode next; public ListNode(int key -1, int val -1, ListNode next null) { this.key key; this.val val; this.next next; } } public class MyHashMap { private ListNode[] map; public MyHashMap() { map new ListNode[1000]; for (int i 0; i map.Length; i) { map[i] new ListNode(); } } private int Hash(int key) { return key % map.Length; } public void Put(int key, int value) { ListNode cur map[Hash(key)]; while (cur.next ! null) { if (cur.next.key key) { cur.next.val value; return; } cur cur.next; } cur.next new ListNode(key, value); } public int Get(int key) { ListNode cur map[Hash(key)].next; while (cur ! null) { if (cur.key key) { return cur.val; } cur cur.next; } return -1; } public void Remove(int key) { ListNode cur map[Hash(key)]; while (cur.next ! null) { if (cur.next.key key) { cur.next cur.next.next; return; } cur cur.next; } } }Gotype ListNode struct { key, val int next *ListNode } type MyHashMap struct { data []*ListNode } func Constructor() MyHashMap { data : make([]*ListNode, 1000) for i : range data { data[i] ListNode{key: -1, val: -1} } return MyHashMap{data: data} } func (this *MyHashMap) hash(key int) int { return key % len(this.data) } func (this *MyHashMap) Put(key int, value int) { cur : this.data[this.hash(key)] for cur.next ! nil { if cur.next.key key { cur.next.val value return } cur cur.next } cur.next ListNode{key: key, val: value} } func (this *MyHashMap) Get(key int) int { cur : this.data[this.hash(key)].next for cur ! nil { if cur.key key { return cur.val } cur cur.next } return -1 } func (this *MyHashMap) Remove(key int) { cur : this.data[this.hash(key)] for cur.next ! nil { if cur.next.key key { cur.next cur.next.next return } cur cur.next } }Kotlinclass ListNode(var key: Int -1, var val: Int -1, var next: ListNode? null) class MyHashMap() { private val map Array(1000) { ListNode() } private fun hash(key: Int): Int key % map.size fun put(key: Int, value: Int) { var cur map[hash(key)] while (cur.next ! null) { if (cur.next!!.key key) { cur.next!!.val value return } cur cur.next!! } cur.next ListNode(key, value) } fun get(key: Int): Int { var cur map[hash(key)].next while (cur ! null) { if (cur.key key) { return cur.val } cur cur.next } return -1 } fun remove(key: Int) { var cur map[hash(key)] while (cur.next ! null) { if (cur.next!!.key key) { cur.next cur.next!!.next return } cur cur.next!! } } }Swiftclass ListNode { var key: Int var val: Int var next: ListNode? init(_ key: Int -1, _ val: Int -1, _ next: ListNode? nil) { self.key key self.val val self.next next } } class MyHashMap { private var map: [ListNode] init() { map (0..1000).map { _ in ListNode() } } private func hash(_ key: Int) - Int { return key % map.count } func put(_ key: Int, _ value: Int) { var cur map[hash(key)] while cur.next ! nil { if cur.next!.key key { cur.next!.val value return } cur cur.next! } cur.next ListNode(key, value) } func get(_ key: Int) - Int { var cur map[hash(key)].next while cur ! nil { if cur!.key key { return cur!.val } cur cur!.next } return -1 } func remove(_ key: Int) { var cur map[hash(key)] while cur.next ! nil { if cur.next!.key key { cur.next cur.next!.next return } cur cur.next! } } }Rust用Vec(i32, i32)模拟桶内链表省去手写节点struct MyHashMap { buckets: VecVec(i32, i32), } impl MyHashMap { fn new() - Self { Self { buckets: vec![Vec::new(); 1000], } } fn hash(key: i32) - usize { key as usize % 1000 } fn put(mut self, key: i32, value: i32) { let idx Self::hash(key); for pair in self.buckets[idx].iter_mut() { if pair.0 key { pair.1 value; return; } } self.buckets[idx].push((key, value)); } fn get(self, key: i32) - i32 { let idx Self::hash(key); for pair in self.buckets[idx] { if pair.0 key { return pair.1; } } -1 } fn remove(mut self, key: i32) { let idx Self::hash(key); if let Some(pos) self.buckets[idx].iter().position(|p| p.0 key) { self.buckets[idx].remove(pos); } } }时间与空间复杂度时间复杂度每个函数调用 $O(\frac{n}{k})$空间复杂度$O(k m)$。其中 $n$ 为 key 总数$k$ 为 map 的大小此处 $1000$$m$ 为去重后的 key 数量。桶越多单桶内链表越短常数时间越接近 $O(1)$桶越少内存越省但冲突链越长——这正是桶数量作为核心调参的含义。仓库中的其他实现变体对照仓库中同一题目的不同语言解法可以看到拉链法的两个自由度桶数量、哈希函数在不同实现中取值各异java/0706-design-hashmap.java桶数取19997素数哈希函数采用 Knuth 乘法散列(long)key * 12582917 % 19997而非简单取模使 key 分布更均匀put被实现为“先remove(key)再头插新节点”逻辑上等价于“更新或插入”cpp/0706-design-hashmap.cpp桶数取10010每个桶用std::listpairint,int代替手写单链表find返回迭代器后统一处理增删改代码更简洁且文件头注释明确给出时间 $O(n)$、空间 $O(n)$ 的复杂度结论go/0706-design-hashmap.go桶数仅512仍用哑头节点 尾插的标准拉链结构展示了桶数偏小时冲突链可能更长的取舍。从源码结构看这些变体说明“1000 个桶 key % 1000”只是拉链法的一个典型配置实际工程中桶数量与哈希函数质量共同决定了冲突概率而算法骨架定位桶 - 遍历链 - 命中更新 / 未命插入 / 摘除节点在所有实现中是一致的。常见陷阱陷阱一put 时不更新已存在的 key当 key 已存在时put()应当更新其 value而不是追加一个重复节点。# 错误 - 会产生重复条目 def put(self, key: int, value: int) - None: cur self.map[self.hash(key)] while cur.next: cur cur.next cur.next ListNode(key, value) # 总是新增节点 # 正确 - 存在则更新否则插入 def put(self, key: int, value: int) - None: cur self.map[self.hash(key)] while cur.next: if cur.next.key key: cur.next.val value # 更新已有节点 return cur cur.next cur.next ListNode(key, value) # 新增重复节点不仅浪费空间还会让get返回旧值、remove只删除其中一个。陷阱二get 时从哑头节点开始遍历get应当从dummy.next第一个真实节点开始而不是从哑头节点本身开始。# 错误 - 会检查哑头节点的 key def get(self, key: int) - int: cur self.map[self.hash(key)] # 从哑头开始 while cur: if cur.key key: # 哑头 key-1理论上可能误匹配 return cur.val cur cur.next return -1 # 正确 - 跳过哑头节点 def get(self, key: int) - int: cur self.map[self.hash(key)].next # 从哑头之后开始 while cur: if cur.key key: return cur.val cur cur.next return -1哑头节点存在的意义是统一remove/put的指针操作始终操作cur.next免去对“删除的是桶首节点”的特判但它的key -1语义是占位而非数据遍历时必须跳过。两种方案的取舍维度方案一直接定址数组方案二1000 桶拉链法时间复杂度每次操作 $O(1)$每次操作 $O(n/k)$平均近似 $O(1)$空间复杂度$O(1000000)$ 固定$O(k m)$随实际 key 数增长前提条件key 值域有界且可承受任意整数 key冲突处理无需下标即 key链表串联典型适用key 密集、值域小、追求极致常数时间通用场景、key 稀疏或值域大选择上的直觉是key 上限只有 $10^6$ 时两种方案都能通过但直接定址表用 $O(10^6)$ 固定空间换取绝对 $O(1)$拉链法用平均 $O(1)$ 换取 $O(m)$ 的动态空间且天然支持任意整数 key。面试与工程实现中拉链法及其工程优化素数桶数、乘法散列、桶内结构换用标准容器是更通用、更值得深入掌握的路线。延伸阅读原始讲解文档articles/design-hashmap.md题目实现参考python/0706-design-hashmap.py、javascript/0706-design-hashmap.js、kotlin/0706-design-hashmap.kt姊妹题设计哈希集合拉链法同样适用python/0705-design-hashset.py【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考