哈希表¶

哈希表（Hash Table）是一种基于 哈希函数 实现的数据结构，通过键（Key）直接访问值（Value），实现 \(O(1)\) 时间复杂度的查找、插入和删除操作。它是"空间换时间"思想的经典体现，常用于解决查找、计数、去重、分组、记忆优化、数组索引映射等问题。

空间换时间的智慧

"空间换时间"是计算机科学中的核心权衡思想，在软件和硬件设计中无处不在：

CPU 缓存：用 L1/L2/L3 缓存换取更快的数据访问
数据库索引：用额外的索引空间换取查询速度
CDN：在全球部署服务器换取更快的内容分发
Redis/Memcached：用内存存储换取毫秒级响应
预计算：提前计算结果（如前缀和）换取查询效率

核心概念¶

哈希函数¶

哈希函数将键映射到数组索引：

1	`index = hash(key) % capacity`

理想哈希函数的特性：

确定性：相同的键总是产生相同的哈希值
均匀分布：键均匀分布在哈希表中，减少冲突
高效计算：哈希函数本身的计算速度要快

哈希冲突¶

当两个不同的键映射到同一个索引时，就发生了 哈希冲突。

解决方法：

方法	原理	优点	缺点
链地址法（Separate Chaining）	每个索引位置存储一个链表，冲突的键值对追加到链表中	实现简单不限容量	链表过长时性能退化需要额外指针空间
开放寻址法（Open Addressing）	冲突时按某种规则寻找下一个空位	内存利用率高缓存友好	删除操作复杂负载因子高时性能下降

开放寻址法的探测方式：

线性探测：index = (hash + i) % capacity
二次探测：index = (hash + i²) % capacity
双重哈希：index = (hash1 + i × hash2) % capacity

负载因子¶

1	`负载因子 = 元素数量 / 哈希表容量`

链地址法：通常在负载因子 > 0.75 时扩容
开放寻址法：通常在负载因子 > 0.5 时扩容

常见实现¶

不同语言的哈希表¶

语言	数据结构	底层实现	特点
Go	`map[K]V`	开放寻址 + 链表	无序，并发不安全
Python	`dict`	开放寻址（二次探测）	3.7+ 保持插入顺序
Java	`HashMap`	链地址法（红黑树优化）	链表长度 > 8 转红黑树
C++	`unordered_map`	链地址法	基于桶的实现
JavaScript	`Map` / `Object`	引擎优化	`Map` 保持插入顺序

Go 语言示例¶

// 创建哈希表
m := make(map[string]int)

// 插入/更新
m["apple"] = 5
m["banana"] = 3

// 查找
value, exists := m["apple"]
if exists {
    fmt.Println(value) // 5
}

// 删除
delete(m, "banana")

// 遍历（无序）
for key, value := range m {
    fmt.Printf("%s: %d\n", key, value)
}

// 长度
fmt.Println(len(m))

时间复杂度¶

操作	平均时间复杂度	最坏时间复杂度
查找	\(O(1)\)	\(O(n)\)
插入	\(O(1)\)	\(O(n)\)
删除	\(O(1)\)	\(O(n)\)

最坏情况

当所有键都发生哈希冲突时，退化为链表，时间复杂度为 \(O(n)\)。

经典应用场景¶

快速查找计数统计去重分组映射缓存/记忆化索引映射

问题：判断元素是否存在

// 判断数组中是否存在重复元素
func containsDuplicate(nums []int) bool {
    seen := make(map[int]bool)
    for _, num := range nums {
        if seen[num] {
            return true
        }
        seen[num] = true
    }
    return false
}

经典题目：

问题：统计元素出现次数

// 统计字符串中每个字符的出现次数
func countChars(s string) map[rune]int {
    count := make(map[rune]int)
    for _, ch := range s {
        count[ch]++
    }
    return count
}

经典题目：

问题：移除重复元素

// 数组去重
func removeDuplicates(nums []int) []int {
    seen := make(map[int]bool)
    result := []int{}
    for _, num := range nums {
        if !seen[num] {
            seen[num] = true
            result = append(result, num)
        }
    }
    return result
}

问题：将元素按某种规则分组

// 字母异位词分组
func groupAnagrams(strs []string) [][]string {
    groups := make(map[string][]string)
    for _, str := range strs {
        // 排序后的字符串作为键
        key := sortString(str)
        groups[key] = append(groups[key], str)
    }

    result := [][]string{}
    for _, group := range groups {
        result = append(result, group)
    }
    return result
}

经典题目：

49. Group Anagrams

问题：存储计算结果避免重复计算

// 斐波那契数列（记忆化递归）
func fib(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if val, exists := memo[n]; exists {
        return val
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

问题：建立值到索引的映射

// 两数之和
func twoSum(nums []int, target int) []int {
    indexMap := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if j, exists := indexMap[complement]; exists {
            return []int{j, i}
        }
        indexMap[num] = i
    }
    return nil
}

经典题目：

哈希表 vs 其他数据结构¶

特性	哈希表	数组	链表	二叉搜索树
查找	\(O(1)\)	\(O(n)\)	\(O(n)\)	\(O(\log n)\)
插入	\(O(1)\)	\(O(n)\)	\(O(1)\)	\(O(\log n)\)
删除	\(O(1)\)	\(O(n)\)	\(O(1)\)	\(O(\log n)\)
有序性	✕	✓	✕	✓
空间效率	低	高	低	中

使用技巧¶

1. 选择合适的键类型¶

可哈希的类型：

✅ 整数、浮点数、字符串
✅ 元组（不可变）
❌ 列表、字典（可变类型）

2. 自定义哈希键¶

当需要复杂的键时，可以将多个值组合成字符串或元组：

// 使用字符串作为复合键
key := fmt.Sprintf("%d,%d", x, y)

// 或使用结构体（需实现 comparable）
type Point struct {
    X, Y int
}
m := make(map[Point]int)

3. 默认值处理¶

// 方法 1：检查键是否存在
if val, exists := m[key]; exists {
    // 键存在
} else {
    // 键不存在，使用默认值
}

// 方法 2：直接使用零值
count := m[key] // 如果不存在，返回 0
m[key] = count + 1

4. 避免并发问题¶

Go 的 map 不是并发安全的，需要使用 sync.Map 或加锁：

import "sync"

var (
    m  = make(map[string]int)
    mu sync.RWMutex
)

// 读操作
mu.RLock()
value := m[key]
mu.RUnlock()

// 写操作
mu.Lock()
m[key] = value
mu.Unlock()

常见陷阱¶

1. 遍历顺序不确定¶

m := map[string]int{"a": 1, "b": 2, "c": 3}
for k, v := range m {
    // 每次遍历顺序可能不同！
    fmt.Println(k, v)
}

解决方案

如果需要有序遍历，先将键排序：

keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
    fmt.Println(k, m[k])
}

2. 遍历时修改¶

// ❌ 错误：遍历时删除可能导致未定义行为
for k := range m {
    if someCondition(k) {
        delete(m, k) // 危险！
    }
}

// ✅ 正确：先收集要删除的键
toDelete := []string{}
for k := range m {
    if someCondition(k) {
        toDelete = append(toDelete, k)
    }
}
for _, k := range toDelete {
    delete(m, k)
}

3. 值是指针 vs 值类型¶

// 值类型：无法直接修改
type Person struct {
    Name string
    Age  int
}
m := make(map[string]Person)
m["alice"] = Person{"Alice", 30}
m["alice"].Age = 31 // ❌ 编译错误！

// 解决方案 1：使用指针
m2 := make(map[string]*Person)
m2["alice"] = &Person{"Alice", 30}
m2["alice"].Age = 31 // ✅

// 解决方案 2：重新赋值
p := m["alice"]
p.Age = 31
m["alice"] = p // ✅

经典题目¶

基础题进阶题高级题

1. Two Sum — 两数之和（入门必做）
217. Contains Duplicate — 存在重复元素
242. Valid Anagram — 有效的字母异位词
383. Ransom Note — 赎金信

49. Group Anagrams — 字母异位词分组
128. Longest Consecutive Sequence — 最长连续序列
146. LRU Cache — LRU 缓存（哈希表 + 双向链表）
387. First Unique Character in a String — 字符串中的第一个唯一字符

149. Max Points on a Line — 直线上最多的点数
380. Insert Delete GetRandom O(1) — 常数时间插入、删除和获取随机元素
460. LFU Cache — LFU 缓存

总结¶

哈希表是算法面试中最常用的数据结构之一，掌握以下要点：

✅ 理解原理：哈希函数、冲突解决、负载因子
✅ 熟练应用：查找、计数、去重、分组、缓存
✅ 注意陷阱：遍历顺序、并发安全、值类型修改
✅ 时间复杂度：平均 \(O(1)\)，最坏 \(O(n)\)
✅ 空间换时间：用额外空间换取查找效率

哈希表¶

核心概念¶

哈希函数¶

哈希冲突¶

负载因子¶

常见实现¶

不同语言的哈希表¶

Go 语言示例¶

时间复杂度¶

经典应用场景¶

哈希表 vs 其他数据结构¶

使用技巧¶

1. 选择合适的键类型¶

2. 自定义哈希键¶

3. 默认值处理¶

4. 避免并发问题¶

常见陷阱¶

1. 遍历顺序不确定¶

2. 遍历时修改¶

3. 值是指针 vs 值类型¶

经典题目¶

总结¶

评论