HashSet 的 contains() 退化为 O(n) 是因哈希碰撞导致所有元素集中在同一桶，须遍历链表逐调 equals()；JDK8+ 树化仅优化单桶内查找至 O(log k)，无法解决哈希函数缺陷。
哈希碰撞严重时，HashSet 的 contains() 为什么变慢
不是“变慢一点”，而是从平均 O(1) 退化为最坏 O(n) —— 这意味着遍历整个桶里所有元素逐个调用 equals()。JDK 8+ 虽然在链表长度 ≥8 且数组长度 ≥64 时会转为红黑树，但前提是哈希值分布仍集中在一个桶里；如果大量对象 hashCode() 返回相同值（比如只依赖一个固定字段），树化也救不了查找效率。
hashCode() 写得弱，HashSet 就真成“线性集合”了
常见错误场景：自定义类只重写了 equals()，没重写 hashCode()；或 hashCode() 总是返回常量（如 return 1;）。此时所有实例都落到同一个桶中，add()、contains()、remove() 全部退化为链表遍历。
- 调试时可打印
map.size()和map.entrySet().stream().map(e -> e.getKey().hashCode() % map.capacity()).distinct().count()，看实际分散的桶数是否远小于元素数 - 用
Objects.hash(field1, field2)是安全起点；避免手动拼接字符串再取hashCode()（易触发哈希风暴） - 若业务中大量使用短字符串（如 ID 为 "001", "002"…），注意默认
String.hashCode()在低位重复性高，可能加剧冲突
JDK 8+ 的树化机制不是万能的
树化只解决单个桶内查找效率，不解决哈希函数本身缺陷。即使桶内转成红黑树，时间复杂度也只是降到 O(log k)（k 是该桶元素数），但如果 10 万个元素全挤进 1 个桶，log₂(100000) ≈ 17，仍比正常散列的 O(1) 慢一个数量级，且扩容失效——因为扩容依据的是总元素数和负载因子，不是桶分布均匀度。
- 树化触发条件苛刻：
bucket链表长度 ≥8 且 整个HashMap数组长度 ≥64；否则仍维持链表 - 一旦发生树化，后续插入同桶元素需走红黑树路径，比较开销比链表更大（要比较
compareTo()或hashCode()+equals()） - 若对象未实现
Comparable，又没传Comparator，树化会失败并回退为链表
真实业务中最容易被忽略的一点
性能问题往往不出现在单元测试里——测试数据少、哈希分布“看起来还行”。真正出问题是在上线后，某类日志 ID、用户设备指纹、或时间戳截断字段（如只取秒级）导致批量对象哈希值撞车。这时 HashSet 查找延迟毛刺明显，但堆栈里看不到明显异常，只会看到 HashMap.get() 占用 CPU 飙升。别等报警，对高频使用的自定义 key 类，务必做哈希分布压测。
