GESP 七级 · GESP 202512 C++ 七级 第 3 题

现有一个地址区间为 $0 \sim 10$ 的哈希表，当出现冲突情况，会往后找第一个空的地址存储（到 $10$ 冲突了就从 $0$ 开始往后），现在要依次存储 $(1,3,5,7,9)$，哈希函数为 $h(x) = (x^2 + x) \bmod 11$。其中 $9$ 存储在哈希表哪个地址中（ ）。

函数指针：bool (*Fx)(int) 声明一个指向"接收int返回bool"的函数的指针，可作为参数传递给其他函数（回调机制）。

函数指针和普通指针不同，函数指针指向的是代码段中的函数入口地址。声明格式：返回类型 (*指针名)(参数列表)。

【考点】哈希表冲突处理｜线性探测｜哈希函数计算

1. 🎯 考纲定位

• GESP 七级"数据结构与算法"模块，明确考查哈希表冲突处理机制。命题人用这道题卡住的是多数学生只会算哈希值、忽略冲突探测过程的弱点。

2. 🧠 解题思维

• 先算每个键的哈希：h(1)=2, h(3)=1, h(5)=8, h(7)=1, h(9)=2。
• 依次插入：1→2；3→1；5→8；7 落在 1 冲突，线性探测到 3；9 落在 2 冲突，继续探测到 3 已占，再探测到 4，恰好是第一个空位。
• 通法：对哈希表线性探测，就是"计算哈希→检查是否占用→若占用则向后逐项探测直到找到空位（到末尾绕回）"。

3. 🪤 陷阱拆解

• 选项 A 是只算 h(9) 得到的 2，选项 C 是 7 探测到的 3，选项 B 是 3 探测到的 1。命题人特意让 9 的哈希和 1 相同，让 7 的哈希也和 1 相同，从而制造连环冲突。
• 最阴险的细节是"到 10 冲突了就从 0 开始往后"的绕回规则，很多学生看到 9 落在 2 就以为冲突直接跳到 3，却忘了 3 已被 7 占用，必须继续探测到 4。
• 只背结论不模拟过程，必掉坑。

4. 🔄 反命题思维

• 若把哈希函数改为 h(x) = (x^2+2x) mod 11，则 9 的哈希会变为 3，答案变成 C。
• 若把探测方式改成二次探测，9 可能停在 5。
• 刷到这类题先问：命题人想考我哈希值、探测顺序还是绕回规则？