哈希表

本章目标：理解哈希表原理，掌握用哈希表将 O(n²) 优化到 O(n) 的思维转换。

你将学到

• 哈希函数的设计原则
• 冲突解决策略（拉链法、开放地址法）
• 负载因子与扩容
• Swift 中 Dictionary 和 Set 的底层实现
• 用哈希表做计数与映射
• 哈希表配合双向链表实现 LRU

1. 概念

哈希表通过哈希函数将 key 映射到数组下标，实现 O(1) 平均时间的查找、插入和删除。它是算法题中最常用的"空间换时间"手段——当发现需要频繁查找时，第一反应应该是"能不能用哈希"。

冲突不可避免（鸽笼原理），两种主流解决方案：

• 拉链法：每个桶存一个链表，冲突元素追加到链表
• 开放地址法：冲突后按规则探测下一个位置（线性探测、二次探测、双重哈希）

Swift 的 Dictionary 和 Set 使用开放地址法，基于亚秒级哈希算法实现，性能优秀。

2. 核心模板

计数哈希（字符频率）

func charFrequency(_ s: String) -> [Character: Int] {
    var freq: [Character: Int] = [:]
    for ch in s {
        freq[ch, default: 0] += 1
    }
    return freq
}

集合查找（两数之和变体）

// 判断数组中是否存在两个不同元素之和等于 target
func twoSumExists(_ nums: [Int], _ target: Int) -> Bool {
    var seen: Set<Int> = []
    for num in nums {
        if seen.contains(target - num) {
            return true
        }
        seen.insert(num)
    }
    return false
}

复杂度

• 查找/插入/删除：平均 O(1)，最坏 O(n)
• 遍历：O(n)

3. 经典题目精讲

LeetCode 49 · 字母异位词分组

题意：将字母异位词组合在一起（如 "eat" 和 "tea"）。

思路：将排序后的字符串作为 key，异位词排序后相同。也可用 26 字母计数作为 key。

func groupAnagrams(_ strs: [String]) -> [[String]] {
    var groups: [String: [String]] = [:]
    for str in strs {
        let key = String(str.sorted())
        groups[key, default: []].append(str)
    }
    return Array(groups.values)
}

LeetCode 128 · 最长连续序列

题意：给定未排序数组，找最长连续整数序列长度。要求 O(n)。

思路：全部放入 Set，然后只从序列起点（num-1 不在 Set 中）开始向后数。

func longestConsecutive(_ nums: [Int]) -> Int {
    let numSet = Set(nums)
    var longest = 0
    for num in numSet {
        // 只从序列起点开始
        if !numSet.contains(num - 1) {
            var curNum = num
            var curLen = 1
            while numSet.contains(curNum + 1) {
                curNum += 1
                curLen += 1
            }
            longest = max(longest, curLen)
        }
    }
    return longest
}

LeetCode 146 · LRU 缓存（哈希 + 双链表思路）

题意：设计 O(1) get/put 的 LRU 缓存。

思路：哈希表存储 key 到节点的映射，双向链表维护访问顺序。每次访问把节点移到头部，淘汰时删尾部。详见 LRU 缓存专题。

4. 易错点

• ⚠️ Swift 中 Dictionary 访问不存在的 key 返回 nil，用 dict[key, default: 0] 避免手动判空
• ⚠️ 自定义类型作为 Dictionary key 必须实现 Hashable 协议
• ⚠️ 遍历 Dictionary 时顺序不确定，如需有序需用排序后的数组
• ⚠️ 哈希表最坏情况退化为 O(n)，面试中可以说"平均 O(1)"

5. 推荐刷题清单

题号	题名	难度	关键
1	两数之和	Easy	哈希查找
49	字母异位词分组	Medium	排序 key
128	最长连续序列	Medium	Set 优化
146	LRU 缓存	Medium	哈希+双链表
560	和为 K 的子数组	Medium	前缀和+哈希

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS) 第 11 章