哈希表：链地址法
链地址法用哈希函数把键映射到桶。本课为 h(k) = k mod capacity。冲突的键存入同一个桶的链中；一次操作只处理该桶。哈希分布良好、负载因子保持常数时，平均操作时间为 O(1)。
像把信件按门牌号取模放入信箱：先直接找到信箱，再在共享该箱的信件中查找。冲突的成本就是桶内搜索。
链地址法如何工作
数组有 capacity 个桶，每桶保存一条键链。先计算 h(k)，再跳到对应桶，其余桶不参与。
insert(k) 先逐个比较。已有相同键就返回，不修改；本课是集合语义，不是键值更新。未命中则把新键放到链头。真正链表的头插为 O(1)，但展示的 Python chain.insert(0, ...) 使用数组列表，会移动链内元素，成本 O(链长)。这不改变总体查重的线性桶内成本，却不能把展示实现的头插单独说成常数时间。
get(k) 返回匹配的链内位置，未找到返回 -1。delete(k) 找到后移除并返回 True，其余链项重新相连。不需要墓碑，也不扰动其他桶。真实链表只改邻接指针；展示的数组列表删除还会移动本桶后续元素。
三种操作都是：计算哈希、扫描桶链、根据比较结果决定。全表的地址冲突被限制到一条链内。
逐步演示
默认五个空桶，h(k) = k mod 5：
insert(7)：7 % 5 = 2，桶 2 为空，头插后[7]。insert(12)：12 % 5 = 2，与 7 冲突。比较[2][0] = 7，未命中，头插后[12, 7]，新值在前。insert(3)：3 % 5 = 3，桶 3 直接变为[3]，不扫描桶 2。insert(17)：17 % 5 = 2，依次比较[2][0] = 12、[2][1] = 7，均不等，头插后[17, 12, 7]。get(12)：哈希到 2，先比较 17，再命中位置 1 的 12。全表有四个键，但本次只比较两次。delete(12)：同样越过 17，在深度 1 命中，移除后桶 2 为[17, 7]。
再查 get(22)：它也映射到 2，扫描整条链后返回未找到。缺失查询要支付完整链长的成本。
播放器限制单链最多六个节点，超出时说明是显示深度限制。这个上限用于适配 1920×1080 画布，不是链地址法的结构上限；冲突链可以继续增长，只会变慢。
画布把桶竖排，链向右展开。游标逐节点比较，命中变绿，新键从链头进入。哈希、遍历和提交变化分成不同步骤。
时间与空间复杂度
负载因子 α = n / capacity 也是每桶平均条目数。
| 操作 | 平均，α 为常数且哈希分布良好 | 最坏 |
|---|---|---|
insert | O(1) | O(n) |
get | O(1) | O(n) |
delete | O(1) | O(n) |
更完整的平均界为 O(1 + α)：一次哈希加期望桶内查找。链地址法允许 α 超过 1；开放寻址则必须为新键保留槽位。所有键集中到一桶时，最坏退化为一条长度 n 的链。攻击者也可能刻意构造冲突，适当的哈希设计或针对适用键类型的随机种子可降低此类风险。
空间为 O(n + m)，n 个条目加 m 个桶；即使空表也要保存桶数组。
边界情况
- 重复插入：找到键后不修改。键值字典可在同一位置更新值，但本课没有该语义。
- 空桶：插入立即头插；查询和删除在空链结束并报告未找到。
- 删除缺失键：扫描完返回
False，状态不变。 - 全部冲突：仍然正确，只是桶内查找变长。
常见错误
- 把条目数不能超过容量当规则。 1000 桶可保存 5000 条目，平均每桶五项。是否扩容取决于目标性能，阈值不是通用的 0.75 或 1.0。
- 从不扩容。 固定桶数下持续增加键会拉长链。负载因子过高时，扩容并重新分桶。
- 跳过查重。 重复副本会让查询只找到前一份，删除只移除一份，破坏集合语义。
- 把简单取模当作适用于所有键的哈希。 输入存在规律时，某些桶会集中冲突。实际方案可能先混合位，如 MurmurHash、SipHash，或对适用类型使用带种子的哈希；不能假设所有语言和键类型都采用同一种机制。
- 忽略内存行为。 链式实现删除简单、允许较高负载，但需追踪节点；开放寻址用连续数组，在适当负载下有缓存优势。按访问模式选择。