拉链法和开放寻址法各有什么优缺点？该怎么选？
简化版
拉链法给每个桶挂链表，冲突元素串起来，好删、负载因子能大于 1，但有指针开销、缓存不友好；开放寻址法让冲突元素在同一个数组里探测找空位，缓存友好、省内存，但删除麻烦、负载因子必须小于 1、易聚集。内存紧张/读多/追求缓存性能选开放寻址；频繁增删/负载高/实现简单选拉链。
详细版
| 维度 | 拉链法 | 开放寻址法 |
|---|---|---|
| 存储 | 桶 + 链表/红黑树 | 所有元素都在数组里 |
| 内存 | 每节点多存指针 | 无指针，但需留空位 |
| 缓存友好度 | 低（节点分散） | 高（连续数组） |
| 负载因子 | 可 > 1 | 必须 < 1（否则装满） |
| 删除 | 简单，改指针 | 麻烦，需墓碑标记 |
| 冲突严重时 | 链表变长（可转树） | 探测链变长 + 聚集 |
| 对哈希函数要求 | 相对宽松 | 更敏感 |
| 代表 | Java HashMap | Python dict、ThreadLocalMap |
完整版教学
一、拉链法的优缺点细看
优点：
- 删除简单：找到节点改前后指针即可，不影响其他元素。
- 负载因子可 > 1：链表能一直接，元素比桶还多也不会「装满」，只是链变长。
- 对哈希函数宽松：即使分布一般，也就是某些链稍长，不会像开放寻址那样触发大面积聚集。
缺点：
- 指针内存开销：每个节点多存一两个指针。
- 缓存不友好：链表节点在堆上分散，遍历时频繁 cache miss。
- 冲突严重会退化：链表变长查找 O(n)（Java 8 用红黑树把它压到 O(log n)）。
二、开放寻址法的优缺点细看
优点：
- 缓存友好：所有元素连续存在数组里，探测时基本命中缓存，实测常常比拉链快。
- 省内存：没有链表指针，数据密度高。
缺点：
- 删除麻烦：不能直接把槽位清空——否则会中断「探测链」，让后面本该找到的元素误判为不存在。必须用墓碑（tombstone）标记「这里删过」，查找时继续往后探，插入时可复用。墓碑积累多了还得整理。
- 负载因子必须 < 1：数组一旦接近满，探测代价急剧上升，所以要更早扩容。
- 聚集问题：线性探测会让占用的槽连成一片，冲突进一步加剧；需二次探测/双重哈希缓解。
- 对哈希函数更敏感：分布不均会显著放大聚集。
三、为什么删除是开放寻址的经典坑
假设 A、B 冲突，A 在下标 5，B 被线性探测放到下标 6。现在删掉 A，若把下标 5 直接清空：之后查 B 时算出下标 5 是空的，就会误以为「B 不存在」而停止探测——其实 B 在下标 6。所以必须留个墓碑告诉查找逻辑「这里删过，请继续往后找」。这是开放寻址实现时最容易错的点。
四、怎么选（结论）
- 选开放寻址：内存敏感、追求缓存/查询极致性能、元素以查为主、能接受更早扩容。典型如 Python
dict、Java 的ThreadLocalMap。 - 选拉链：增删频繁、负载可能较高、想要实现简单健壮、不想被聚集困扰。典型如 Java
HashMap、大多数教学与通用实现。
没有绝对优劣，是「缓存/内存」和「删除便利/负载弹性」之间的权衡。
五、复杂度与适用边界
| 维度 | 拉链法 | 开放寻址法 |
|---|---|---|
| 冲突位置 | 桶外链表/树 | 数组内部继续探测 |
| 删除 | 相对直接 | 需要墓碑或重排 |
| 负载因子 | 可超过 1 | 通常不能太高 |
| 缓存局部性 | 指针跳转较多 | 数组连续更友好 |
拉链法:
bucket[2] -> A -> B -> C
开放寻址:
bucket[2]=A, bucket[3]=B, bucket[4]=C开放寻址在负载因子接近 1 时会出现很长探测序列，例如容量 1000 已经放了 900 个元素，插入新元素可能连续探测多个已占位置。拉链法即使桶里有多个元素，也能把冲突限制在对应桶的链上，但会付出额外指针和节点对象成本。
记忆钩子：拉链法把冲突“挂到桶外”，开放寻址把冲突“挤在数组里”。一个删除更自然，一个局部性更好，选择时看负载、删除和内存模型。
六、常见误区与追问
- 误区：开放寻址法就是没有冲突。 它只是把冲突元素继续放在数组其他位置，冲突仍然存在。
- 误区：拉链法一定比开放寻址法慢。 拉链法删除简单、负载因子弹性大；开放寻址缓存友好但怕高负载和删除复杂。
- 误区：开放寻址删除直接置空就行。 直接置空会截断后续探测路径，导致本来存在的元素查不到。
- 追问：什么是墓碑标记？ 删除时不直接清空，而是标记为 deleted，让查找能继续越过这个位置。
- 追问：Java HashMap 更接近哪种？ 常规 HashMap 使用拉链法，冲突严重时链表可树化。
- 追问：开放寻址适合什么场景？ 数据量可控、负载因子较低、追求数组局部性和较少对象分配的场景。
七、加强记忆
拉链法「桶外挂链」：好删、负载可>1、宽松，但有指针、缓存差；开放寻址「数组内探测」：缓存好、省内存，但删除要墓碑、负载须<1、易聚集。内存紧/读多选开放寻址，增删多/负载高选拉链。开放寻址删除必须用墓碑标记，否则会中断探测链。