哈希表：散列函数、冲突解决与扩容

02-线性数据结构核心预计 25 分钟哈希表散列冲突期望O(1)

学习状态：

一句话定义

哈希表（Hash Table）用散列函数（Hash Function）把键映射到桶数组下标，以「数组寻址 O(1) + 冲突处理」实现期望 O(1) 的插入、查找与删除，是最重要的期望常数级结构。

为什么重要

从缓存、去重、计数到数据库索引与语言字典，哈希表是工程中出现频率最高的结构；「期望 O(1) 但最坏 O(n)」这一非对称保证也集中了本库最多的分析训练——负载因子、期望探测长度、rehash 均摊，全是 kp-002/kp-004 的直接应用。面试与日常排障（哈希碰撞攻击、乱序输出）都绕不开它。

前置知识

kp-001（ADT）、kp-004（均摊）、模运算基础。

核心概念

散列函数三要求：确定性（同键同值）、均匀性（键均匀落到各桶）、雪崩性（键微变则哈希值大变）；工程实现常为「先算 hash，再映射到桶」两步。
冲突（Collision）：不同键映射到同一桶。两大策略：链地址法（链表挂同桶键）与开放寻址（探测序列找空位：线性探测、二次探测、双重散列）。
负载因子：α = n/m（元素数/桶数）。链地址法期望成功查找约 1 + α/2 次比较；开放寻址期望探测约 1/(1−α) 次（α→1 时爆炸）。
扩容（Rehash）：α 超阈值（工程常 0.75，或 Java 8 HashMap 链表长 8 转红黑树）时桶数翻倍、全量重散列；单次 Θ(n)，均摊 O(1)（kp-004）。
无序性：哈希表不保序；需要有序遍历要用树结构（kp-012/kp-013）或跳表。

原理与机制

哈希表是「两级筛」机制：散列函数做粗筛（O(1) 定桶，同桶只是候选），equals 做精筛（桶内逐个精确确认）。扩容机制与之配套：负载因子超阈值即翻倍桶数并全量重散列，把 α 拉回常数级——倍增让 rehash 间隔与搬迁代价呈几何级数（均摊 O(1)），散列函数的均匀性决定候选分布。两级筛共同支撑「期望 O(1)、最坏 O(n)」的非对称保证。

直观类比

哈希表是图书馆的「按书名首字母分架」：报书名，管理员按规则直接走到某书架（O(1)）；两本书被分到同一格就是冲突——要么同格并排（链地址），要么顺延放下一格（开放寻址）；书太多格子挤了就整体换更大的柜子并重新分架（rehash）。

公式或模型

桶映射：bucket = hash(key) mod m；m 取 2 的幂时可用位运算 hash & (m−1)，并用扰动函数把高位混入低位。
链地址法期望：查找成功 ≈ 1 + α/2，失败 ≈ α + e^(−α) ≈ α（α 有界时常数）。
开放寻址（均匀散列假设）期望：成功 ≈ (1/α)·ln(1/(1−α))，失败 ≈ 1/(1−α)。α=0.75 时失败探测已约 4 次，α=0.9 时 10 次——这就是工程上限设在 0.7~0.75 的原因。

图示

链地址法:                     开放寻址（线性探测）:
桶0 ─ [k1]→[k9]→∅             [ , k7, k8, k11, , ] ← k5 撞 k7：
桶1 ─ [k3]→∅                     探测下一格…直到空位插入
桶2 ─ [k5]→[k8]→[k11]→∅      查找 k11：从 k7 起顺延比较
扩容: m 4→8 时每个键重新取 mod，整表重排（Θ(n) 一次，均摊 O(1)）

实例或案例

词频统计：map[词] += 1，一次遍历 O(n) 期望完成，是文本处理第一工具。
Python dict：开放寻址 + 扰动；Java 8 HashMap：链地址 + 链表长 8 转红黑树（最坏从 O(n) 压到 O(log n)，缓解碰撞攻击）；Go map：桶内 8 槽 + 溢出桶。
数据库哈希索引、Memcached 的内存哈希；路由表中精确匹配。

常见误区

用可变对象当键或重写字段后不重算哈希：键「失踪」。键必须不可变或哈希稳定，且 equals 与 hashCode 必须一致（相等 ⇒ 同哈希）。
认为哈希表「有序」或「按插入序」：输出顺序依赖桶布局与扩容史，需要序请换树/有序结构。
只看期望 O(1) 忘了最坏 O(n)：恶意构造碰撞可把服务打挂（哈希洪水攻击），需随机化种子或树化兜底。
忽视 α 与探测退化：开放寻址在 α 逼近 1 时不只是「慢一点」，而是数量级劣化，必须及时扩容。

自测题

α = 0.75 时，链地址法期望成功查找的比较次数约为多少？开放寻址失败探测期望呢？

答案要点：约 1 + 0.375 ≈ 1.4 次；开放寻址失败 ≈ 1/(1−0.75) = 4 次。

为什么 equals 相等的两个对象必须哈希相同，反之哈希相同却不要求相等？

答案要点：哈希是「先分桶后比较」的第一道筛；同桶只是候选，最终靠 equals 精确判定，反向不成立（允许冲突）。

设计支持按插入序遍历的哈希表，思路是什么？

答案要点：链地址 + 额外一条贯穿所有条目的双向链表记录插入序（LinkedHashMap 的做法），占用多一指针代价。

与其他知识点的关系

kp-010 把哈希推到分布式（一致性哈希）与概率（布隆过滤器）；kp-012/kp-013 是「要有序」时的替代方案；kp-030 并查集内部也用哈希思想做映射；kp-007 双向链表支撑 LRU 组合。

延伸阅读

《算法导论》第 11 章（11.2 链地址、11.4 开放寻址）；Kirsch & Mitzenmacher 关于布隆过滤器哈希族的结果可衔接 kp-010。