CSP-S 提高级 · CSP 2025 提高级第一轮 第 6 题

在一个大小为 13 的哈希表中，使用闭散列法的线性探查来解决冲突。哈希函数为 $H(\text{key}) = \text{key} \bmod 13$。依次插入关键字 $18, 26, 35, 9, 68, 74$。插入 $74$ 后，它最终被放置在哪个索引位置？

这道题考哈希表闭散列的线性探查。拿到题先算每个关键字的哈希值，再按插入顺序模拟冲突处理：遇到冲突就往后挪，直到找到空位或绕回表头。

最容易栽跟头的是忽略‘绕回表头’这一步。比如74算出来是9，9被占了就查10，10也被占了（之前插的9），学生容易以为查到底了或者随便选个位置，其实还得继续查11。另外别把模运算算错，74 mod 13 确实是9，不是11，别被选项D带偏了。

考点与概念

哈希表（闭散列/开放地址法）：当发生冲突时，不在表外新建节点，而是在表内找下一个空位。 线性探查：从冲突位置开始，依次检查 hash+1, hash+2, …，直到找到空位；若查完表尾还没空位，就绕回表头继续查。

命题视角

这类题喜欢给一串数字，让你一步步模拟插入过程。坑往往藏在‘看似有空位’的地方——比如9号位置被占了，10号也被占了，学生容易以为查到底了或者随便选个位置，其实还得继续查11。另外别把模运算算错，74 mod 13 确实是9，不是11，别被选项D带偏了。

逐步推导

表大小13，索引0~12，哈希函数 H(key) = key mod 13。

1. 插入18：18 mod 13 = 5 → 位置5空 → 放5 2. 插入26：26 mod 13 = 0 → 位置0空 → 放0 3. 插入35：35 mod 13 = 9 → 位置9空 → 放9 4. 插入9：9 mod 13 = 9，冲突！→ 检查10 → 空 → 放10 5. 插入68：68 mod 13 = 3 → 位置3空 → 放3 6. 插入74：74 mod 13 = 9，冲突！→ 检查10 → 冲突（被9占了）→ 检查11 → 空 → 放11

避坑指南

线性探查找空位要检查 hash+1, hash+2,… 直到表尾，必要时绕回到表头。本题中74的哈希值是9，9和10都被占，必须继续往后查到11才是空位。别把74 mod 13算成11，也别以为查到10就停。另外注意选项D是11，容易误选，但正确答案确实是11，说明绕回表头这一步没做错。

考频与趋势

特殊结构（闭散列/线性探查）在题库共考过2题，覆盖1个考试级别（2024-2025）；逐年分布：2024年1题、2025年1题；分赛事：CSP 提高级2题。 同余与模运算在题库共考过28题，覆盖6个考试级别（2020-2026）；逐年分布：2020年2题、2021年1题、2022年1题、2023年2题、2024年6题、2025年8题、2026年7题、null年1题；分赛事：GESP 五级9题、GESP 八级7题、CSP 提高级5题、CSP 入门级3题、GESP 七级2题、GESP 六级2题。

预测

基于上述数据，同余与模运算在2025年考得最多（8题），且CSP 提高级近年持续有题，未来仍会高频出现。特殊结构题目前两年各1题，分布较均匀，暂无足够依据预测未来会突然增多或减少，但考虑到哈希表是数据结构核心，大概率会保持每年1-2题的节奏。因此，线性探查这类题在未来几年仍值得重点复习，尤其是绕回表头这一细节，命题人很可能继续用它挖坑。