LeetCode 706. 设计哈希映射
目录
题目描述
题意分析
要求不借助现成的映射容器，自己实现一个键值都是非负整数的映射，支持三个操作：
put(key, value)插入或覆盖、get(key)查询（不存在返回 -1）、remove(key)删除。约束里有两个信号值得注意。第一，键的取值范围是 $[0, 10^6]$，是有限且非负的，这意味着「开一个长度 $10^6 + 1$ 的数组直接下标寻址」在内存上勉强可行，但那是用空间换掉了题目真正想考的东西；题目名字里的「设计哈希映射」摆明了要看的是把大值域压缩到小数组之后如何处理冲突。第二，调用次数最多 $10^4$，实际存活的键远少于值域大小，说明桶数组只需要开到几百上千的量级就足够摊薄冲突。
边界要点集中在三处：
put一个已经存在的键必须覆盖旧值而不是再插一份，否则get会读到过期数据；get不存在的键要返回 -1，而不能返回 0 或抛异常；remove一个不存在的键必须安静返回，删除的又恰好是链表头节点时，还要记得把桶数组里的指针一起改掉。
解法：数组桶 + 链地址法
核心思路
直接用
key作为数组下标虽然能做到常数时间，但空间取决于整个键值域。更通用的做法是用key % BASE把键映射到较小的桶数组。映射会发生冲突，例如 1 和 770 在BASE = 769时都落入 1 号桶，因此桶内还必须保留原始键。这里用链地址法处理冲突：每个桶是一条单链表，节点保存
key、value和next。put、get、remove都先定位桶，再沿链比较原始键。新键头插即可；已有键必须更新原节点，不能再插入一个副本。数据结构的不变量是：每个已存键只出现一次，并且只位于
buckets[key % BASE]对应的链中。put的「先查重、后头插」维持唯一性；get扫完整条链仍未命中即可判定不存在；remove摘掉匹配节点后即可结束。固定取素数 769 是基于本题最多约一万次操作的简单折中，能减少常见周期数据带来的聚集。生产级哈希表还会根据装载因子扩容和重新散列，但本题不需要额外实现。
解题步骤
- 构造长度为
BASE的桶数组，每个桶初始为空；题目保证键非负，所以key % BASE可直接作为下标。put：遍历目标链，命中键就更新值并返回；未命中则把新节点插到链头。get：遍历目标链，命中返回值；走到链尾仍未命中则返回 -1。remove：在链头前接一个虚拟节点，用前驱指针摘掉目标节点，再把真实桶头更新为dummy.next。冲突用例最能验证实现：先执行
put(1, 10)、put(770, 20)，两个键同在 1 号桶但仍能分别取到 10 和 20；删除 770 后，键 1 仍必须保留。
代码实现
class MyHashMap {
private static final int BASE = 769;
private Node[] buckets;
public MyHashMap() {
buckets = new Node[BASE];
}
public void put(int key, int value) {
int index = hash(key);
Node cur = buckets[index];
while (cur != null) {
if (cur.key == key) {
cur.value = value;
return;
}
cur = cur.next;
}
buckets[index] = new Node(key, value, buckets[index]);
}
public int get(int key) {
Node cur = buckets[hash(key)];
while (cur != null) {
if (cur.key == key) {
return cur.value;
}
cur = cur.next;
}
return -1;
}
public void remove(int key) {
int index = hash(key);
Node dummy = new Node(-1, -1, buckets[index]);
Node pre = dummy;
Node cur = buckets[index];
while (cur != null) {
if (cur.key == key) {
pre.next = cur.next;
buckets[index] = dummy.next;
return;
}
pre = cur;
cur = cur.next;
}
}
private int hash(int key) {
return key % BASE;
}
private static class Node {
int key;
int value;
Node next;
Node(int key, int value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
}
type MyHashMap struct {
buckets []*HashNode
}
type HashNode struct {
key int
value int
next *HashNode
}
func Constructor() MyHashMap {
return MyHashMap{buckets: make([]*HashNode, 769)}
}
func (this *MyHashMap) Put(key int, value int) {
index := key % len(this.buckets)
for cur := this.buckets[index]; cur != nil; cur = cur.next {
if cur.key == key {
cur.value = value
return
}
}
this.buckets[index] = &HashNode{key: key, value: value, next: this.buckets[index]}
}
func (this *MyHashMap) Get(key int) int {
index := key % len(this.buckets)
for cur := this.buckets[index]; cur != nil; cur = cur.next {
if cur.key == key {
return cur.value
}
}
return -1
}
func (this *MyHashMap) Remove(key int) {
index := key % len(this.buckets)
dummy := &HashNode{next: this.buckets[index]}
pre := dummy
for cur := this.buckets[index]; cur != nil; cur = cur.next {
if cur.key == key {
pre.next = cur.next
this.buckets[index] = dummy.next
return
}
pre = cur
}
}
复杂度分析
- 时间复杂度：设当前键数为
n、桶数为b。分布均匀时每次操作期望为 $O(1 + n / b)$；所有键冲突时最坏为 $O(n)$。- 空间复杂度：$O(n + b)$，分别用于链表节点和桶数组。
关键点总结
- 哈希函数只负责定位桶；节点中的原始
key才能在发生冲突后确认身份。put必须先查重再插入，维持「一个键只对应一个节点」的不变量。- 头插让新键插入为 $O(1)$；虚拟头节点让删除链首与链中节点共用一套逻辑。
- 固定桶数足以满足题目约束，但复杂度不是无条件 $O(1)$；极端冲突时仍会退化为链表。
- 面试追问扩容时，应说明：装载因子过高后创建更大的桶数组，并按新桶数重新计算每个键的位置。
易错点总结
put不查重会产生重复节点：更新后再删除一次，旧值可能重新暴露。- 节点只存值、不存键时，同一桶中的冲突键无法区分。
- 删除链首后若没有同步
buckets[index]，桶仍指向已删除节点；虚拟头节点能统一处理。get未命中必须返回题目规定的 -1，不能用 0，因为 0 本身是合法值。- 当前哈希函数依赖「键非负」约束；若键域允许负数，Java 应使用
Math.floorMod(key, BASE)，避免负下标。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 705. 设计哈希集合 | 简单 | 只存键的链地址法 |
| 146. LRU 缓存 | 中等 | 哈希表配双向链表 |
| 208. 实现 Trie (前缀树) | 中等 | 多叉树按字符寻址 |
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 哈希表配变长数组 |
| 622. 设计循环队列 | 中等 | 定长数组的环形下标 |
| 432. 全 O(1) 的数据结构 | 困难 | 哈希表配按计数分桶的链表 |