CSP-S 2024 第一轮 第10题：在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和冲突解决策略。已知

题目

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

选项

• A. $O(1)$
• B. $O(\log n)$
• C. $O(1/(1-\alpha))$
• D. $O(n)$

答案

D

题解

选 D．\(O(n)\)。

开放地址法中，发生冲突后，需要按照探测规则继续检查其他位置。最坏情况下，查找一个元素可能需要检查表中全部 \(n\) 个元素，因此时间复杂度为 \(O(n)\)。

例如，使用线性探测时，如果所有键的哈希值都相同，它们会连续存放。查找最后插入的键，就需要依次检查这 \(n\) 个位置。

选项 C 的 \(O\!\left(\frac{1}{1-\alpha}\right)\) 通常是在均匀散列假设下，查找失败时的期望时间复杂度上界，且要求 \(\alpha<1\)，不是最坏情况。

记住这道题的关键：问的是“最坏情况”，不是“平均情况”。