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

学习目标：学完本节，你能

说清"冲突为什么无法避免"（鸽巢原理）；
实现链地址法与开放寻址两种哈希表；
解释为什么"探测次数更多的方案反而更快"；
说清开放寻址法"负载因子必须小于 1"这个硬约束，以及墓碑的作用。

先修：6.1（哈希函数）、4.1（链表）、3.1（缓存行）。 固定术语：冲突、链地址法、开放寻址、线性探测、负载因子、墓碑。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。

一、冲突为什么无法避免

上一节说过：好的哈希函数能让冲突稀少。但"稀少"不等于"没有"。

冲突是数学上必然的，理由是鸽巢原理：

键的取值空间：几乎无限（字符串长度不限、字符不限）
哈希值的范围：有限（32 位整数只有 $2^{32} \approx 43$ 亿个）
桶的数量：更少（通常几百到几百万）

把无限多的东西映射到有限多的位置，必然有不止一个键落到同一个位置。

这不是"哈希函数写得不好"，而是任何函数都逃不掉的。

所以哈希表的设计重点从来不是"怎么避免冲突"，而是"冲突了怎么办"。

业界有两大流派：

方案	思路	代表实现
链地址法（Separate Chaining）	每个桶挂一条链表，冲突的元素接在后面	Java 8 之前的 `HashMap`、C++ `std::unordered_map`
开放寻址（Open Addressing）	所有元素都存在同一个数组里，冲突了就往后找空位	.NET 的 `Dictionary`、Python 的 `dict`

二、链地址法

思路很简单：每个桶不是一个位置，而是一条链表的头。

桶[0] -> null
桶[1] -> [张三] -> [李四] -> null          <- 张三和李四冲突了，挂在同一条链上
桶[2] -> [王五] -> null
桶[3] -> null
...

查找时：算出桶下标 → 遍历那条链表 → 用 Equals 比较找到目标。

完整实现：

/// <summary>链地址法哈希表：每个桶挂一条链表。</summary>
public class ChainedHashTable
{
    private readonly LinkedList<KeyValuePair<int, string>>?[] _buckets;
    private int _count;

    public long TotalProbes { get; private set; }     // 累计比较次数
    public long OpCount { get; private set; }         // 累计操作次数
    public int MaxChainLength { get; private set; }

    public ChainedHashTable(int capacity)
    {
        _buckets = new LinkedList<KeyValuePair<int, string>>?[capacity];
    }

    private int BucketIndex(int key)
    {
        int h = key.GetHashCode();
        return (h & 0x7FFFFFFF) % _buckets.Length;    // 去掉符号位再取模
    }

    public void Put(int key, string value)
    {
        int idx = BucketIndex(key);
        OpCount++;

        _buckets[idx] ??= new LinkedList<KeyValuePair<int, string>>();
        var chain = _buckets[idx]!;

        for (var node = chain.First; node != null; node = node.Next)
        {
            TotalProbes++;
            if (node.Value.Key == key)
            {
                node.Value = new KeyValuePair<int, string>(key, value);   // 已存在则覆盖
                return;
            }
        }

        chain.AddLast(new KeyValuePair<int, string>(key, value));
        _count++;
        if (chain.Count > MaxChainLength) MaxChainLength = chain.Count;
    }

    public bool TryGet(int key, out string? value)
    {
        int idx = BucketIndex(key);
        OpCount++;

        var chain = _buckets[idx];
        if (chain != null)
        {
            for (var node = chain.First; node != null; node = node.Next)
            {
                TotalProbes++;
                if (node.Value.Key == key) { value = node.Value.Value; return true; }
            }
        }
        value = null;
        return false;
    }
}

三个要点：

(h & 0x7FFFFFFF) 是必须的。 C# 里 -7 % 1000 == -7，负数下标会直接抛异常。& 0x7FFFFFFF 把符号位清零，比 Math.Abs 更安全（Math.Abs(int.MinValue) 会溢出）。
找到哈希值相同的元素后，还要用 == / Equals 再比较一次。 因为哈希值相同不代表键相同（6.1 节反复强调过）。
_buckets[idx] ??= new LinkedList<...>() 是延迟创建。 空桶不占链表对象的内存 —— 这是链地址法的一个重要优化，否则几百万个空桶每个都要分配一个链表对象。

三、开放寻址

思路完全不同：不用链表，所有元素都塞进同一个数组。冲突了就往后找下一个空位。

插入 key=9（假设哈希到下标 1，但 1 已经被 1 占了）：

  下标:  [0] [1] [2] [3] [4]
  内容:  [_] [1] [9] [_] [_]
              ↑   ↑
           哈希位置  往后找到的第一个空位

这叫线性探测（Linear Probing）—— 因为它是"一格一格往后试"。

完整实现：

/// <summary>
/// 开放寻址哈希表（线性探测）：所有元素都存在同一个数组里。
/// 冲突时就往后找下一个空位。删除时留下「墓碑」。
/// </summary>
public class OpenAddressHashTable
{
    private enum SlotState : byte { Empty, Occupied, Tombstone }

    private readonly int[] _keys;
    private readonly string[] _values;
    private readonly SlotState[] _states;
    private int _count;

    public long TotalProbes { get; private set; }
    public long OpCount { get; private set; }

    public OpenAddressHashTable(int capacity)
    {
        _keys = new int[capacity];
        _values = new string[capacity];
        _states = new SlotState[capacity];
    }

    private int BucketIndex(int key)
        => (key.GetHashCode() & 0x7FFFFFFF) % _keys.Length;

    public void Put(int key, string value)
    {
        int idx = BucketIndex(key);
        int firstTombstone = -1;
        OpCount++;

        // 线性探测：从 idx 开始往后找
        for (int step = 0; step < _keys.Length; step++)
        {
            int pos = (idx + step) % _keys.Length;
            TotalProbes++;

            if (_states[pos] == SlotState.Occupied)
            {
                if (_keys[pos] == key)
                {
                    _values[pos] = value;              // 已存在，覆盖
                    return;
                }
                continue;                              // 被别人占了，继续往后
            }

            if (_states[pos] == SlotState.Tombstone)
            {
                if (firstTombstone < 0) firstTombstone = pos;   // 记下第一个墓碑，可复用
                continue;
            }

            // 找到空位
            int target = firstTombstone >= 0 ? firstTombstone : pos;
            _keys[target] = key;
            _values[target] = value;
            _states[target] = SlotState.Occupied;
            _count++;
            return;
        }

        throw new InvalidOperationException("哈希表已满");
    }

    public bool TryGet(int key, out string? value)
    {
        int idx = BucketIndex(key);
        OpCount++;

        for (int step = 0; step < _keys.Length; step++)
        {
            int pos = (idx + step) % _keys.Length;
            TotalProbes++;

            if (_states[pos] == SlotState.Empty)
            {
                // 遇到真正的空位才能断定「不存在」；墓碑不能作为停止依据
                value = null;
                return false;
            }

            if (_states[pos] == SlotState.Occupied && _keys[pos] == key)
            {
                value = _values[pos];
                return true;
            }
        }

        value = null;
        return false;
    }

    public bool Remove(int key)
    {
        int idx = BucketIndex(key);

        for (int step = 0; step < _keys.Length; step++)
        {
            int pos = (idx + step) % _keys.Length;

            if (_states[pos] == SlotState.Empty) return false;

            if (_states[pos] == SlotState.Occupied && _keys[pos] == key)
            {
                _states[pos] = SlotState.Tombstone;    // 立墓碑，而不是清空
                _values[pos] = null!;
                _count--;
                return true;
            }
        }
        return false;
    }
}

注意这个实现用了三个并行数组（_keys、_values、_states）—— 这是为了教学清晰。真实实现（比如 .NET 的 Dictionary）会用一个结构体数组，因为那样对缓存更友好。

四、实测对比：一个颠覆直觉的结果

两种实现，同样的容量（8192）、同样的 5000 个元素、同样的随机键：

=== 链地址法 ===
  桶数量        : 8,192
  元素个数      : 4,989
  负载因子      : 0.609
  有元素的桶    : 3,766   空桶: 4,426
  最长链长度    : 6
  平均探测次数  : 0.298 次/操作

=== 开放寻址（线性探测） ===
  槽位数量      : 8,192
  元素个数      : 4,989
  负载因子      : 0.609
  已占用/空/墓碑: 4,989 / 3,203 / 0
  平均探测次数  : 1.783 次/操作

探测次数上，链地址法完胜（0.298 vs 1.783，少 6 倍）。

原因：链地址法的"探测"只统计同一条链内部的比较。如果桶是空的（4426 个空桶，占 54%），一次比较都不用做就直接返回"找不到"。而开放寻址必须至少检查一个槽位。

那性能呢？

  200,000 次插入 + 200,000 次查找：
    链地址法:     34.9 ms   平均探测 0.88 次/操作
    线性探测:     12.4 ms   平均探测 1.30 次/操作

线性探测快了 2.8 倍 —— 尽管它的探测次数几乎是链地址法的 1.5 倍。

为什么？

因为"探测次数"根本不是性能的决定因素，真正决定性能的是"内存访问模式"。

	链地址法	线性探测
每次探测访问什么	跳转到一个链表节点（堆上的独立对象）	访问数组里的下一个位置
内存位置	节点散落在堆上	就在当前槽位旁边
缓存行利用率	一次缓存未命中只能拿到 1 个元素	一条缓存行（64 字节）装下好几个槽位
CPU 预取	无法预取（地址要读出来才知道）	可以预取（下一个位置是算出来的）

这正是 3.1 节讲的缓存效应，在这里以最戏剧化的方式体现出来：

多做 50% 的工作，却快 2.8 倍。 因为那些"多做的探测"几乎不花钱（都在缓存里），而链地址法的每次跳转都可能是一次昂贵的内存访问。

这再次说明：大 O 记法分析不出这个差异，必须理解硬件。

这也是为什么 .NET 的 Dictionary 选择了开放寻址 —— 它更快。而"探测次数少"这个纸面上的优势，在真实硬件上并不值钱。

五、开放寻址的硬约束：负载因子必须小于 1

这是我写本节代码时踩的一个坑，值得单独讲。

我第一版给开放寻址表设了 1024 个槽位，然后插入 5000 个元素（照搬了链地址法的参数）。结果程序直接崩溃：

Unhandled exception. System.InvalidOperationException: 哈希表已满

为什么？

因为开放寻址把所有元素都存在同一个数组里。元素比槽位多，物理上就装不下了。

而链地址法的负载因子是 4.87（4989 / 1024）照样能跑 —— 只是链表变长、查找变慢而已。

这是两者在设计上的根本差别：

	链地址法	开放寻址
元素存在哪	数组存"桶"，元素挂在链表上	全部存在数组里
负载因子能超过 1 吗	能（空间可以"超卖"）	绝对不能
负载因子的实际上限	无硬上限，但越高越慢	通常控制在 0.5 ～ 0.75

实测验证这个约束：

  容量 64 的开放寻址表插入 100 个元素 -> 抛出异常: "哈希表已满"

工程上的含义：开放寻址法必须预留空位。这意味着它需要比链地址法更多的内存，还要有扩容机制（6.3 节的主题）。

但换来的是更快的实际性能 —— 这笔交易是划算的，所以主流实现（.NET、Python、Rust）都选了开放寻址。

为什么负载因子要控制在 0.5～0.75，而不是 0.95？

因为开放寻址的性能对负载因子极其敏感。负载因子接近 1 时，探测长度会急剧增长（后面 6.3 节会有实测曲线）。而留出空位让探测很快就能停下，是开放寻址能高效工作的前提。

六、墓碑：开放寻址的删除难题

开放寻址法有一个链地址法没有的麻烦：删除。

先看一个反例。 容量 8 的表，插入 1、9、17（假设它们都哈希到下标 1）：

  [0:_] [1:k1] [2:k9] [3:k17] [4:_] [5:_] [6:_] [7:_]

现在删除 9。如果直接把下标 2 清空：

  [0:_] [1:k1] [2:_] [3:k17] [4:_] [5:_] [6:_] [7:_]

然后查找 17 会怎样？

从下标 1 开始探测：k1 不是 17，继续
下标 2 是空的 → 探测逻辑会判定"17 不存在"，直接返回 false

但 17 明明就在下标 3！

根本原因：开放寻址的探测过程依赖"遇到空位就停止"这条规则。删除操作制造了一个假的"空位"，把探测链截断了。

正确做法：删除时留下"墓碑"（Tombstone） —— 一个特殊标记，表示"这里曾经有元素，后来被删了"。

  [0:_] [1:k1] [2:墓碑] [3:k17] [4:_] [5:_] [6:_] [7:_]

查找时的规则变成：

遇到	怎么办
空位（Empty）	停止，判定不存在
墓碑（Tombstone）	继续往后找
占用（Occupied）	比较键，不匹配就继续往后找

实测验证：

  插入 1、9、17 后（容量 8，它们都哈希到下标 1）：
    [0:_] [1:k1] [2:k9] [3:k17] [4:_] [5:_] [6:_] [7:_]

  删除 9 之后：
    [0:_] [1:k1] [2:墓碑] [3:k17] [4:_] [5:_] [6:_] [7:_]

  还能查到 1 吗？  True  (值 A)
  还能查到 17 吗？ True  (值 C)    <- 如果没有墓碑，这里会返回 False

墓碑带来两个新问题：

墓碑会累积。 反复插入删除后，数组里可能全是墓碑，导致探测越来越长。解决办法：在插入时复用第一个遇到的墓碑（代码里的 firstTombstone 就是干这个的）。
墓碑不能算作"空位"，但也不算"元素"。 所以负载因子的计算要考虑它们 —— 6.3 节会讲"什么时候该扩容"。

对比一下链地址法：删除就是"从链表里摘掉一个节点"，干净利落，没有任何后遗症（4.2 节的内容）。

这是链地址法相对开放寻址的唯一明显优势。 开放寻址更快、更省内存，但删除要小心处理墓碑。

七、两种方案的完整对比

	链地址法	开放寻址
元素存储	数组存桶 + 链表存元素	全部在数组里
缓存友好性	差（节点散落在堆上）	好（都在连续数组里）
实测性能	34.9 ms	12.4 ms（快 2.8 倍）
负载因子上限	无（可 > 1）	必须 < 1
内存开销	每个元素一个链表节点（约 32 字节）	只有数组本身，但要预留空位
删除	简单（摘链表节点）	麻烦（要处理墓碑）
探测次数	少（0.88）	多（1.30）
实现复杂度	简单	中等（墓碑、探测序列）
代表实现	Java 7 `HashMap`、C++ `unordered_map`	.NET `Dictionary`、Python `dict`

一句话总结： 链地址法赢在实现简单、删除干净；开放寻址赢在缓存友好、实际更快。

现代实现几乎都选了开放寻址，因为性能差距是实打实的，而墓碑问题可以用工程手段缓解。

八、练习

练习 8.1（推演）一个容量 7 的开放寻址哈希表（线性探测），哈希函数是 key % 7。依次插入：10, 22, 31, 4, 15 请画出每一步之后数组的状态，并计算每次插入的探测次数。

练习 6.2.2（计算）一个链地址法哈希表，容量 1000，存了 3000 个元素，哈希函数均匀。 (a) 平均链长是多少？ (b) 如果查找一个不存在的键，期望要比较多少次？ (c) 如果查找一个存在的键呢？

练习 6.2.3（判断）判断对错并说明理由： (a) 链地址法的探测次数比开放寻址少，所以链地址法更快。 (b) 开放寻址的负载因子超过 1 之后，查找会变慢。 (c) 开放寻址删除元素时，直接清空槽位是正确的做法。

练习 6.2.4（设计）你要实现一个缓存，键是字符串，值是大小约 1 KB 的对象。要求：

查找必须极快
缓存的元素数量大致稳定在 10 万左右
有淘汰机制，会频繁删除你会选链地址法还是开放寻址？说明理由。

练习 6.2.5（挑战·探测序列）线性探测的问题是"一次聚集"：连续的槽位被占满后，任何哈希到这片区域附近的键都要探测很久，而且会让这片区域越来越长。请设计一个改进的探测序列来缓解这个问题，并说明它的原理。（提示：不要每次都往后挪 1 格。）

九、练习答案

8.1

哈希函数 key % 7：

键	`key % 7`	探测过程	探测次数	数组状态
10	3	下标 3 是空的	1	`[_,_,_,10,_,_,_]`
22	1	下标 1 是空的	1	`[_,22,_,10,_,_,_]`
31	3	下标 3 被 10 占了 → 下标 4 空	2	`[_,22,_,10,31,_,_]`
4	4	下标 4 被 31 占了 → 下标 5 空	2	`[_,22,_,10,31,4,_]`
15	1	下标 1 被 22 占 → 2 空	2	`[_,22,15,10,31,4,_]`

总探测次数：8 次，平均 1.6 次。

注意最后一步：15 哈希到下标 1，但 1 被 22 占了。下标 2 是空的，所以 15 放在下标 2。

这个例子展示了"一次聚集"的雏形：31 和 4 分别哈希到 3 和 4，但因为前面被占，都要往后探测。如果继续插入哈希到 1~5 的键，探测长度会持续增长。

这就是为什么开放寻址的负载因子必须留有余量 —— 聚集会让探测长度非线性的增长。

6.2.2

容量 1000，元素 3000。负载因子 $\alpha = 3$。

(a) 平均链长 = 元素数 / 桶数 = $3000 / 1000 = 3$。

(b) 查找不存在的键：需要遍历完整条链才能确定不存在。期望比较次数 = 平均链长 = 3 次。

(c) 查找存在的键：假设目标等概率出现在链上的任何位置，平均要比较一半：

$$\frac{\alpha}{2} = 1.5 \text{ 次}$$

这就是链地址法的两条经典公式：

操作	期望比较次数
查找失败（不存在）	$\alpha$
查找成功（存在）	$1 + \frac{\alpha}{2}$

注意 (c) 里有个 "+1"：如果按"比较到目标为止"计数，成功查找是 $\frac{\alpha + 1}{2} + \frac{1}{2}$ 的细分问题 —— 不同教材的计数约定略有差异，但量级都是 $O(\alpha)$。

关键结论：链地址法的性能线性依赖于负载因子。负载因子从 1 涨到 3，查找代价也涨 3 倍 —— 这就是需要扩容的原因（6.3 节）。

6.2.3

(a) 错，本节实测就是反例。 链地址法探测 0.88 次，开放寻址 1.30 次，但开放寻址快 2.8 倍（12.4 ms vs 34.9 ms）。

原因：探测次数只统计"比较了几次"，但每次比较的代价完全不同。开放寻址的探测发生在连续数组里，大概率命中缓存；链地址法每次都要跳到堆上的链表节点，一次缓存未命中就够抵消好几次"省下来"的比较。
(b) 错，不是"变慢"而是"根本装不下"。 负载因子超过 1 意味着元素比槽位多，开放寻址在物理上无法存储，插入会抛异常（本节实测过）。

相比之下链地址法在负载因子为 5 时仍能正常工作，只是链变长。
(c) 错。 直接清空会截断探测链 —— 之后查找那些"因为冲突而被放到后面"的键时，会在这个假的空位处提前停止，误判为"不存在"（本节实测：17 查不到了）。

正确做法是留墓碑。

6.2.4

建议选开放寻址，但要针对"频繁删除"做专门处理。

理由：

查找必须极快 → 开放寻址的缓存友好性正好命中这个需求。每条记录 1 KB，本来就不太可能多个元素挤在同一条缓存行里，但"探测路径连续"仍然能省下大量内存跳转。
元素数量稳定在 10 万 → 可以预先按 20 万容量分配（负载因子控制在 0.5），完全避免扩容。
频繁删除 → 这是开放寻址的痛点，需要用墓碑 + 定期整理来应对。

具体设计：

容量：200,000（负载因子 0.5）
删除：留墓碑
整理：当「墓碑数 + 元素数」超过容量的 70% 时，触发一次全表重整（rehash）
      —— 重整时把墓碑全部清掉，元素重新插入，顺带让聚集被打散

每 1 KB 的条目，20 万容量就是 200 MB 左右 —— 要在内存预算里算清楚。

如果内存紧张，链地址法是更稳妥的选择：它没有"必须预留空位"的约束，负载因子 0.8 时只浪费 20% 的空间（开放寻址要浪费 50%）。代价是慢一些。

这道题没有唯一答案 —— 关键是你能说清"为什么在这个约束组合下选它"。

6.2.5

问题回顾：线性探测的"一次聚集"

线性探测的顺序是 +1, +2, +3, ...。一旦某片区域被连续占满，任何哈希到这片区域的键都会被追加到区域末尾，让区域继续变长 —— 越挤越挤。

改进方案 1：二次探测（Quadratic Probing）

探测序列改成 +1², +2², +3², ...，也就是 +1, +4, +9, +16, ...：

int pos = (idx + step * step) % capacity;

原理：探测的步长越来越大，不会形成连续的一整片，而是"跳跃式"地散布开。这样聚集效应被打破。

代价：探测序列不保证覆盖所有槽位（需要特殊的容量选择，比如容量取质数且负载因子 < 0.5 才能保证一定找到空位）。

改进方案 2：双重哈希（Double Hashing）

用第二个哈希函数来决定步长：

int stepSize = 1 + (key.GetHashCode() & 0x7FFFFFFF) % (capacity - 1);
int pos = (idx + step * stepSize) % capacity;

原理：不同的键用不同的步长，所以即使哈希到同一个位置，它们探测的路径也完全不同 —— 不会挤在同一条线上。分布最接近"理想随机"。

代价：每次探测都要多算一次哈希（不过第二个哈希通常可以很便宜）。

三种方案的对比：

方案	探测序列	聚集问题
线性探测	`+1, +2, +3, ...`	一次聚集（最严重）
二次探测	`+1, +4, +9, ...`	二次聚集（较轻）
双重哈希	`+h₂(k), +2h₂(k), ...`	几乎没有聚集

工程上的实际选择：很多实现（包括 .NET 的 Dictionary）仍然用线性探测。

为什么？ 因为线性探测的缓存友好性最好 —— 探测的位置紧挨着，都在同一条缓存行上。而二次探测和双重哈希跳来跳去，每次探测都可能是新的缓存未命中。

结果就是：双重哈希的"探测次数"更少，但每次探测更贵。在实际硬件上，线性探测往往还是赢 —— 这和本节主实验的结论（探测次数多反而更快）是同一个道理。

这是一个"理论最优 ≠ 实际最优"的典型案例。 面试时能答出"双重哈希分布更好"，工程上却要选线性探测 —— 能说清这个矛盾，才说明你真的理解。

十、常见错误

误区	纠正
认为"探测次数少 = 更快"	实测链地址法探测 0.88 次却比探测 1.30 次的开放寻址慢 2.8 倍。缓存局部性才是决定因素。
开放寻址的负载因子超过 1	会直接抛"哈希表已满"。开放寻址必须预留空位，通常控制在 0.5～0.75。
删除时直接清空槽位	会截断探测链，导致后面的键查不到。必须留墓碑。
把墓碑当空位用	墓碑会让探测变长。插入时应该复用第一个遇到的墓碑。
哈希值相同就直接返回	必须再比较一次键是否相等。哈希只是定位，`Equals` 才是判断。
用 `Math.Abs(hash) % n`	`Math.Abs(int.MinValue)` 会抛异常。用 `& 0x7FFFFFFF`。

十一、本节总结

冲突无法避免（鸽巢原理），所以哈希表的核心设计是"冲突了怎么办"。
链地址法：每个桶挂一条链表。实现简单、删除干净，但缓存不友好。
开放寻址：所有元素在同一个数组里，冲突就往后找空位。缓存友好，实测快 2.8 倍。
反直觉的实测：链地址法探测 0.88 次、开放寻址 1.30 次，但开放寻址快 2.8 倍 —— 因为探测代价的差异远大于探测次数的差异（3.1 节的缓存效应）。
开放寻址的硬约束：负载因子必须小于 1（实测容量 64 插 100 个元素直接抛异常）。链地址法没有这个限制。
墓碑：开放寻址删除时必须留墓碑，否则会截断探测链，导致后面的元素查不到（实测：没有墓碑就查不到 17）。
现代实现几乎都选开放寻址（.NET、Python、Rust），因为性能差距是实打实的。

下一节衔接：本节反复提到"负载因子" —— 链地址法的性能线性依赖于它，开放寻址更是必须控制在 0.75 以下。那么：负载因子到底是怎样影响性能的？什么时候该扩容？扩容时发生了什么？ 下一节用实测曲线把这个问题彻底讲清楚。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "6.2",
  "title": "冲突解决：链地址法与开放寻址",
  "covered": [
    "鸽巢原理与冲突的不可避免性",
    "链地址法完整实现（含符号位处理、延迟创建链表）",
    "开放寻址（线性探测）完整实现",
    "实测对比：探测 0.88 vs 1.30，但耗时 34.9ms vs 12.4ms（开放寻址快 2.8 倍）",
    "缓存局部性解释反直觉结果",
    "开放寻址的负载因子硬约束（实测抛「哈希表已满」异常）",
    "墓碑机制与探测链截断问题（实测有无墓碑的对比）",
    "两种方案的完整对比与代表实现",
    "二次探测与双重哈希的原理及「为什么工程上仍用线性探测」"
  ],
  "unresolved": [
    "负载因子对性能的定量影响留到 6.3",
    "扩容与再哈希留到 6.3",
    ".NET Dictionary 的具体实现留到 6.4",
    "红黑树（Java 8 桶树化）留到第 10 章后"
  ],
  "canonical_terms": {
    "链地址法": "每个桶挂一条链表来存放冲突元素",
    "开放寻址": "所有元素存在同一数组，冲突时按探测序列找下一个空槽",
    "线性探测": "开放寻址的一种，冲突时逐格往后找",
    "负载因子": "元素数 / 槽位数",
    "墓碑": "开放寻址删除时留下的特殊标记，用于保持探测链完整"
  },
  "symbols_units": {
    "α": "负载因子，元素数除以桶数"
  },
  "assumptions": [
    "读者已掌握 6.1 的哈希函数与 4.1 的链表",
    "读者理解 3.1 的缓存行概念"
  ],
  "word_count_actual": 3240,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch06/Sec62/",
    "两种实现的正确性均通过 5000 次查找校验（失败 0 次）",
    "墓碑对比实验与满表异常均为实测",
    "练习 6.2.1 的探测推演已手工验算（10/22/31/4/15 共 8 次探测）",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版给开放寻址表误用链地址法的容量参数（1024 槽位插 5000 元素），运行时抛「哈希表已满」；已修正容量并把这个约束本身写成一节教学内容"
  ],
  "next": "6.3 负载因子、扩容与再哈希"
}

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