题目

用哈希(散列)方法处理冲突(碰撞)时可能出现堆积(聚集)现象，下列选项中，会受堆积现象直接影响的是()

错因

A

误以为"堆积 = 数据挤在一起 = 浪费空间"。但存储效率 = 已用单元 / 表长——这只取决于装入了多少元素，与这些元素怎么分布无关。冲突再多，单元被占用的总数不变，存储效率不变。

B

把因果倒置——散列函数是堆积的原因之一（设计不好的函数容易让 key 集中），而不是堆积的结果。题目问"堆积影响什么"，方向是"堆积 → ?"，散列函数本身不会被堆积反向修改。

C

误以为堆积让"实际占用率"变高。装填因子 α = n / m（n 是元素数、m 是表长）——这是装入数据时设计/统计出来的固定比值，不会因为冲突分布如何而变化。冲突 0 次和冲突 100 次，只要装的元素数和表长一样，α 就一样。

总解析

堆积（clustering）现象：

开放定址法处理冲突时（线性探测最典型），不同 key 散列到同一地址 → 后到的 key 沿探测序列找空位 → 同一地址附近形成一片连续的"占用块"。后续即使本不属于这个地址的 key 也可能撞进这片占用块，接力沿块往后探测，进一步加长块。

堆积对各项的影响：

量	公式/定义	是否受堆积影响	原因
存储效率	已用 / 总长	✗	元素数 + 表长决定，与位置分布无关
散列函数	用户预先选定	✗	函数本身固定，是"因"不是"果"
装填因子 α	n / m	✗	与冲突分布无关
平均查找长度 ASL	平均探测次数	✓	堆积越严重，每次探测要走过的连续占用块越长

为什么 ASL 直接被影响？

ASL = 平均每次查找需要的关键字比较次数。开放定址法中，查找步骤是"算出散列地址 → 看该位置是不是目标 → 不是就按探测序列试下一格 → ……直到找到目标或遇到空位"。

• 无堆积：每次冲突独立，探测往后跳几格通常就能找到
• 有堆积：探测要走过整片连续占用块，平均探测次数显著上升

线性探测的 ASL 在 α 不变时，比理想分布会高出一截，这就是堆积的"直接代价"。

直觉对照：想象一条停车场只有一排车位。

• 装填因子 = 停车场利用率（"开了多少车进来"）—— 与车停得乱不乱无关。
• 散列函数 = "你的车想停在哪一格"的偏好规则。
• 存储效率 = "几个格子被占了"。
• ASL = 找车要走过几个格子——这才是车扎堆停（堆积）会变长的那个量。

最终答案是 D（平均查找长度）。