冲突解决：链地址法与开放寻址法

基于通用算法套路 · 核于 2026-07

速查

• 冲突无法消灭：鸽巢原理决定只要 key 多于桶数必有冲突，只能「解决」——主流是链地址法和开放寻址法两大流派。
• 链地址法（Separate Chaining）：每个桶挂一个链表，冲突的 key 全部串进同桶链表；查/插/删先算下标再在链表里操作；链表过长（Java 阈值 8）转红黑树，把最坏 O(n) 压到 O(log n)。
• 开放寻址法（Open Addressing）：不挂链表，冲突时在桶数组里按某规则探测下一个空槽——线性探测（+1,+2,...）、二次探测（+1²,+2²,...）、双重哈希（用第二个哈希函数算步长）。
• 线性探测的聚集（clustering）问题：连续被占的槽会越长，新插入容易撞进聚集块、进一步堆长，性能恶化；二次探测/双重哈希用变长步长打散聚集。
• 删除的坑：开放寻址法不能直接清空槽位（会断开探测链），要用墓碑标记（tombstone）——标记「逻辑删除」，探测时跳过、插入时可复用。
• 负载因子上限：链地址法可 >1（链表能挂任意多）；开放寻址法必须 <1（桶满了就无处探测），通常控制在 0.5~0.7。
• 各语言实现：Java HashMap、C++ unordered_map、Go map、JS Object/Map 多用链地址法；Python dict 用开放寻址法（伪随机探测）。
• Java HashMap 红黑树阈值：链表长度 ≥8 且桶数 ≥64 时转红黑树，退化到 ≤6 时还原链表——防哈希碰撞攻击。
• 负载因子与 rehash 时机：Java 默认 0.75（链地址），Python dict 约 2/3（开放寻址），超阈值即翻倍桶 + 重新哈希。
• 进阶：哈希函数设计与应用 → 参考。

一、链地址法：每个桶挂一条链表

链地址法（Separate Chaining） 的思路最直接：每个桶不存单个元素，而是挂一个链表（或动态数组）。冲突的 key 全部追加到同一个桶的链表里。

buckets[0] -> (k1,v1) -> (k2,v2) -> null
buckets[1] -> (k3,v3) -> null
buckets[2] -> null
buckets[3] -> (k4,v4) -> (k5,v5) -> (k6,v6) -> null

操作流程：算下标 i = hash(key) % capacity，然后在 buckets[i] 这条链表上做查/插/删。

// 链地址法 put
put(key, value) {
  const i = this._index(key);
  const chain = this.buckets[i];
  for (const node of chain) {
    if (node.key === key) { node.value = value; return; } // key 已存在，覆盖
  }
  chain.push({ key, value });  // 新增到链表尾部
  this.size++;
  if (this.size / this.buckets.length > this.loadFactor) this._rehash(); // 超阈值扩容
}

• 优点：实现简单；负载因子可超过 1（链表能挂任意长）；删除直接摘节点，没有墓碑问题。
• 缺点：链表节点分散在堆上，缓存不友好；链表过长时退化成 O(n) 扫链表。
• 优化：链表转红黑树：当某桶链表过长时，把它转成红黑树，查找从 O(n) 降到 O(log n)。Java HashMap 在链表长度 ≥8 且桶数 ≥64 时转红黑树，退化到 ≤6 时还原链表——这有效防御了哈希碰撞攻击（攻击者构造大量冲突 key 让链表变长）。

二、开放寻址法：在数组里探测空槽

开放寻址法（Open Addressing） 不挂任何辅助结构，冲突时就在桶数组里另找一个空槽存进去。核心是探测序列（probe sequence）——冲突后按什么规则找下一个槽。三者区别在于探测步长函数 probe(i)：

方法	探测序列	步长特点	主要问题
线性探测 Linear	h, h+1, h+2, ...	固定步长 1	一次聚集（primary clustering）
二次探测 Quadratic	h, h+1², h+2², ...	步长平方增长	二次聚集（同起点探测序列相同）
双重哈希 Double	h + i×h2(key)	第二个哈希函数算步长	最难聚集，需 h2 与容量互质

// 线性探测：冲突就往后一个一个找空槽
put(key, value) {
  let i = this._index(key);
  while (this.buckets[i] !== null && this.buckets[i].key !== key) {
    i = (i + 1) % this.buckets.length;  // 往后探测，到尾回绕
  }
  if (this.buckets[i] === null) this.size++;
  this.buckets[i] = { key, value };
  if (this.size / this.buckets.length > this.loadFactor) this._rehash();
}

线性探测的聚集问题

线性探测最大的毛病是聚集（clustering）：一旦出现一小段连续被占的槽，后续插入的 key 只要哈希落在这段区间内，就会一路探测到这段尾部填进去，让聚集块越来越长。聚集块越长，新插入撞进去的概率越大，形成恶性循环——平均探测次数随负载因子上升而急剧恶化。经验上，线性探测在负载因子 >0.7 后性能明显变差。

二次探测与双重哈希

• 二次探测：步长按平方增长 i²，能快速跳离聚集区，缓解一次聚集；但所有同起点 key 的探测序列完全相同，会产生二次聚集。
• 双重哈希：用第二个哈希函数 h2(key) 算步长，即探测 h + i×h2(key)。不同 key 的步长不同，探测序列高度差异化，最难聚集——但要求 h2 永不返回 0 且与 capacity 互质（容量取素数保证）。

删除的墓碑问题

开放寻址法不能直接把槽清空——因为探测链依赖「冲突的 key 沿着被占槽一路找下去」，中间清空一个槽会断开后续 key 的探测路径，导致查找丢失已存在的 key。解决办法是墓碑标记（tombstone）：删除时不清空，而是标记为「逻辑已删除」，探测时跳过它、插入时可以复用它。墓碑过多会拖慢查找，需要定期 rehash 清理。

三、链地址法 vs 开放寻址法

维度	链地址法	开放寻址法
辅助结构	每桶链表/红黑树	无，纯数组
负载因子上限	可 >1	必须 <1
缓存友好	差（链表节点分散）	好（全在数组里）
实现复杂度	简单	探测 + 墓碑较繁
删除	直接摘节点	需墓碑标记
适合场景	key 多、负载因子高	key 少、负载因子低、追缓存性能
代表实现	Java HashMap、C++ unordered_map	Python dict、Ruby Hash

选型经验：通用场景（Java/Go/JS）多用链地址法（实现简单、抗冲突能力强、有红黑树兜底）；追求缓存性能且负载因子低时用开放寻址（Python dict 用伪随机探测，把缓存优势发挥到极致）。

四、负载因子与 rehash 时机

不同实现因冲突策略不同，负载因子阈值也不同：

实现	冲突策略	默认负载因子	rehash 动作
Java HashMap	链地址 + 红黑树	0.75	桶数 ×2，重新哈希
Python dict	开放寻址（伪随机）	~2/3（0.66）	桶数 ×2~×4
C++ unordered_map	链地址	1.0（max_load_factor）	桶数 ×2（取素数）
Go map	链地址（桶内数组）	~6.5	渐进式扩容

rehash 的触发都是「插入后检查负载因子，超阈值就翻倍桶数组并重新哈希所有元素」。开放寻址法因为负载因子必须 <1，阈值更低（0.5~0.7）；链地址法可 >1，阈值更高（0.75~1.0）。无论哪种，rehash 单次是 O(n)，但几何扩容下摊还 O(1)。

五、Java HashMap 的红黑树转换（面试高频）

Java 8 的 HashMap 在链地址法基础上加了一层防护：

• 链表转红黑树阈值 = 8：某桶链表长度达到 8 且整个桶数组容量 ≥64 时，把该桶链表转成红黑树，查找从 O(n) 降到 O(log n)。
• 红黑树还原链表阈值 = 6：扩容或删除后某桶节点数退化到 ≤6 时，还原成链表（红黑树常数大，节点少时链表更快）。
• 为什么选 8：基于泊松分布——负载因子 0.75 且哈希均匀时，一个桶里有 8 个节点的概率约 0.00000006（几乎不会自然发生）；只有哈希函数差或被攻击时才会触发，红黑树是「兜底防线」。
• 桶数 <64 时不转树而是扩容：小容量时优先扩容（让 key 重新散列）而非转树。

这套机制让 HashMap 在极端冲突下最坏从 O(n) 退化到 O(log n)，防御了哈希碰撞 DoS 攻击。

交互演示

• 哈希表可视化演示 —— 链地址法链表挂接、开放寻址探测序列与扩容过程

下一步

解决了冲突之后，决定哈希表性能的另一半是哈希函数本身——好哈希要均匀分布 + 雪崩效应，还要支撑去重、计数、一致性哈希等工程应用，见哈希函数设计与工程应用。