Ch14 §01 数组与哈希 · 讲解稿¶

章节定位: Ch14 最基础的数据结构。教"如何用 \(O(1)\) 访问 / 查找": 静态数组 / 动态数组 / 哈希表 / 滑动窗口 / 双指针。承接: §00 复杂度 → §01 数组 + 哈希走向: §02 链表 / §03 树 / §04 图 / §05 排序篇幅: ~3800 字 / 阅读 11 分钟 / 讲解 22-25 分钟

一 · 一句话总览¶

数组 + 哈希 = \(O(1)\) 访问与查找。AI 工程师日常 90% 时间在用 list / dict / set / numpy array。本节教底层 + 经典算法 (滑动窗口 / 双指针)。

二 · 章节主线 (5 段)¶

第 1 段 · 数组基础 (8 分钟)¶

3.1.1 静态 vs 动态¶

维度	静态数组	动态数组 (vector / list)
大小	编译期	运行期
访问	\(O(1)\)	\(O(1)\)
末尾插入	N/A	\(O(1)\) 平摊
中间插入	N/A	\(O(n)\)

3.1.2 Python list 实现¶

连续 C 数组
装填因子 1.125× 扩容
中间插入需移动后续元素

# Python list 操作
arr = [1, 2, 3, 4, 5]
arr[2]        # O(1) 访问
arr.append(6) # O(1) 平摊
arr.insert(2, 99)  # O(n) 插入
arr.pop()     # O(1)
arr.pop(0)    # O(n)

3.1.3 双指针¶

用两个指针遍历, 节省空间 + 时间。

# 两数之和 (有序数组)
def two_sum(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target: return [lo, hi]
        elif s < target: lo += 1
        else: hi -= 1
    return []

3.1.4 经典问题¶

三数之和
盛最多水的容器
接雨水

第 2 段 · 哈希表 (10 分钟)¶

3.2.1 原理¶

键 → 哈希函数 → 桶号 → 值。

3.2.2 哈希函数¶

def h(key, m):
    return hash(key) % m

要求: 均匀, 快速, 确定。

3.2.3 冲突解决¶

链地址 (chaining): 每桶链表。

class HashTable:
    def __init__(self, m=16):
        self.m = m
        self.buckets = [[] for _ in range(m)]

    def put(self, key, val):
        idx = hash(key) % self.m
        for i, (k, v) in enumerate(self.buckets[idx]):
            if k == key:
                self.buckets[idx][i] = (k, val)
                return
        self.buckets[idx].append((key, val))

    def get(self, key):
        idx = hash(key) % self.m
        for k, v in self.buckets[idx]:
            if k == key:
                return v
        return None

开放定址: 冲突时探查下一桶。

3.2.4 装填因子与扩容¶

\(\alpha = n/m\)。\(\alpha > 0.7\) 时扩容 (rehash), 性能下降。

3.2.5 Python dict¶

开放定址哈希表
装填因子 2/3
3.7+ 保插入序
哈希函数用 SipHash (防 HashDoS)

d = {"a": 1, "b": 2}
d["c"] = 3
d.get("a", 0)  # 默认值

3.2.6 一致性哈希¶

节点 / 数据映射到环, 增删节点只影响邻居。用于分布式缓存。

第 3 段 · 滑动窗口 (8 分钟)¶

3.3.1 固定窗口¶

# 固定窗口: 长度 k 子数组最大和
def max_sum_subarray(nums, k):
    s = sum(nums[:k])
    best = s
    for i in range(k, len(nums)):
        s += nums[i] - nums[i - k]
        best = max(best, s)
    return best

\(O(n)\) 时间, \(O(1)\) 空间。

3.3.2 变长窗口¶

# 最长无重复字符子串
def length_of_longest(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

\(O(n)\) 时间, \(O(k)\) 空间 (k 是字符集)。

3.3.3 经典问题¶

最小覆盖子串
字符串的排列
长度最小的子数组

第 4 段 · 前缀和与差分 (5 分钟)¶

3.4.1 前缀和¶

# prefix[i] = sum(nums[:i])
nums = [1, 2, 3, 4, 5]
prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)
# prefix = [0, 1, 3, 6, 10, 15]

# 区间求和 O(1)
def range_sum(i, j):  # [i, j)
    return prefix[j] - prefix[i]

3.4.2 差分¶

# 区间加
diff = [0] * n
diff[l] += val
diff[r] -= val  # 如果区间右开
# 还原
arr = [0] * n
for i in range(1, n):
    arr[i] = arr[i-1] + diff[i]

第 5 段 · 实战与陷阱 (8 分钟)¶

3.5.1 字符串哈希¶

# Rolling hash
def rabin_karp(text, pattern):
    n, m = len(text), len(pattern)
    base = 256
    mod = 10**9 + 7

    h_pat = 0
    h_txt = 0
    for i in range(m):
        h_pat = (h_pat * base + ord(pattern[i])) % mod
        h_txt = (h_txt * base + ord(text[i])) % mod

    for i in range(n - m + 1):
        if h_pat == h_txt:
            if text[i:i+m] == pattern:
                return i
        if i + m < n:
            h_txt = ((h_txt - ord(text[i]) * pow(base, m-1, mod)) * base + ord(text[i+m])) % mod
    return -1

3.5.2 数组去重¶

# O(n) 哈希
def unique(nums):
    seen = set()
    result = []
    for x in nums:
        if x not in seen:
            seen.add(x)
            result.append(x)
    return result

# O(n log n) 排序
def unique_sorted(nums):
    return sorted(set(nums))

3.5.3 Top K Frequent¶

import heapq
from collections import Counter

def top_k_frequent(nums, k):
    cnt = Counter(nums)  # O(n)
    return heapq.nlargest(k, cnt.keys(), key=cnt.get)  # O(n log k)

3.5.4 陷阱¶

数组越界: arr[i] 访问前检查 \(i < n\)。
哈希函数差: 自定义 hash 要均匀, 否则退化 \(O(n)\)。
Python dict 内存: 占用 ~3× 列表。
numpy vs list: numpy 数组定长, 列表变长。
链地址过长: 装填因子高, 转红黑树 (Java 8+ HashMap)。

三 · 易错点 (5 条)¶

数组 vs 链表: Python list 不是链表。
哈希最坏: \(O(n)\) 而非 \(O(1)\)。
滑动窗口边界: 左右指针, 包含 / 不含, 写清楚。
前缀和 0: \(prefix[0] = 0\) 必须, 否则 \(range\_sum(0, j)\) 错。
dict 哈希冲突: Python 内部已处理, 但自定义类需实现 __hash__ 和 __eq__。

四 · 跨章连接¶

章节	关联
Ch07 §04 Transformer	token embedding 是数组
Ch08 §04 Diffusion	滑动窗口 attention
Ch12 §03 GNN	邻居索引是哈希
Ch13 §04 MapReduce	partition 用哈希

五 · 自测 5 题¶

数组访问复杂度? 链表?
哈希表平均查找复杂度?
滑动窗口适用场景?
一致性哈希的优势?
Python list 的扩容?

六 · 一句话总结¶

数组 + 哈希 = \(O(1)\) 访问 + 查找。日常 90% 时间用 list / dict / set。滑动窗口 + 双指针 + 前缀和是 3 个核心技巧。Ch14 §02 进入链表结构。

七 · 板书建议¶

[板书 1: 数组]
   静态 / 动态
   Python list: 1.125× 扩容

[板书 2: 哈希]
   h(k) = k mod m
   链地址 vs 开放定址
   α = n/m

[板书 3: 滑动窗口]
   固定 / 变长
   双指针

八 · 参考资料¶

Cormen et al., CLRS Ch 11 (哈希表)
Python 文档: dict, list
Ch07 §04 Transformer (本套书)
LeetCode Top Interview Questions