CSP-S 2020 第一轮 第5题：将（2，7，10，18）分别存储到某个地址区间为0~10 的哈希表中，如果

题目

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

选项

• A. $x^2 \bmod{11}$
• B. $2x \bmod{11}$
• C. $x \bmod{11}$
• D. $\lfloor \dfrac{x}{2} \rfloor \bmod{11}$，其中$\lfloor \dfrac{x}{2} \rfloor$ 表示 $\dfrac{x}{2}$ 下取整

答案

D

题解

答案是 D。

冲突指的是：两个不同的数，经过哈希函数计算后，得到相同的存储地址。因此，把四个数分别代入各选项，检查结果是否重复即可。

例如，A 中 $7^2=49$，除以 $11$ 余 $5$；$18^2=324$，除以 $11$ 也余 $5$，所以 $7$ 和 $18$ 会冲突。

D 得到的地址为 $1、3、5、9$，互不相同，且都在 $0\sim10$ 内，因此不会产生冲突。