HashMap底层是“数组+链表+红黑树”混合结构：数组为桶（初始容量16，2的幂），链表解决哈希冲突，链表长度≥8且数组容量≥64时转红黑树以优化查询至O(log n)。
Java 中 HashMap 的底层是“数组 + 链表 + 红黑树”三者结合的混合结构，核心目标是在平均情况下实现 O(1) 的增删查性能，同时兼顾高负载时的稳定性。
数组是哈希表的主干容器
HashMap 内部维护一个 Node<k>[] table</k> 数组，每个数组元素称为一个“桶（bucket）”。键值对通过哈希函数计算索引后，被映射到对应桶中。初始容量为 16，且始终是 2 的幂次——这使得取模运算可用位运算 (n - 1) & hash 高效完成，避免了昂贵的 % 运算。
- 扩容时数组长度翻倍（如 16 → 32），所有已有元素需重新哈希再分配（rehash）
- 数组长度为 2 的幂，保证了 hash 值低位能充分参与索引计算，减少哈希冲突
链表解决哈希冲突
当多个键的哈希值经运算后落在同一个桶位置时，就发生哈希冲突。HashMap 使用链地址法：把冲突的节点以单向链表形式串在同一个数组槽位下。
- 新节点插入链表头部（JDK 7 是头插，JDK 8 改为尾插，避免多线程扩容时的死循环）
- 链表查找需遍历，最坏情况退化为 O(n)，所以需要后续优化
红黑树应对链表过长
当某个桶中链表节点数 ≥ 8，且当前数组长度 ≥ 64 时，该链表会转换为红黑树；反之，若树中节点数 ≤ 6，则退化回链表。这是 JDK 8 引入的重要优化。
立即学习“Java免费学习笔记（深入）”；
- 红黑树保证最坏查找/插入/删除为 O(log n)，显著优于长链表
- 不一上来就用树，是因为小规模数据下链表更轻量、缓存友好，树的维护开销反而更高
- 树节点是
TreeNode类型，继承自Node，复用部分字段，但额外维护 parent/child/red 等树结构信息
哈希与键的正确性依赖
HashMap 的正确运行强依赖 hashCode() 和 equals() 的合理实现：
-
hashCode()决定键被分配到哪个桶；若两个相等对象返回不同哈希值，会导致 get 失败 -
equals()在桶内比对具体键是否匹配；若未重写，将使用 Object 默认的引用比较，导致逻辑错误 - 因此，自定义类作 key 时，必须同时重写这两个方法，且保持一致性：相等的对象必须有相同哈希值
