hashmap通过链地址法处理哈希冲突，链化（尾插链表）与树化（≥8且容量≥64时转红黑树）、退化（≤6节点还原为链表）动态切换，辅以扰动函数和扩容机制平衡效率与内存开销。
Java 中 HashMap 通过“链地址法”处理哈希冲突，再结合阈值控制实现链化与树化动态切换，核心是平衡查找效率与内存开销。
链化：冲突发生时默认挂链表
当多个 key 的 hash 值映射到同一个桶（数组索引）时，HashMap 不覆盖原有数据，而是将新节点追加到该桶的链表尾部（JDK 1.8 起采用尾插法，避免多线程下的环形链表问题）。每个 Node 包含 hash、key、value 和 next 引用，形成单向链表。
- 查找时先定位桶，再逐个比对 key 的 hash 值和 equals 结果
- 链表结构插入稳定、删除方便，且扩容时只需重哈希节点，无需移动其他桶数据
- 适合冲突较少的日常场景，时间复杂度平均为 O(1)，最坏为 O(n)
树化：链表过长时升级为红黑树
当某个桶中链表长度 ≥ 8 且整个哈希表数组长度 ≥ 64 时，该链表会转为红黑树。这个双重条件设计基于泊松分布统计——在负载因子 0.75 下，单桶出现 8 个节点的概率仅约千万分之六，说明已属异常碰撞（如恶意 Hash 攻击或低质量 hashCode）。
- 树化后查找、插入、删除最坏时间复杂度降为 O(log n)
- TreeNode 是 Node 的子类，仍保留在原桶位置，上层调用完全无感
- 不满足条件时不强制树化，避免小数据量下红黑树维护开销反超链表
退化：红黑树节点减少时还原为链表
当树中有效节点数 ≤ 6 时，红黑树会自动退化回链表。这确保了轻量级操作仍走简单路径，避免“小题大做”。
- 退化触发发生在 resize 或 remove 过程中，由 treeifyBin 方法统一判断
- 退化只针对当前桶，不影响其他桶结构
- 6 和 8 之间留出缓冲区间，防止频繁树化/退化震荡
配合机制：扰动函数 + 扩容进一步缓解冲突
链化与树化是冲突发生后的应对策略，而扰动函数和扩容是从源头降低冲突概率的关键辅助手段：
- hash 值经扰动（h ^ (h >>> 16)）让高位参与索引计算，避免仅低位变化导致的集中冲突
- 数组长度始终为 2 的幂，用 hash & (length - 1) 替代取模，提升索引计算效率
- 负载因子默认 0.75，元素数超过容量 × 0.75 即触发翻倍扩容，所有节点重哈希分散，天然稀释链表长度
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
