最坏情况下哈希表查找为o(n)，因大量key的hashcode相同且未树化时，全堆积于同一链表桶中，需逐个equals遍历；满足链表≥8且数组≥64才转红黑树，降为o(log n)；若compareto无效或数组过小，仍退化为o(n)。

最坏情况下是 O(n)。

为什么是 O(n)

当大量不同 key 的 hashCode() 完全相同（或模数组长度后落在同一桶），且未触发树化时，所有元素会堆积在同一个桶中，形成单向链表。此时：

• 每次 get() 或 put() 都需从头遍历链表，逐个比对 equals()
• 查找第 n 个元素需遍历 n 次，时间与元素总数线性相关
• 若该桶中存有 10,000 个键值对，一次查询最多执行约 10,000 次比较

红黑树能改善吗

能，但有前提条件：

Alibabacloud Sdk Client Initialization For Java

在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

• 必须同时满足：链表长度 ≥ 8 且 数组长度 ≥ 64
• 满足时链表转为红黑树，最坏查询降为 O(log n)（如 log₂10000 ≈ 14）
• 若数组太小（比如刚初始化为 16），即使链表很长也不会树化，仍维持 O(n)

什么情况会让红黑树也失效

极少数场景下，树化后性能反而不如链表：

• 所有 key 的 hashCode() 完全相同，且 compareTo() 无法有效区分（例如自定义类未实现可比较逻辑或返回 0）
• 此时 TreeNode 无法构建有效二叉结构，退化为类似链表的线性查找
• 红黑树节点内存开销更大，实际性能可能更差

真实攻击中的表现

哈希碰撞攻击（HashDoS）正是利用这一点：

• 攻击者批量生成不同字符串，使其 hashCode() 全部等于某固定值（如 0）
• 服务端用 HashMap 解析参数（如 Spring 的 @RequestParam Map）时，单请求即可让一个线程卡在长链表遍历中
• CPU 单核 100%，响应延迟从微秒级飙升至数十毫秒甚至超时

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南