CSP-S 提高级 · CSP 2024 提高级第一轮 第 10 题

在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知某哈希表中有 $n$ 个键值对，表的装载因子为 $\alpha (0 < \alpha \leq 1)$。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（ ）？

这题考哈希表开放地址法最坏时间复杂度。别被装载因子迷惑，直接想极端情况：所有键哈希值相同怎么办？

最容易掉进选项 C 的陷阱，那是线性探测的平均探测次数公式，题目明确问最坏情况。还有学生可能误以为 O(n) 是链表才有的，其实哈希表最坏退化成链表长度也是 O(n)。

这道题考查数据结构中哈希表的冲突解决策略，特别是开放地址法在最坏情况下的时间复杂度。命题人挖坑很典型：给了装载因子α，让你联想到那个漂亮的平均探测次数公式 1/(1-α)，然后让你选 C。但题目关键词是“最坏情况”，这直接否定了平均情况的适用性。开放地址法的核心思想是遇到冲突就按探测序列找下一个空位，最坏情况就是所有键的哈希值都相同，导致它们全部挤在同一个起始位置，探测序列会一直往后挪，直到把表中所有已占用的位置都检查一遍。此时查找一个元素需要遍历 n 个键值对，时间复杂度就是 O(n)。选项 A 和 B 显然不对，哈希表不是平衡树。所以选 D。考频数据：题库共考过 2 题，覆盖 1 个考试级别（2024-2025），2024 年 1 题、2025 年 1 题，都是 CSP 提高级。暂无足够依据预测未来具体考法。