拉链法处理冲突
复习
- 哈希函数与哈希表：根据键直接算出位置
- 单向链表：节点用指针相连
- 数组：连续存储，可按下标访问
TL;DR
- 拉链法把落到同一位置的元素串成一个链表
- 查找时先定位位置，再在链表里找
- 实现简单，删除也方便
- 冲突多时链表变长，性能随之下降
正文
上一章说，不同的键可能算出同一个位置。拉链法（chaining）是最直观的解决办法：既然撞车了，那就让它们排成一队。
每个位置挂一条链
拉链法的结构是：一个数组，每个格子叫一个“桶”（bucket）。每个桶里，挂着一条链表。
- 存入时：先算出位置，再把新元素挂到那个桶的链表上 - 查找时：先算出位置，再到那个桶的链表里逐个比较
于是，即使多个键算到了同一个位置，它们也只是在同一条链上各占一个节点，不会互相覆盖。
实现简单，删除方便
拉链法有几个讨喜的地方：
- 不用为“表会不会满”发愁：链可以随时加长
- 删除方便：在链表里摘掉一个节点即可，不像开放寻址那样要特殊处理
- 实现自然：数组加链表，都是熟悉的东西
它的代价，是要为每个节点多存一个链表的指针，占用额外空间。
链太长就慢了
拉链法的性能，取决于链的长度。
理想情况下，绝大多数桶里只有一两个元素，查找接近 O(1)。但如果哈希函数不好，或者数据太多，导致某些桶的链拉得很长，那么查找这些键时，就退化成了“在链表里顺序查找”，最坏是 O(n)。
所以，关键在于控制链的长度：让元素尽量均匀分布，并在链变长时及时扩容。这正是下一章要谈的“负载因子”。
拉链法用“额外的链表”来化解冲突。也有另一派思路，选择不引入额外结构，直接在表里找地方——下一章来看。
思考题 1
拉链法为什么用链表，而不是再用一个数组来存放冲突元素？
思考题 2
如果很多键都落到了同一个桶，拉链法的性能会怎样？
小结
知识点
- 拉链法在每个桶上挂一条链表
- 存入与查找都先定位桶，再在链上操作
- 实现简单、删除方便，但需额外指针空间
- 链过长时查找退化为
O(n)
参考资料
- Wikipedia(zh)：哈希表：包含拉链法等冲突处理方式
- Wikipedia(zh)：链表：拉链法中用于串联冲突元素
思考题答案（仅供参考）
思考题 1
因为冲突元素的个数事先不确定，链表可以按需动态增长，插入删除都方便，也不必预分配固定容量。用数组还得处理扩容，反而更麻烦。链表天然适合“数量不定、需要频繁增删”的场景。
思考题 2
那个桶的链表会变得很长，查找、插入都要在链上一个个走，退化成链表的顺序操作，最坏达到 O(n)，O(1) 的优势荡然无存。所以需要控制负载因子，必要时扩容。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪