Java中HashMap的replace(Key, Value)方法的时间复杂度是多少？

核心结论 #

• 平均场景下时间复杂度为O(1)，你的初始判断是正确的
• 极端场景下（大量哈希碰撞）的时间复杂度和JDK版本相关：JDK7及更早为O(n)，JDK8及之后为O(log n)

具体逻辑说明 #

replace(K, V)的底层执行逻辑和get(K)完全一致，没有额外的重哈希、扩容开销，仅在找到匹配的key节点后直接修改其存储的value值：

1. 首先计算入参key的哈希值，定位到对应的数组桶位，这一步是固定O(1)开销
2. 遍历该桶内的存储结构，找到equals判断匹配的key节点
3. 直接修改节点的value属性，返回旧值，这一步是固定O(1)开销

哈希碰撞的影响 #

你担心的哈希碰撞只会影响第二步的遍历开销，分两种情况：

• 正常业务场景：只要hashCode()方法实现合理，哈希值分布均匀，每个桶内的节点数会稳定在常数级，遍历开销可以忽略，整体复杂度就是O(1)，这也是业界对HashMap操作的通用复杂度评估标准
• 极端异常场景：如果出现大量哈希碰撞（比如恶意构造相同哈希值的key，或者hashCode()方法实现错误所有key返回相同哈希值），所有节点都落在同一个桶内：
  • JDK7及更早版本：桶底层用链表存储，最坏需要遍历整个链表才能找到目标节点，复杂度O(n)
  • JDK8及之后版本：桶内链表长度超过8时会自动转换为红黑树存储，最坏遍历开销为O(log n)

这种极端场景正常开发中几乎不会遇到，不需要作为常规评估依据。

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