NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 9 题

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

这题别急着套公式，先算出四个数开根号下取整后的值，再分别代入四个选项看有没有撞车。D 选项把数值拉得足够开，天然避开了冲突，其他几个要么直接取模，要么平方后模数太小，很容易撞。

最容易栽跟头的就是忽略下取整符号，直接把√17当成根号17（约4.12）去模，或者误以为√10=3.16要进位。还有同学看到平方和倍数函数就下意识觉得‘肯定有冲突’，其实只要算对了下取整，D 就是完美的无冲突方案。

这题考什么

哈希表基础：哈希函数设计、冲突判断。

概念人话版

哈希函数就是把数据扔进地址区间，地址区间固定为 0~10，一共 11 个坑。冲突就是两个不同的数扔进去，掉进同一个坑里。