GESP 七级 · GESP202609 C++ 七级 第 9 题

关于哈希表，下列说法正确的是（　　）。

哈希表的核心是哈希函数将键映射到索引。由于哈希函数是确定性的，且表大小有限，必然存在不同键映射到同一索引的情况，即冲突。链地址法用链表解决冲突，查找时间取决于链表长度，平均为 O(1 + α)，并非恒定 O(1)。开放定址法通过探测下一个空闲位置解决冲突，是标准做法。查找效率与装填因子 α = n/m 直接相关，元素越多效率越差。因此，只有 C 选项正确。

A 错在"完全避免冲突"。哈希函数是确定性的，且表大小有限，必然存在不同键映射到同一索引的情况。即使使用完美哈希，也需预先知道所有键，不适用于通用场景。B 错在"一定为 O(1)"。链地址法查找时间取决于链表长度，平均为 O(1 + α)，当装填因子 α 接近 1 时，链表可能很长，退化为 O(n)。D 错在"与元素个数无关"。查找效率与装填因子 α = n/m 直接相关，元素越多，冲突概率越高，平均探测次数增加。C 正确，开放定址法通过探测下一个空闲位置解决冲突，是标准做法。

1. 考纲定位

本题考查 GESP 七级《数据结构与算法》模块中"哈希表"核心概念。命题人意图检验考生对哈希冲突必然性的理解——这是绝大多数考生容易忽略的底层逻辑。

2. 解题思维

哈希表的核心是哈希函数将键映射到索引。由于哈希函数是确定性的，且表大小有限，必然存在不同键映射到同一索引的情况，即冲突。链地址法用链表解决冲突，查找时间取决于链表长度，平均为 O(1 + α)，并非恒定 O(1)。开放定址法通过探测下一个空闲位置解决冲突，是标准做法。查找效率与装填因子 α = n/m 直接相关，元素越多效率越差。因此，只有 C 选项正确。