Java - 集合篇

6.1 ArrayList / LinkedList

ArrayList 源码分析

核心变量：

private static final int DEFAULT_CAPACITY = 10;                        // 默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {};                  // 空实例共享数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};  // 默认大小空实例
transient Object[] elementData;  // 存储元素的数组缓冲区
private int size;                // ArrayList 大小

ArrayList 扩容机制

特性	说明
触发时机	`add()` 前检查 `size+1` 是否超数组长度
首次扩容	无参构造 → 首次 `add()` 时才初始化为 10
后续扩容	`newCapacity = oldCapacity + (oldCapacity >> 1)`，即 1.5 倍
不足时	若 1.5 倍仍不足，直接用所需最小容量
数据迁移	`Arrays.copyOf()` 拷贝，O(n)

⚠️ 已知数据量时，建议指定初始容量，避免多次扩容。

ArrayList 底层原理总结：

底层是动态数组
初始容量 0，首次添加才初始化为 10
扩容为原来的 1.5 倍，每次扩容需拷贝数组

数组与 List 互转

Arrays.asList() → List：底层复用同一数组地址，数组改了 List 也会变
List.toArray() → 数组：底层进行了拷贝，List 改了数组不受影响

ArrayList vs LinkedList 总结

维度	ArrayList	LinkedList
底层结构	动态数组（连续内存）	双向链表（离散内存）
增删（头/中）	O(n)	理论 O(1)，但查找位置需 O(n)
增（尾）	O(1) 均摊，缓存友好，通常更快	O(1)
空间	省空间，无指针开销	每节点额外 2 个指针，碎片化
线程安全	❌	❌

6.2 HashMap 底层原理

前置知识

红黑树五条性质：

节点要么是黑色，要么是红色
根节点是黑色
叶子节点都是黑色的空节点
红色节点的子节点都是黑色
任意完整路径包含的黑色节点数量一致

所有红黑规则都是为了保证树的平衡。红黑树是自平衡的 BST，时间复杂度 O(log n)。

散列表（Hash Table）：

散列表 = 根据 Key 进行 Value 索引的数据结构。由数组演化而来，利用数组支持下标随机访问的特性。

散列冲突：多个 key 映射到同一数组下标位置。几乎无法完全避免。

链表法解决冲突：每个桶（bucket/slot）对应一条链表，冲突元素放入链表中。

时间复杂度：

插入：O(1)
查找/删除：平均 O(1)，最坏 O(n)（链表），转红黑树后 O(log n)

HashMap 实现原理

HashMap = 数组（存储容器）+ Hash 算法（导航仪/映射规则）

底层使用 Hash 表（数组 + 链表或红黑树）：

put 时，用 key 的 hashCode 重新 hash 计算下标
存储时若 hash 冲突：
- key 相同 → 覆盖 value
- key 不同 → 放入链表或红黑树
get 时，找到 hash 对应的下标，再判断 key 是否相同

JDK 1.7 vs JDK 1.8

版本	结构	冲突处理
JDK 1.7	数组 + 链表	拉链法（头插法）
JDK 1.8	数组 + 链表 + 红黑树	链表长度 > 8 且数组长度 ≥ 64 → 转红黑树；节点 < 6 时退化回链表

6.3 HashMap put 流程 / 扩容 / 寻址 / 死锁

put 方法具体流程

put 流程五步总结：

判断 table 是否为空 → resize() 初始化
计算 hash 得到数组索引
table[i] == null → 直接新建节点
table[i] != null：
- 首个元素 key 相同 → 覆盖
- 是红黑树 → 树中插入
- 是链表 → 尾插法插入，超 8 则转红黑树
插入成功后判断 size > threshold → 扩容

HashMap 使用懒加载：创建后不立即分配数组，首次 put 时才初始化。

扩容机制（resize）

简要逻辑：判断现状 → 容量翻倍 → 建新数组 → 利用位运算将旧数据分流到新数组（无需重算 Hash）。

扩容总结：

首次添加初始化数组长度为 16
每次扩容为之前的 2 倍
扩容后迁移数据：
- 无冲突节点 → 直接 e.hash & (newCap-1) 计算新位置
- 红黑树 → 走树的 split
- 链表 → (e.hash & oldCap) == 0 判断，0 则留在原位，1 则移到 原位置 + oldCap

寻址算法

生成原始哈希值：调用 Key 的 hashCode()
高位扰动：h ^ (h >>> 16)，让高位也参与计算，减少冲突
位运算取模：hash & (n-1)，因为 n 是 2 的幂，等价于取模运算

为何数组长度一定是 2 的幂？

计算索引时：位与运算代替取模，效率高

扩容时：hash & oldCap == 0 判断位置不变还是移动

JDK 1.7 HashMap 多线程死锁问题

本质：扩容时 头插法 + 并发操作 → 链表成环。

解决方案：

多线程环境使用 ConcurrentHashMap
升级 JDK 1.8+（头插法 → 尾插法，但仅解决死循环，数据覆盖问题仍存在）