CSP-S 提高级 · CSP 2020 提高级第一轮 第 5 题

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

这题核心就是暴力枚举，把四个数分别套进四个公式算一算，看哪组算出来的结果互不相同。

最容易栽跟头的就是看错下取整符号，把 floor(x/2) 当成 x/2 直接算，或者算完忘了再对 11 取模。另外，题目问的是‘不会产生冲突’，很多学生会惯性思维去验证其他选项，结果反而在 A、B、C 里纠结半天，忽略了 D 才是唯一解。还有，模运算的结果范围是 0 到 10，别算成 1 到 11。

这道题考查的是哈希表的基本原理，特别是哈希冲突的产生与避免。简单来说，哈希函数就是把数据映射到地址的‘翻译官’，如果两个不同的数据被翻译成同一个地址，就叫冲突。这题地址区间是 0 到 10，一共 11 个坑，模数就是 11。命题人想考察的不是死记硬背，而是让你亲手把四个数代入四个不同的‘翻译规则’里跑一遍，看哪个规则能把它们全部分开。拿到题先想什么？别急着列公式，先明确目标：找出一组哈希值，使得 2、7、10、18 对应的结果互不相等。从哪入手？直接代入计算，这是最稳妥的。具体怎么算？我们一个个来。A 选项是平方取模，2 平方是 4，7 平方是 49 除以 11 余 5，10 平方是 100 除以 11 余 1，18 平方是 324 除以 11 余 5，哎，7 和 18 都撞车了，A 不行。B 选项是 2x 取模，2 变 4，7 变 14 余 3，10 变 20 余 9，18 变 36 余 3，7 和 18 又撞车了，B 也不行。C 选项最简单，就是直接取模，2 余 2，7 余 7，10 余 10，18 余 7，7 和 18 还是撞车，C 也排除。最后看 D 选项，下取整后再取模。2 除以 2 下取整是 1，1 余 1；7 除以 2 下取整是 3，3 余 3；10 除以 2 下取整是 5，5 余 5；18 除以 2 下取整是 9，9 余 9。这四个结果 1、3、5、9 全都不同，完美避开了所有冲突。避坑方面，一定要看清 floor 符号，别把它当成普通除法，也别漏掉最后的 mod 11。考频趋势上，哈希冲突这类概念题在 CSP 提高级里虽然不算高频，但每年必现，尤其是这种带简单数论运算的，2020 年这道题就是典型代表。预测未来，只要模数给得合适，这类‘代入排除法’的哈希题还可能会以不同变体出现，比如换个数集或者换模数，解题思路不变，还是老老实实算一遍。