散列表底层演进本质是用数组提供o(1)随机访问骨架，链表解决哈希冲突，红黑树优化长链表查找；数组为定位基础，(n−1)&hash实现高效下标计算，负载因子超0.75触发翻倍扩容以维持性能。
散列表的底层演进，本质是为了解决数组固定长度与链表无序查找之间的矛盾——它不是简单拼凑，而是用数组做索引骨架、用链表应对不确定性，再逐步引入红黑树优化极端情况。
为什么必须用数组打底？
数组提供O(1)随机访问能力，这是散列表实现“键到值直接映射”的物理基础。散列表把 key 经哈希函数转成一个非负整数，再通过 (n - 1) & hash（n 是数组长度，要求是 2 的幂）快速算出下标。这个运算比取模快，且能均匀分散数据。没有数组，就失去“定位即访问”的核心优势。
链表挂载是怎么发生的？
哈希函数无法完全避免冲突（不同 key 算出相同下标），链表就是为此而生的兜底结构：
- 每个数组位置（桶）存的是一个节点指针，初始为 null
- 首次插入某桶时，新建 Node 并赋给该桶
- 后续同桶插入，新节点以头插或尾插方式接在已有链表后
- 查找时，先定位桶，再遍历链表逐个比对 key 的 equals()
这种“数组索引 + 链表容错”组合，让平均查找成本降为 O(1 + α)，其中 α 是负载因子（元素总数 / 数组长度）。
什么时候链表会升级成红黑树？
当某个桶的链表太长（默认 ≥8），查找退化为 O(n)，影响整体性能。此时触发树化，但需同时满足两个条件：
- 该链表长度 ≥8
- 整个散列表的数组长度 ≥64
不满足第二条时，优先选择扩容而非树化——因为小数组下树化收益低，反而增加维护开销。树化后，该桶由链表头节点切换为 TreeNode，支持 O(log n) 查找；若后续删除频繁导致节点 ≤6，则自动退化回链表。
扩容如何影响已有数据？
当元素数超过 capacity × loadFactor（默认 0.75），触发 resize()：
- 新数组容量 = 原容量 × 2
- 所有旧节点重新计算桶位：新下标要么是原下标，要么是原下标 + 旧容量
- 无需全部 rehash，仅靠位运算即可判断迁移方向
扩容保障了 α 始终可控，是维持 O(1) 性能的关键守门机制。
