NOIP 普及 2013 第一轮 第 5 题：选择不产生冲突的哈希函数

题目

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

选项

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

答案

D

题解

考点定位

本题考「无冲突哈希函数」,对应大纲 3.3.4 哈希表（难度【2】）。

解题过程

对 {2,6,10,17} 检验 ⌊√x⌋ mod 11：⌊√2⌋=1、⌊√6⌋=2、⌊√10⌋=3、⌊√17⌋=4——两两不同 ✓。

（x mod 11：2,6,10,6 冲突；x² mod 11：4,3,1,6 ✓ 也无冲突？2²=4、6²=36 mod 11=3、10²=100 mod 11=1、17²=289 mod 11=3 → 6 与 17 冲突 ✗；2x mod 11：4,1,9,1 冲突 ✗。）

选 D。

易错提醒

① 逐个函数对全部 4 个键验算；② ⌊√x⌋：2→1、6→2、10→3、17→4（17 的平方根 ≈4.12）。