NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 5 题

将 $\{2, 6, 10, 17\}$ 分别存储到某个地址区间为 $0\sim 10$ 的哈希表中，如果哈希函数 $h(x) =$ （ ），将不会产生冲突，其中 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

拿到题先别急着套公式，把四个数一个个代入每个选项算算余数，看哪个能让它们都跑到不同的格子里，这就是检验哈希函数是否冲突的硬道理。

很多同学会被模数 11 迷惑，觉得只要结果小于 11 就没事，或者草草看一眼平方、乘 2 就觉得能分散，其实冲突就在那几个数字的余数撞车里。比如用 x mod 11，10 和 17 都撞在 6 上；用平方再模 11，2 和 10 又撞在 4 上。避坑的关键是老老实实算出每个数映射后的具体地址，再两两比对有没有重复，千万别凭直觉跳过计算步骤。

这道题考查哈希函数的基本性质与冲突判断。哈希函数 h(x) 的作用是把不同关键字映射到地址区间，如果两个不同关键字映射到同一个地址，就叫冲突。这道题给的地址区间是 0~10，也就是模 11 的空间，四个数{2,6,10,17}要分别映射到不同的地址才算无冲突。命题人喜欢在这种单选题里挖坑，就是让你别只看函数形式，真得把每个数代入算出余数再比对，很多选项乍一看挺合理，一算就露馅。思考心法很简单：拿到题先代入四个数，逐个算出 h(x) 的结果，然后把结果列出来看有没有重复。具体计算过程：选项 A 是 x mod 11，代入得 2→2，6→6，10→10，17→6，10 和 17 撞车，冲突；选项 B 是 x² mod 11，2²=4→4，6²=36→3，10²=100→1，17²=289→3，6 和 17 撞车，冲突；选项 C 是 2x mod 11，2→4，6→12→1，10→20→9，17→34→1，6 和 17 撞车，冲突；选项 D 是 floor(√x) mod 11，√2≈1.414 下取整得 1，√6≈2.449 下取整得 2，√10≈3.162 下取整得 3，√17≈4.123 下取整得 4，四个结果分别是 1,2,3,4，互不相同，完全没有冲突。所以正确答案是 D。这道题的考点就是哈希函数构造与冲突检测，属于 STL 容器基础里的哈希表实现原理，也是竞赛里高频出现的坑点。从考频数据看，STL 容器基础在题库里共考过 127 题，覆盖 8 个考试级别，逐年分布：2011 年 1 题、2013 年 2 题、2023 年 14 题、2024 年 22 题、2025 年 47 题、2026 年 37 题、null 年 4 题；分赛事：GESP 五级 70 题、GESP 六级 28 题、GESP 八级 15 题、GESP 七级 8 题、NOIP 普及组 初赛 2 题、GESP 四级 2 题、NOIP 提高组 初赛 1 题、CSP 入门级 1 题，说明哈希相关题目近几年热度持续上升，尤其是 GESP 五级占比最高。基于这个趋势，未来哈希函数构造、冲突解决策略（如线性探测、二次探测）可能会以更复杂的形式出现，比如给一个动态增长的键集让你判断某种哈希函数是否始终无冲突，或者结合其他数据结构考察哈希表的扩容机制。暂无足够依据预测具体题型，但可以肯定的是，扎实掌握哈希函数的代入计算与冲突判断是应对这类题目的基本功，一定要避免只看不算的惯性思维。