散列：原理
看完你能讲清散列表为何 O(1) 查找，以及何时会失效
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
散列：原理
看完你能讲清散列表为何 O(1) 查找，以及何时会失效
电话查号台的启示
上一节我们说散列是一种映射。但映射到底意味着什么、它和翻字典有什么本质不同？让我们从最熟悉的电话查号台说起。
字典要排序+二分；查号台靠映射直接定位，不必遍历
散列的核心思想
左侧多个键汇入散列函数，右侧分散到不同地址再定位取值
循值访问是什么
上页说散列把关键字变成存储地址。这「变」的过程就是循值访问：不靠位置、不靠顺序，单凭值本身就能算出它该去哪。
取件码直接对应柜格，输入即开门
数组的随机访问
从下标到值的 O(1) 路径：自左向右走一次完整的随机访问，每步耗时恒定。
循值访问的数组方案
前一页说数组按下标访问是 O(1)，一步到位。可我们的需求是反过来的：拿到一个值，直接找到它，别遍历。怎么把「按值」变成「按下标」？答案只有一个动作：把值变成下标。
把客人名映射为房号,拿到号就能直奔房间,不必逐间敲
散列函数是什么
前页我们让数组下标直接等于键——但现实中键往往是字符串这样的复杂数据，没法当下标用。需要一个"翻译器"把任意键变成整数下标，这就是散列函数。
客人姓名（输入）对应房间号（输出），规则固定但同姓会撞房
散列函数的实现
两份最小可运行的散列实现：整数取模 + 字符串多项式滚动哈希。
取模把任意整数压成数组下标；字符串先被多项式编码成整数，每步取模防溢出。'hash' 与 'Hash' 落入不同桶。
散列查找的完整流程
一次散列查找分四步走完，每一步都不能少。
什么是冲突
散列函数把键变成数组地址，理想情况下一一对应。但键的取值范围远大于数组长度，总会有不同键算出同一个地址——这就是冲突。
20人只15个柜，必有两人分到同柜，钥匙对不上
冲突的概率分析
从左到右: 直觉→配对洞察→精确累乘→拐点
装填因子与性能
上一页用生日悖论说明元素越多越容易撞——但'多'是相对的，撞的概率取决于表有多满。装填因子就是把这种'满'精确量化成一个数字。
停车场越满，找空位要绕的圈越多，对应 α 越大平均探测次数越多
两大流派对比
解决冲突的两种思路完全不同——原地探测 vs 链式延伸，这一根本分歧决定了内存布局、缓存行为与负载能力的差异。
- 冲突时探测数组内下一个空槽
- 数据连续存放，缓存极友好
- 装填因子需<0.7，否则性能崩塌
- 冲突时在该槽位挂链表延伸
- 数组配指针，节点离散分布
- 可大于1，删除只需摘节点
开放地址法图解
发生冲突后，三种探测法从h出发，按各自规则生成探查序列。
链地址法图解
上方是桶数组，每个槽位挂一条链表；冲突键串在同一条链。
链地址法的插入操作
C 语言实现链地址法的"头插法"插入，五步即可完成。
头插法精髓就在这五行—— ④⑤ 两步完成 O(1) 插入:先让新节点指向旧链头,再把桶首指针改成新节点;顺序反了旧链表就丢了。
再散列
上一页说过，装填因子越大冲突越多、性能越差。怎么办？把表扩大、把元素重新散列一次——这就是「再散列」。
旧房住不下→找大一倍新房→所有家具按新房间重新摆位
删除操作的陷阱
开放地址法靠探测链走到底——只要中间出现一个「空」，就认为「后面没有」。删除时如果直接清空槽位，就把探测链切断了。
书被借走不放「已借出」牌子，读者看到空位就以为没这本书
自测检验
散列查找平均可达 O(1) 的最核心原因是什么？
本章要点
- ✓本质是空间换时间，均摊O(1)有前提
- ✓冲突是鸽巢原理的必然，非偶然
- ✓装填因子超0.7，性能拐点出现
- ✓开放地址vs链地址：看场景权衡
- ✓开放地址删除不标记=埋雷
课后思考
三道题覆盖核心机制、工业实践、安全边界。建议先合上书自己想 5 分钟，再对照参考答案检验思路。
参考答案开放地址法每个槽只容一个元素，空槽变少会让探测序列越来越长，并出现连续占用的'聚簇'；链地址法每个槽是链表，再满也只是链表变长，查找仍是 O(1+α)，扩展代价平滑。
参考答案0.75 是空间与时间的折中点。装填因子越小空间浪费越多，越大冲突概率按指数级上升；0.75 时扩容触发概率（泊松分布）约 0.5%，是工业界公认的甜点，也有数学推导支撑。
参考答案会出现。攻击者可精心构造大量哈希碰撞的键发起'哈希洪水攻击'，让服务端性能骤降。Java 早期 String 哈希因此被攻破，现引入链表转红黑树优化；Python 用随机化哈希种子防御。