GESP 八级 · GESP 202403 C++ 八级 第 20 题

为解决哈希函数冲突，在哈希表项内设置链表存储该项内的所有冲突元素，则该哈希表内查找元素的最差时间复杂度为 $O(1)$。

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

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

【考点】哈希表冲突处理｜平均/最坏时间复杂度｜链表遍历

【考纲定位】哈希表冲突处理｜平均/最坏时间复杂度。命题人专卡"哈希表查找一定是O(1)"的迷思，绝大多数考生看到哈希就默认O(1)，却忽略最坏情况下的链表遍历成本。这道题在GESP八级数据结构模块，考察对哈希表性能边界的理解。

【解题思维】看到哈希表加链表，立刻想到"最坏情况全冲突"——所有元素都落在同一个桶里，该桶退化为长度为$n$的链表。此时遍历链表查找元素的时间复杂度为$O(n)$，而非$O(1)$。这类题通法是：先确认数据结构的查找机制（哈希+链表），再构造极端场景（所有元素哈希值相同），最后推导该场景下的时间复杂度。如果题目问的是平均情况，答案就是O(1)。

【陷阱拆解】选项B选"错误"是必然的，因为命题人把"最坏情况"和"平均情况"故意混淆。哈希表在平均情况下确实是$O(1)$，但一旦所有元素哈希到同一位置，链表长度就是$n$，查找必须从头遍历到尾，时间复杂度变成$O(n)$。如果你只背结论"哈希表O(1)"，就会掉进这个语义陷阱，误选A。命题人利用考生对"哈希表"这一抽象概念的过度简化，忽略了具体实现（链表）带来的最坏情况。

【反命题思维】假如把"最差"改成"平均"，答案立刻变A；若换成开放寻址法，最坏情况仍是$O(n)$，但平均可能接近$O(1)$。记住：刷到哈希相关题，先问自己"命题人考的是平均还是最坏？冲突解决用的是链表还是开放寻址？"这道题的核心就是区分平均和最坏情况，以及理解链表遍历的代价。