给我简单讲解：哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）

在 CSP-J/S 初赛和各省名校自招中，“哈希冲突（Hash Collision）的开地址法（线性探测与二次探测）” 是每年必考、且只要考就属于 100% 拿分的送分题。

这类题目不需要写代码，关键在于搞懂探测公式，并在草稿纸上模拟画表格。

---

一、 核心背景：什么是哈希冲突？

• 假设我们有一个长度为 $M$ 的哈希表（数组下标 $0 \sim M-1$）。
• 散列函数通常是模运算：$H(key) = key \bmod M$。
• 冲突：两个不同的数算出来的下标一样（比如 $M=11$，$key_1=1$ 和 $key_2=12$，因为 $1 \bmod 11 = 12 \bmod 11 = 1$，它们都想挤进下标 1 的位置）。
• 开地址法（Open Addressing）：既然原本的家被占了，就按照某种“既定规则”在数组里找下一个空位置。

---

二、 线性探测法（Linear Probing）——“挨个往后挪”

1. 核心公式

如果算出来的初始位置 $H_0 = H(key)$ 已经有人了，就依次往后看：

$$H_i = (H(key) + i) \bmod M \quad (i = 1, 2, 3, \dots) $$

通俗说就是：+1，+2，+3，+4……挨个往后找，走到数组末尾就绕回开头（取模）。

2. 手推实战演练

题目：散列表长 $M = 11$，$H(key) = key \bmod 11$。采用线性探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

我们画一个下标 $0 \sim 10$ 的表格：

1. 插入 12：$12 \bmod 11 = 1$。下标 1 是空的，直接放入：
   • 表格：位置 1: 12
2. 插入 23：$23 \bmod 11 = 1$。发现下标 1 已经被 12 占了（冲突）！
   • 启动线性探测：试探 $(1 + 1) \bmod 11 = 2$。
   • 下标 2 是空的，放入：
   • 表格：位置 1: 12，位置 2: 23
3. 插入 34：$34 \bmod 11 = 1$。下标 1 冲突！
   • 试探 $(1 + 1) \bmod 11 = 2$，也被 23 占了，继续冲突！
   • 试探 $(1 + 2) \bmod 11 = 3$，下标 3 是空的，成功放入！
   • 结果：34 最终存放在下标 3。

• 优缺点常考点：容易产生**“聚集/堆积（Clustering）”**现象——连续一长串都被占满，后面的数冲突越来越频繁。

---

三、 二次探测法（Quadratic Probing）——“跳跃着找”

为了解决线性探测“容易扎堆”的问题，二次探测改成了步长平方跳跃（有的教材也叫平方法）。

1. 核心公式

如果 $H(key)$ 冲突，探测序列为：

$$H_i = (H(key) \pm i^2) \bmod M \quad (i = 1, 2, 3, \dots) $$

即偏移量依次为：

$$+1^2, \ -1^2, \ +2^2, \ -2^2, \ +3^2, \ -3^2, \dots $$

也就是：

$$+1, \ -1, \ +4, \ -4, \ +9, \ -9, \dots$$

⚠️ 草稿纸算负数取模秘诀（极其重要，考场避坑点）： 如果算出来是负数，直接加上表长 $M$ 即可！ 例如：$(0 - 1) \bmod 11 = -1 \rightarrow -1 + 11 = 10$。

2. 手推实战演练

题目：散列表长 $M = 11$，$H(key) = key \bmod 11$。采用二次探测法，依次插入 {12, 23, 34}。求 34 最终落在哪个位置？

1. 插入 12：$12 \bmod 11 = 1$，下标 1 空闲，存入 1。
2. 插入 23：$23 \bmod 11 = 1$，冲突！
   • 探测第一步（$+1^2$）：$(1 + 1) \bmod 11 = 2$，下标 2 空闲，存入 2。
3. 插入 34：$34 \bmod 11 = 1$，冲突！
   • 探测第一步（$+1^2$）：$(1 + 1) \bmod 11 = 2$，位置 2 已被 23 占领，继续冲突！
   • 探测第二步（$-1^2$）：$(1 - 1) \bmod 11 = 0$！
   • 下标 0 是空的，成功放入！
   • 结果：34 最终存放在下标 0（注意与线性探测得到的结果不同！）。

---

四、 考场应试“三步做题法”

初赛或自招考场上遇到这类选择题，不要在脑子里凭空想，按以下 3 步做：

1. 画尺子：草稿纸画一条横线，标出下标 $0 \sim M-1$。
2. 算模数：把每一个给出的数先模上 $M$，写在草稿纸上。
3. 按顺序落子：
   • 没冲突直接填进去；
   • 遇到冲突看清题干：
     • 若是线性：+1, +2, +3... 顺延往后走；
     • 若是二次：先试 +1，不行试 -1，再不行试 +4，再不行试 -4……（负数直接加模数 $M$）。