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

一个哈希表，包括 $n$ 个位置（分别编号 $0 \sim (n-1)$），每个位置最多仅能存储一个元素。该哈希表只有插入元素和查询两种操作，没有删除或修改元素的操作。以下说法错误的是（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】哈希表｜线性探测｜时间复杂度

1. 考纲定位 本题考查 GESP 七级"数据结构与算法"模块中的哈希表线性探测机制。命题人专门设置此题，就是要卡住考生对"哈希表不是随机访问"这一本质的认知偏差——不少学生误以为哈希表始终 O(1) 查询，却忘了冲突处理链的存在。

2. 解题思维 按选项逐一检验：

• A 项：哈希表满时，若目标元素恰好被插入到哈希位置之后的最远空位，线性探测需遍历全部 n 个位置，O(n) 正确。
• B 项：同样满表情形，探测链最长可达 n，仍是 O(n)，断言 O(1) 显然错误。
• C 项：哈希函数只覆盖前 m 个位置，冲突时向后探测，最多探测 n−m 个空位，O(n−m) 正确。
• D 项：线性探测将冲突元素依次往后放，但一旦遇到空位就停止，故空位之后不可能再有该元素，说法错误。

题目问"错误的是"，B、D 都错，但 D 是更隐蔽的语义陷阱——它把"哈希位置空"偷换成"元素不存在"，实际该元素可能已被探测链推到别处。

3. 陷阱拆解

• A 项陷阱：默认哈希表"空位即不存在"，忽略探测链的存在。
• B 项陷阱：把 O(1) 当成哈希表的固有属性，未区分"理想哈希"与"实际探测"。
• C 项陷阱：误以为哈希范围 m 小就会自然减少探测次数，实则探测上限仍是 n−m。
• D 项陷阱：最阴险！"哈希位置为空"≠"元素不在表中"，因为元素可能被推到后面，这是线性探测的必然结果。

4. 反命题思维 若把哈希函数改为开放寻址的二次探测，再问"最坏查询复杂度"，答案会变成 O(√n) 而非 O(n)。刷到此类题，先问自己：这里考的是哈希的"理论理想性"，还是"实际探测链"？前者选 O(1)，后者选 O(n)。