哈希表（Hash Table）
哈希表的本质就是把“查找一个值”转换成“计算一个地址”，所以它擅长做映射、去重和计数。
核心思路
哈希表（Hash Table），也叫散列表，是根据键（Key）直接访问内存存储位置的数据结构。通过哈希函数将键映射到表中的位置来访问记录，以加快查找速度。
Key → Hash Function → Hash Value (Index) → Value
"apple" → hash() → 3 → [_, _, _, "red", _, ...]
"banana" → hash() → 7 → [_, _, _, "red", _, _, _, "yellow", ...]
核心特点
- O(1) 查找：平均情况下常数时间查找
- 键值对存储：通过key快速访问value
- 无序：元素没有固定顺序（普通哈希表）
- 唯一键：每个键只能出现一次
核心组成
1. 哈希函数（Hash Function）
将任意类型的键转换为数组索引。
好的哈希函数特性：
- 确定性：相同输入产生相同输出
- 高效性：计算快速
- 均匀性：结果均匀分布
常见哈希函数：
2. 哈希冲突（Collision）
不同的键可能产生相同的哈希值。
解决方法：
链地址法（Chaining）
索引 链表
0 → [("key1", val1)] → [("key5", val5)]
1 → [("key2", val2)]
2 → None
3 → [("key3", val3)] → [("key6", val6)] → [("key9", val9)]
4 → [("key4", val4)]
开放地址法（Open Addressing）
线性探测：
二次探测：
双重哈希：
基本操作
时间复杂度
| 操作 | 平均 | 最坏 | 说明 |
|---|---|---|---|
| 查找 | O(1) | O(n) | 最坏情况所有键冲突 |
| 插入 | O(1) | O(n) | 可能需要扩容 |
| 删除 | O(1) | O(n) | 链表需遍历 |
空间复杂度
- O(n)：n 为键值对数量
- 负载因子 = n / table_size（通常保持在 0.75 以下）
Go 代码
使用内置 map
hashMap := make(map[string]string)
hashMap["apple"] = "red"
hashMap["banana"] = "yellow"
value := hashMap["apple"]
delete(hashMap, "apple")
// 检查键是否存在
if value, ok := hashMap["banana"]; ok {
fmt.Println(value)
}高频写法
func twoSum(nums []int, target int) []int {
pos := make(map[int]int)
for i, x := range nums {
if j, ok := pos[target-x]; ok {
return []int{j, i}
}
pos[x] = i
}
return nil
}
func countFreq(nums []int) map[int]int {
cnt := make(map[int]int)
for _, x := range nums {
cnt[x]++
}
return cnt
}怎么判断该用哈希表
- 题目在问“是否存在”“是否重复”“出现次数”。
- 需要把一个值快速映射到另一个值。
- 想把原本
O(n^2)的双重枚举压成O(n)。
常用技巧
经典题目
基础应用
计数统计
查找问题
- 字符串中的第一个唯一字符 - LeetCode 387
- 最长连续序列 - LeetCode 128
- 快乐数 - LeetCode 202
设计问题
高级应用
- 四数相加 II - LeetCode 454
- 前 K 个高频元素 - LeetCode 347
- 无重复字符的最长子串 - LeetCode 3
优缺点
优点
- ✅ 平均 O(1) 的查找、插入、删除
- ✅ 适合快速查找
- ✅ 灵活的键类型
缺点
- ❌ 无序（普通哈希表）
- ❌ 空间开销大
- ❌ 最坏情况 O(n)
- ❌ 不支持范围查询
易错点
哈希表平均是
O(1)，但这不代表可以无脑用。
- 遍历
map时默认无序，不能依赖迭代顺序。 - 需要有序输出时，往往要额外排序键。
- 键类型必须可比较，否则不能作为 Go
map的 key。 - 做滑动窗口时，别忘了元素移出窗口后同步更新计数。
应用场景
- 快速查找：数据库索引、缓存
- 去重：集合（Set）
- 计数统计：词频统计
- 关联数据：配置项、映射关系
- 缓存实现：LRU、LFU