GESP 八级 · GESP 202412 C++ 八级 第 22 题

使用哈希函数 $f(x) = x \bmod p$ 建立键值为 int 类型的哈希表，只要 $p$ 取小于等于哈希表大小的素数，可保证不发生碰撞。

质数判定优化：只需检查2到√n。偶数除了2都不是质数。判断素数的时间复杂度O(√n)。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】哈希冲突处理｜哈希函数设计｜哈希表大小选择

命题人故意将"素数模"包装成"无冲突保证"，这是典型的绝对化陷阱。哈希冲突的必然性源于抽屉原理：当哈希表大小有限时，不同键值必然映射到同一位置，素数仅能改善分布均匀性。

解题关键在理解"碰撞"的数学定义：f(x1)=f(x2)且x1≠x2。即使p为素数，只要哈希表大小p≤表长，不同整数x1和x1+p必然映射到同一槽位。例如p=7、表长=10时，7和14碰撞。

陷阱拆解：A选项错误源于混淆"减少碰撞概率"与"消除碰撞"。素数模确实能让哈希值更均匀，但均匀≠无冲突。命题人利用考生对素数特性的过度信任，用数学上严谨的表述包装常识性错误。

反命题思维：若改为"使用哈希函数f(x)=x mod p（p为素数且p≤表长）可减少哈希冲突"，则命题成立。哈希表设计核心矛盾是"有限存储vs无限键值"，素数只是优化手段而非终极解。