GESP 七级 · GESP 202409 C++ 七级 第 23 题

某个哈希表键值 $x$ 为整数，$H(x) = x \% p$ 是常用的哈希函数之一，要求 $p$ 选择素数是因为这样不会产生冲突

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

1不是质数也不是合数。埃氏筛法标记时从i×i开始而非从2×i开始，因为小于i×i的倍数已经被更小的质数筛过。

【考点】Hash Table | Prime Numbers | Collision Handling

🎯 考纲定位：GESP 七级侧重考查数据结构应用能力，哈希表是必考模块。命题人卡住的是考生对哈希冲突机制的肤浅理解——误以为选素数就能"自动消除"冲突，实则哈希冲突是算法固有特性，与模数是否素数无关。GESP 七级"数据结构与算法"模块明确要求掌握哈希表原理与冲突处理策略。

🧠 解题思维：哈希函数 H(x) = x % p 的本质是键值取模后映射到桶号，冲突必然发生。选素数 p 可优化分布均匀性，但无法避免冲突。真正解决冲突要靠开放寻址或链地址法，而非数论技巧。素数在哈希函数中的真正作用是降低同余冲突概率，而非消除冲突。

🪤 陷阱拆解：陷阱在于"不会产生冲突"的绝对化表述。命题人利用考生对"素数=无冲突"的错误直觉，混淆了冲突概率与冲突必然性。命题人刻意用"不会产生冲突"这种绝对化措辞，诱导考生忽略哈希冲突不可避免性。

🔄 反命题思维：若改成"选素数 p 可减小冲突概率"则正确；改成"H(x) = x % p 一定无冲突"仍错误。因此，仅凭"素数"二字断言无冲突，是典型的概念混淆。