使用动态数组实现的HashMap时间复杂度是多少？put/get仍为O(1)吗

你提到的这种用动态数组（示例中为ArrayList）作为哈希桶底层存储的拉链法HashMap，put和get操作的均摊时间复杂度依然为O(1)，只有极端场景下才会出现复杂度退化，具体分析如下：

• 哈希寻址环节开销固定：HashMap的核心逻辑是先对key做哈希计算，再取模得到桶数组的下标，直接定位到对应存储位置。不管底层是静态数组还是动态数组，数组按下标随机访问的时间复杂度都是O(1)，这一步的开销不会因为使用动态数组发生变化。
• 动态数组扩容的均摊开销可忽略：动态数组容量不足时复制全量元素到新数组的扩容操作确实是O(n)级开销，但工业级HashMap通常会设置固定加载因子（常见为0.75），每次扩容都会将容量翻倍，平均每插入n个元素才会触发一次扩容，扩容开销平摊到每一次put操作上就是常数级，不会影响均摊时间复杂度的结论。
• 最坏复杂度退化场景：如果哈希函数设计不合理，大量key的哈希值冲突，全部落到同一个哈希桶的链表中，那么不管底层用什么数组实现，get/put都需要遍历整个链表做key匹配，最坏时间复杂度会退化到O(n)。目前成熟的HashMap实现都会做哈希打散优化，同时会将过长的链表转换为红黑树，把最坏复杂度降到O(log n)，正常使用场景下几乎不会触发退化。

参考实现代码：

public class HashMap <key, value>{
    private class Entry <k, v>{
        private k key;
        private v value;

        public Entry(k key, v value){
            this.key = key;
            this.value = value;
        }
    }

    private ArrayList < LinkedList<Entry<key, value>> > buckets = new ArrayList<>();
    
    // 其余实现逻辑
    // ...
}

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