题目

为提高哈希(Hash)表的查找效率，可以采取的正确措施是( )。 I. 增大装填因子 II. 设计冲突少的哈希函数 III. 处理冲突时避免产生堆积现象

错因

A

把"装填因子大小与效率的关系"方向完全弄反了。 越大表越满，元素之间冲突概率越高，平均查找长度（ASL）越长，效率下降。要提效率应该减小 α（如扩容、rehash）——这正是 Java HashMap、Python dict 的扩容机制原理。

B

只选 II，漏掉 III。"避免堆积"也是提效率的有效措施——堆积（次级聚集）会让一连串冲突的元素挤成一团，失败查找时要扫描整个堆积块才能确认不存在。改用平方探测、双重哈希、链地址法都能减少这种聚集。

C

把 I 当对（同 A 的方向错误），同时正确判断 II 对。少考虑了 III。

总解析

逐项判断：

• I 错：装填因子 越大，冲突越多，ASL 越长。线性探测下不成功查找的 ASL ≈ ， 趋近 1 时 ASL 急剧爆炸。要减小 α 才能提效率。

• II 对：哈希函数冲突少 → 直接命中目标位置的概率高 → ASL 直接降低。这是哈希函数设计的核心目标（如 MurmurHash、CityHash 都为均匀分布优化）。

• III 对：堆积（次级聚集）现象是线性探测的固有问题——一连串冲突的元素聚成一段连续空间，失败查找要扫整段。改用平方探测（按 跳）、双重哈希（用第二个哈希函数算步长）、或链地址法（每个槽挂链表）都能避免堆积，显著降低 ASL。

正确措施是 II 和 III。最终答案是 D。