考研笔记

处理冲突的方法

任何设计出来的散列函数都不可能绝对地避免冲突。 为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个「空」的 Hash 地址。

方法分两大类：开放定址法（在同一张表里另找位置）和拉链法（在表外挂链表）。这一节是 7.5 里手算量最大的一节——7.5.4 的两个 全靠这里的探测序列算出来。

机制

开放定址法

所谓开放定址法，是指表中可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为式中 为散列函数；； 表示散列表表长； 为增量序列。

用 表示处理冲突中第 次探测得到的散列地址，假设得到的另一个散列地址 仍然发生冲突，只得继续求下一个地址 ，以此类推，直到 不发生冲突为止，则 为关键字在表中的地址。

取定某一增量序列后，对应的处理方法就是确定的。 通常有以下 4 种取法：

1. 线性探测法，也称线性探测再散列。特点是：冲突发生时，顺序查看表中下一个单元（探测到表尾地址 时，下一个探测地址是表首地址 0），直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。

它的病是「堆积」：线性探测法可能使第 个散列地址的同义词存入第 个散列地址，这样本应存入第 个散列地址的元素就争夺第 个散列地址的元素的地址……从而造成大量元素在相邻的散列地址上聚集（或堆积）起来，大大降低了查找效率。

边界辨析：

堆积是「非同义词之间」的争夺造成的（2014 年直接考过）。 同义词本来就要抢同一个地址，那是冲突的定义； 堆积特指本来互不相干的关键字被挤到一起、互相延长探测路径。 所以「堆积由同义词冲突引起」是错的，正确答案是非同义词之间发生冲突。

2. 平方探测法，也称二次探测法。散列表长度 必须是一个可以表示成 的素数。

平方探测法是一种处理冲突的较好方法，可以避免出现「堆积」问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

3. 双散列法

需要使用两个散列函数：当通过第一个散列函数 得到的地址发生冲突时，则利用第二个散列函数 计算该关键字的地址增量。初始探测位置 ； 是冲突的次数，初始为 0。

补充：双散列法一定能探测到所有位置吗？

不一定，关键看第二个散列函数给出的步长与表长是否互素。 对某个关键字，记 ，它的探测序列就是从 出发，每次加 ，再对 取模。

能探测到的不同位置数能遍历全表

为什么？ 走了 步后回到起点，等价于 。满足它的最小正整数是 ；一旦回到起点，后面就只会重复。

例如（补充示例），、、 时，探测地址为 ，只能到 3 个位置，即使 都空着也探测不到。若改成 ，则 ，能走遍全表。

常用设计：表长 取素数，并保证 。 这样步长自然与 互素。例如，对非负整数关键字，可取

截图中的写法还要补一个条件

截图给出 。即使 是素数，也只有在 时，才能保证步长与 互素。 若 、，就得到 ，每次加 再模 ，永远停在初始地址。所以不能只记“表长是素数”，还要检查步长模 不能为 。

4. 伪随机序列法： 伪随机数序列。

边界辨析：

开放定址法不能随便物理删除元素。 教材的注意框原文： 「采用开放定址法时，不能随便物理删除表中已有元素，否则会截断其他同义词元素的查找路径， 删除元素时可以做一个删除标记，进行逻辑删除。 但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用。」 这是 2023 年的命题追踪，两句都要能答：为什么不能物理删（截断查找路径）， 逻辑删除的副作用是什么（假满）。

拉链法（链接法，chaining）

对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。假设散列地址为 的同义词链表的头指针存放在散列表的第 个单元中，因而查找、插入和删除操作主要在同义词链中进行。

拉链法适用于经常进行插入和删除的情况。

以关键字序列 、散列函数 为例（教材图 7.33）：

flowchart LR
    T0["0"] --> N0["∧"]
    T1["1"] --> A1["01"] --> A2["14"] --> A3["27"] --> A4["79 ∧"]
    T2["2"] --> N2["∧"]
    T3["3"] --> B1["55"] --> B2["68 ∧"]
    T4["4"] --> N4["∧"]
    T5["5"] --> N5["∧"]
    T6["6"] --> C1["19"] --> C2["84 ∧"]
    T7["7"] --> D1["20 ∧"]
    T8["8"] --> N8["∧"]
    T9["9"] --> N9["∧"]
    T10["10"] --> E1["10"] --> E2["23 ∧"]
    T11["11"] --> F1["11 ∧"]
    T12["12"] --> N12["∧"]

    classDef slot fill:#c8e6c9,stroke:#1b5e20,stroke-width:2px
    classDef node fill:#e3f2fd,stroke:#1565c0
    classDef nil fill:#eeeeee,stroke:#9e9e9e
    class T0,T1,T2,T3,T4,T5,T6,T7,T8,T9,T10,T11,T12 slot
    class A1,A2,A3,A4,B1,B2,C1,C2,D1,E1,E2,F1 node
    class N0,N2,N4,N5,N8,N9,N12 nil

注意表长只到 12：拉链法的散列表长度就等于散列函数的值域大小，不需要留空位，这与开放定址法不同。

边界辨析：

链内的次序取决于插入策略，题目必须交代。 上图 1 号槽里是 01→14→27→79， 而插入顺序是 14, 01, 27, 79——既不是插入顺序也不是纯头插。 教材 7.5.5 的选择题里出现过「若限定在链首插入」这样的限定语，说明这是需要被指明的条件。 链内次序直接改变 成功：按图中次序算出的 成功， 换成头插法则各链倒序，数值会变。做题时先看题目怎么规定，没规定就按图/按顺序插入并写明假设。

手算模板

开放定址法建表（以线性探测为例）：

  1. 圈出 （散列函数的模）和 （表长）。探测公式里用的是 。
  2. 逐个关键字：，比较次数从 1 开始计。
  3. 该位置非空且不等 → 比较次数 ，地址换成 。
  4. 直到落到空位，写入。
  5. 把每个关键字的比较次数记成一行——这就是 7.5.4 的分子。

平方探测的顺序不要写错：，即偏移量依次是 ，正负交替，不是 一路加上去。若算出的地址为负，同样对 取模到 。

双散列法：， 从 0 开始， 就是初始位置。

边界

说法判断说明
「堆积由同义词冲突引起」❌由非同义词之间的冲突引起（2014）
「线性探测到表尾就失败」❌回绕到表首地址 0，因为公式里有
「线性探测时同义词一定相邻」❌中间可能夹着非同义词
「平方探测能探测到所有单元」❌不能，但至少能探测到一半单元
「平方探测的表长可以任意」❌ 必须是可表示成 的素数
「平方探测的增量是 」❌是 ，正负交替
「双散列法只用一个散列函数」❌两个，第二个算的是增量
「双散列法一定能探测到所有单元」❌对该关键字，步长与表长互素才行；不同探测位置数为
「双散列的表长是素数，就一定能遍历全表」❌还要保证步长模 不为
「开放定址法可以直接删除元素」❌会截断同义词的查找路径，须做逻辑删除
「逻辑删除没有副作用」❌多次删除后表面很满、实际有许多位置未利用（2023）
「拉链法会引起聚集现象」❌拉链法不会堆积，同义词各走各的链
「拉链法的表长要大于关键字个数」❌表长 值域大小即可，链表可以任意长
「拉链法适合频繁插入删除」✅教材原话，与开放定址法的「不能物理删除」正相反

口径差异：

std::unordered_map / Java HashMap 用的都是拉链法（Java 8 起链表过长会转红黑树）， 所以有工程或算竞背景的人对「开放定址」往往很陌生， 而 408 的手算题几乎全考开放定址法（尤其线性探测）——因为它能出成填表题。 平方探测的 素数、双散列的 从 0 起算，这些细节在工程里完全用不到，考试却直接问。

对照速查

方法增量 会不会堆积特殊约束
线性探测会探测到表尾回绕到 0
平方探测，不会 须为 型素数；只能探测一半单元
双散列不会需两个散列函数， 从 0 起；步长与表长互素才能遍历全表
伪随机序列伪随机数序列不会—
开放定址法拉链法
冲突元素放哪表内另找空位表外同义词链
表长要求，必须留空位 值域大小即可
堆积线性探测会不会
删除只能逻辑删除可直接从链上摘除
适用表相对静态经常插入和删除

考点

  • 开放定址法的递推公式及四种增量序列。
  • 堆积由非同义词冲突引起（2014）。
  • 平方探测的三个约束：增量正负交替、 为 型素数、只能探测一半单元。
  • 双散列法的 从 0 起算；能否遍历全表看步长与表长是否互素。
  • 开放定址法不能物理删除 + 逻辑删除的副作用（2023）。
  • 拉链法不会堆积、适合频繁增删。
  • 手算填表——本节的主要工作量。

链接

反向链接