GESP 七级 · GESP 202406 C++ 七级 第 23 题

现使用有 $N$ 个表项的哈希表，从 $M$ 个元素中进行查找。该哈希表为解决哈希函数冲突，为每个表项处建立单链表存储冲突元素。其查找操作的最坏情况时间复杂度为 $O(M)$。

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

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

【考点】哈希表｜冲突解决｜时间复杂度

GESP七级“数据结构与分析”模块，专门卡住“只记平均O(1)却忽略最坏O(M)"的直觉偏差。命题人把冲突解决方式（单链表）与时间复杂度（最坏）绑定，就是看你是否能透过表象分析极端分布。任何哈希表最坏情况都是O(最长链长度)，而最长链长度最极端可达M，所以本题答案是O(M)。

哈希表最坏情况就是所有键值都哈希到同一个桶（例如哈希函数恒为0或所有键的哈希值相同）。此时单链表长度等于元素总数M，查找必然遍历整条链表，时间复杂度为O(M)。这一结论对任意哈希函数都成立，只要存在一种输入分布使所有元素冲突，最坏就是O(M)。

选项B是典型陷阱：考生熟悉平均情况或混淆表长N与链长M，误以为最坏是O(N)或O(M/N)。题干强调“单链表存储冲突元素”，说明是分离链法，冲突链长度才是关键，而非表长。若考生只背“哈希表查找O(1)"，就会掉进这个坑。

若把“最坏情况”换成“平均情况”，答案变O(1)；若换成“开放寻址法”，最坏可能退化为O(N)。此类题先问自己：命题人想考我什么？——哈希函数分布与冲突解决方式的结合点。刷到类似题，先确认冲突解决方式，再想极端分布下的复杂度。