hashmap通过链地址法解决哈希冲突，jdk 1.8起叠加红黑树优化（链表≥8且数组≥64时转树）和动态扩容机制（容量翻倍、重哈希），三者协同保障o(1)平均查找性能。
Java 中 HashMap 发生哈希冲突时，主要靠链地址法（拉链法）解决，JDK 1.8 起在此基础上叠加了红黑树优化和动态扩容机制，三者协同保障性能不退化。
链地址法：每个桶挂一个链表
HashMap 底层是一个数组，每个数组位置（桶）不直接存键值对，而是存一个链表（或红黑树）的头节点。当多个 key 的 hash 值落到同一索引时：
- 新节点采用尾插法追加到链表末尾（JDK 1.8 起，避免多线程扩容死循环）
- 查找时先定位桶，再遍历链表，用
equals()比对 key - 插入、删除都不影响其他桶，实现简单，空间弹性好
红黑树优化：链表太长就升级结构
单纯链表在极端冲突下会退化为 O(n) 查找。JDK 1.8 引入阈值控制：
- 当某个桶的链表长度 ≥ 8 且 整个数组长度 ≥ 64 时，链表自动转为红黑树
- 当树中节点数 ≤ 6 时，红黑树退化回链表
- 转换后查找最坏时间复杂度从 O(n) 降至 O(log n)，但不会一有冲突就树化，避免小数据开销
扩容与哈希扰动：从源头缓解冲突
冲突无法消除，但可大幅减少：
- 默认初始容量 16，负载因子 0.75；元素数超 12 就触发扩容（容量翻倍），所有 key 重新计算位置，打散堆积
- key 的 hashCode 经过扰动函数：
(h = key.hashCode()) ^ (h >>> 16)，让高位参与索引计算，避免低比特重复导致的集中冲突 - 数组长度始终是 2 的幂，用
hash & (length - 1)替代取模，提升索引计算效率
为什么不选其他方案？
开放定址法（如 ThreadLocalMap 使用的线性探测）要求所有数据挤在数组里，容易聚集、删除困难；再哈希和公共溢出区在标准库中基本不用。HashMap 选择链地址法，是因为它更适应动态增删、高负载、大对象的通用场景，工程落地成熟，扩展性强。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
