GESP 七级 · GESP 202312 C++ 七级 第 22 题

某个哈希表键值 $x$ 为整数，为其定义哈希函数 $H(x) = x \% p$，则 $p$ 选择素数时不会产生冲突。（ ）

别被‘素数’两个字骗了，冲突的本质是不同键值对模p同余，与p是否素数无关，直接举反例即可。

学生容易把‘哈希表设计选素数’这一经验法则机械迁移，认为选素数就能彻底消灭冲突。其实冲突只要求x1≠x2但x1≡x2(mod p)，无论p是素数还是合数，只要键值范围足够大，必然存在这样的对。命题人就是用‘不会产生冲突’这种绝对化表述挖坑，诱导死记硬背的学生选A。

【考点】哈希冲突的本质与素数模运算的误区

1. 考纲定位：GESP七级‘数据结构’模块，命题人卡住的是‘哈希表冲突’与‘素数模运算’两个知识点的机械记忆误区——学生容易把‘哈希表选素数’和‘哈希函数与素数取模’混为一谈，误以为选素数就能彻底消灭冲突。

2. 解题思维：哈希表冲突的本质是不同键值映射到同一槽位。H(x)=x%p 无论p是否为素数，只要存在x1≠x2满足x1≡x2(mod p)，就会冲突。素数只是让模运算的余数分布更均匀，但无法阻止冲突发生，因为冲突只与键值对模同余有关。

3. 陷阱拆解：命题人用‘不会产生冲突’这种绝对化表述，诱导学生把‘哈希表通常用素数模’这一经验法则错误迁移到本题。学生若只记住‘哈希表选素数’而不理解冲突产生的条件（键值对模同余），就会盲目选A。

4. 反命题思维：如果把p改成非素数，比如6，冲突依然会发生（如1和7仍同余1），只是分布更不均匀；若把题目改成‘存在某些键值对会冲突’，则命题为真。刷到类似题，先问：冲突的根本条件是什么，而不是被表面条件（如素数）迷惑。

5. 避坑：GESP七级常考‘哈希冲突不可避免’，学生易错选‘选素数可避免冲突’。记住：冲突只与键值范围与表长有关，与p是否为素数无关。即使p是素数，只要键值范围超过p，必然存在同余对。

6. 考频趋势：质数与合数考点在题库共考过52题，覆盖7个考试级别（2010-2026）；逐年分布：2010年1题、2019年1题、2020年1题、2023年7题、2024年21题、2025年13题、2026年6题、null年2题；分赛事：GESP五级29题、GESP七级7题、GESP八级7题、CSP入门级3题、GESP六级3题、CSP提高级2题、NOIP普及组初赛1题。本题属于质数与合数考点在哈希表中的具体应用，符合2023-2025年高频趋势。

7. 预测：基于给定数据与经验，未来GESP七级仍可能以‘哈希冲突与素数模’组合命题，但会减少绝对化表述，改为‘选素数可完全避免冲突’这类更隐蔽的陷阱。暂无足够依据预测具体年份或题型变化。