哈希表创建时间复杂度疑问：最坏与均摊复杂度分析

一、创建含n个元素的哈希表最坏时间复杂度是否为O(n²)？ #

这个结论仅在极端罕见的扩容策略下成立，在实际常用的哈希表实现中并不正确：

• 哈希表单次插入最坏O(n)的场景是触发扩容时，需要重新哈希并迁移当前所有元素。但主流哈希表（如Java HashMap、Python dict）采用容量翻倍的扩容策略：初始容量通常为固定值，当负载因子达标时，容量变为原来的2倍。
• 插入n个元素时，扩容次数为log₂n级，每次扩容迁移的元素数依次为1、2、4、...、n/2，总迁移操作数为1+2+4+...+n/2 = n-1，属于O(n)级别。加上n次插入本身的操作，总时间复杂度为O(n)。
• 只有当哈希表采用线性扩容策略（比如每次容量只加1）时，才会出现插入第k个元素时触发扩容并迁移k个元素的情况，总操作数为1+2+...+n = O(n²)，但这种策略因效率过低，几乎不会被实际实现采用。

二、创建含n个元素的哈希表的平均和均摊时间复杂度是否为O(1)？ #

答案是否定的，正确结论是O(n)：

• 单次插入的平均/均摊时间复杂度为O(1)，指的是每次插入操作的平均开销是常数级。但创建含n个元素的哈希表需要执行n次插入操作，总开销为n × O(1) = O(n)。
• O(1)代表常数时间，意味着操作耗时不随n变化，但创建n个元素必然需要遍历、处理每个元素，耗时随n线性增长，不可能是常数时间。

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