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

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

这题就是模拟哈希表填充过程，核心在于先算平方取模定位，遇到冲突就顺着往后找空位，切记要按 0 到 7 的顺序一步步填，不能跳步漏算。

学生最容易在计算平方取模时出错，比如把 6 的平方算成 36 后忘记除以 11 取余，或者把 7 的平方算错；其次是在模拟线性探测时，遇到冲突后没有严格往后找第一个空位，而是凭感觉填了后面某个位置，或者在探测过程中漏掉了已经被占用的格子；最后还有人会忽略题目中“到 10 后从 0 开始”的循环规则，导致后续元素的地址判断错误。

本题考查哈希表的基本操作，特别是哈希函数计算与冲突解决策略——线性探测法。哈希函数 h(x)=x² mod 11 将关键字映射到 0~10 的地址区间，当发生冲突时，系统会依次往后查找下一个可用的空地址，直到找到为止。理解这一机制是解题的关键。命题人喜欢用这种需要手动模拟的过程来考察学生的细心程度和逻辑推演能力，往往在中间某个元素就会埋下陷阱，比如某个平方数取模后恰好落入已被占用的区域，从而引发一连串的探测。拿到题后，正确的思考路径是：先列出 0 到 7 的哈希值，然后按照插入顺序，逐个判断目标地址是否空闲，若空闲则直接存入，若冲突则从 h(x)+1 开始向后扫描，直到找到第一个空位。计算时务必准确，模 11 的余数要细心核对。避坑方面，特别注意 6 和 7 的处理：6²=36，36 mod 11=3，而地址 3 已被元素 5 占用，于是从 4 开始探测，4 被 2 占用，5 被 4 占用，6 是空的，所以 6 存入 6；接着处理 7，7²=49，49 mod 11=5，地址 5 已被元素 4 占用，从 6 开始探测，6 已被元素 6 占用，继续往后，7 是空的，因此 7 存入 7。这里很容易因为前面的探测过程导致后面元素的位置判断失误，务必严格按顺序模拟。从历年考频看，哈希表相关题目在数据管理与数据结构两板块均有出现，其中数据结构部分考得更为频繁，2009、2019、2020、2021 年均有涉及，2021 年更是出现了两道，说明这类考察线性探测或二次探测的题目是近年来的热点，命题趋势明显倾向于在 CSP 提高级和 NOIP 提高组中反复打磨这一知识点。基于此，预测未来考试中仍会高频出现类似的哈希表模拟题，可能会在哈希函数设计上稍作变化，或者在探测策略上引入更复杂的场景，但核心思路不变。因此，面对此类题目，保持耐心、严谨地一步步模拟，是拿到分数的不二法门。