负载因子为2的外链式哈希表插入N个元素的最坏复杂度是多少

你推导的Θ(N)是平均时间复杂度，该结论成立的前提是哈希函数能将键均匀映射到不同桶中。负载因子固定为2时，每个桶的平均链表长度为常数，单次插入的平均时间是常数，N次插入总耗时确实为Θ(N)，这个结论在平均场景下是正确的。

最坏时间复杂度结论 #

最坏情况下插入N个元素的时间复杂度为 Θ(N²)，推导逻辑如下：

• 最坏场景为所有插入的键都产生哈希冲突，全部被映射到同一个桶的链表中
• 标准哈希表插入逻辑需要先判断键是否已存在：每次插入新元素时，都需要遍历当前桶内已有的所有元素做键值比对，确认不存在后再插入
• 总操作次数计算：
  • 插入第1个元素：无需比对，耗时为常数
  • 插入第2个元素：比对1次，耗时为常数+1次比对开销
  • ...
  • 插入第N个元素：比对N-1次，耗时为常数+(N-1)次比对开销
• 累加所有操作的总开销为 $N(N-1)/2 + C*N$，其中C为单次哈希计算的常数开销，最终复杂度为Θ(N²)

内容的提问来源于stack exchange，提问作者daniel