哈希表时间复杂度真的是O(1)吗？主流语言实现的底层数组大小通常是多少？

首先回应第一个问题：直接称哈希表时间复杂度为O(1)是否完全错误？

你提到的哈希表基础结构为数组加链表、平均查找长度为O(n/array_length)的结论是正确的，但“O(1)的说法完全错误”这个判断并不成立。

• 算法复杂度分析中哈希表的O(1)特指均摊复杂度，前提是哈希表维持合理的负载因子（负载因子=存入元素总数n/底层数组长度length）。所有工业级哈希表实现都会预设负载因子阈值，通常在0.6~0.75区间，一旦当前负载因子超过阈值就会触发扩容：申请更大的新底层数组，将所有旧元素重新哈希后存入新数组，把负载因子重新降到阈值以下。这种情况下n/length始终被控制在常数范围，因此均摊下来插入、查找、删除操作的复杂度确实符合O(1)的定义。
• 你举的长度为100的数组存入100万条数据的例子，属于完全没有扩容逻辑的极端错误实现，不符合工业界的标准实现规范，不能用来否定O(1)的通用结论。

接下来是主流语言哈希表的底层数组大小说明：

JavaScript 哈希表（Object/Map） #

不同JS引擎实现有差异，以应用最广的V8引擎（Chrome、Node.js采用）为例：

• 空哈希表默认初始底层数组大小为16，负载因子阈值为0.75
• 每次扩容后新数组大小为旧数组的2倍，数组长度始终保持为2的幂次，用于优化哈希取模运算效率

Go 语言哈希表（map） #

• 未指定容量的空map初始化时底层数组大小默认是0，插入第一个元素时会申请长度为8的初始数组
• 负载因子阈值为6.5（Go的哈希表做了专属优化，远高于其他语言的阈值也能保持稳定性能），触发扩容时新数组大小为旧数组的2倍
• 如果初始化时指定容量（make(map[K]V, cap)），底层会根据传入的容量计算适配的初始数组长度，保证存入cap个元素前不需要触发扩容

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