CSP-S 提高级 · CSP 2022 提高级第一轮 第 12 题

给定地址区间为 0~9 的哈希表，哈希函数为 h(x) = x % 10，采用线性探查的冲突解决策略（对于出现冲突情况，会往后探查第一个空的地址存储；若地址 9 冲突了则从地址 0 重新开始探查）。哈希表初始为空表，依次存储(71, 23, 73, 99, 44, 79, 89)后，请问 89 存储在哈希表哪个地址中。（ ）

别急着算，先画个 0-9 的格子。把前六个数按顺序插进去，每插一个就更新一下表的状态。看到 89 冲突了，顺着线性探查一步步往后挪，直到碰到第一个空位停下，那个位置就是答案。

最大的坑是模拟不全：89 的哈希值是 9，地址 9 被 99 占了，接着查 0，0 被 79 占了，再查 1，1 被 71 占了，很多同学就在这儿停了，以为答案是 1 或 0，忘了还得继续往后查。另外还有两个数容易看错顺序：73 先插，占 3 冲突后挪到 4；44 后插，4 已经被 73 占了，所以 44 会去 5。如果把这俩位置记反，后面 89 的探查路径就会全乱。

这道题考查的是哈希表的线性探查法（Linear Probing）解决冲突的机制，核心就是模拟插入过程。

首先明确规则：哈希函数 h(x) = x % 10，地址空间 0~9。当 target 地址被占时，依次检查 (target+1)%10、(target+2)%10……直到找到空位；若绕一圈回到原地址仍无空位，则表满。

我们按顺序插入这七个数，并在纸上维护一个 10 格的数组，每步都更新状态，这是最稳妥的“心法”。

1. 插入 71：71%10=1，地址 1 为空，直接存入 71。 2. 插入 23：23%10=3，地址 3 为空，直接存入 23。 3. 插入 73：73%10=3，地址 3 已被 23 占，线性探查下一个地址 4，4 为空，存入 73。 4. 插入 99：99%10=9，地址 9 为空，直接存入 99。 5. 插入 44：44%10=4，地址 4 已被 73 占，探查下一个地址 5，5 为空，存入 44。 6. 插入 79：79%10=9，地址 9 已被 99 占，探查下一个地址 0，0 为空，存入 79。 7. 插入 89：89%10=9，地址 9 已被 99 占；继续探查 0，0 已被 79 占；继续探查 1，1 已被 71 占；继续探查 2，2 是空的！

因此，89 最终存储在地址 2 中，对应选项 D。

易错点复盘：

• 89 的探查路径必须完整走完：9→0→1→2。很多同学只查到 0 或 1 就停，或者误以为 0 是空的，导致选错。
• 73 和 44 的位置容易混淆：73 先插，占 4；44 后插，4 已被占，所以 44 去 5。如果顺序记反，后面 89 的探查就会出错。
• 线性探查是“往后挪 1 格”，不是随机跳，也不是回退，必须严格按 (h(x)+i)%10 的顺序检查。

考频与趋势：同余与模运算在题库中已考过 28 题，覆盖 6 个级别，近年热度持续攀升：2020 年 2 题、2021 年 1 题、2022 年 1 题、2023 年 2 题、2024 年 6 题、2025 年 8 题、2026 年 7 题，GESP 五级、八级、CSP 提高级等均有涉及。哈希表线性探查作为典型应用，未来仍可能以单选题形式出现，重点考察冲突链的完整模拟或查询路径判断。

暂无足够依据预测具体年份考题，但建议强化“画图模拟”这一基本功，这是应对此类题最直接、最不易出错的方法。