java 集合框架
ArrayList 深度解析
1.1 底层数据结构
// JDK1.8源码关键定义
transient Object[] elementData; // 实际存储数据的数组
private int size; // 当前元素数量1.2 核心机制
① 扩容机制
// 添加元素核心逻辑（JDK1.8）
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 容量检查
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY(10), minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity); // 触发扩容
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 1.5倍扩容
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity);
}扩容流程图解：
添加元素 → 检查容量不足 → 计算新容量（原1.5倍）
↓ ↑
数组拷贝（System.arraycopy）② 随机访问性能
// 时间复杂度O(1)
public E get(int index) {
rangeCheck(index);
return elementData(index); // 直接数组下标访问
}③ 插入删除性能瓶颈
// 中间插入示例（需移动元素）
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}元素移动示意图：
原数组: [A][B][C][D][ ][ ]
插入X到位置1:
1. 将B,C,D后移 → [A][ ][B][C][D][ ]
2. 放入X → [A][X][B][C][D][ ]二、LinkedList 深度解析
2.1 底层数据结构
// JDK1.8双向链表节点定义
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} 2.2 核心操作原理
① 插入元素
// 头部插入（O(1)时间复杂度）
private void linkFirst(E e) {
final Node f = first;
final Node newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
} ② 随机访问性能
// get方法通过折半查找优化（仍为O(n)）
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node node(int index) {
if (index < size>> 1)) { // 前一半从头遍历
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // 后一半从尾遍历
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} ③ 内存占用分析
每个元素需要额外存储：
- 前驱节点引用（4/8字节）
- 后继节点引用（4/8字节）
- 对象头（12字节）
总内存开销约为：(对象头) + 元素数据 + 2*指针
三、HashMap 深度解析
3.1 数据结构演进
JDK1.7 vs JDK1.8
版本 | 数据结构 | 冲突处理 | 线程安全性问题 |
JDK1.7 | 数组+单向链表 | 头插法 | 多线程扩容可能导致死循环 |
JDK1.8+ | 数组+链表/红黑树 | 尾插法 | 数据丢失问题仍存在 |
3.2 核心实现原理
① 哈希函数优化
// JDK1.8的hash()方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}设计目的：将高16位与低16位异或，减少哈希碰撞概率
② 链表树化条件
static final int TREEIFY_THRESHOLD = 8; // 链表转树阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化容量
// 树化逻辑（部分代码）
final void treeifyBin(Node[] tab, int hash) {
int n, index; Node e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize(); // 优先扩容
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 执行树化操作...
}
} ③ 扩容机制（resize）
// 扩容核心逻辑（部分）
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < maximum_capacity oldcap>= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // 双倍扩容
}
// ...其他情况处理
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
// 数据迁移逻辑（高低位拆分）...
return newTab;
} ④ 红黑树退化为链表
static final int UNTREEIFY_THRESHOLD = 6; // 树转链表阈值3.3 put操作全流程
graph TD
A[计算key的hash值] --> B{桶位置是否为空?}
B -- 是 --> C[直接创建新节点插入]
B -- 否 --> D{是否是树节点?}
D -- 是 --> E[红黑树插入]
D -- 否 --> F[遍历链表]
F --> G{存在相同key?}
G -- 是 --> H[覆盖value]
G -- 否 --> I[尾部插入新节点]
I --> J{链表长度≥8?}
J -- 是 --> K{数组长度≥64?}
K -- 是 --> L[转换为红黑树]
K -- 否 --> M[扩容]四、三大集合对比总结
特性 | ArrayList | LinkedList | HashMap |
底层结构 | 动态数组 | 双向链表 | 数组+链表/红黑树 |
随机访问 | O(1) | O(n) | key哈希计算O(1) |
插入删除 | 尾部O(1)，中间O(n) | 头尾O(1)，中间O(n) | 哈希冲突时O(1)~O(log n) |
内存占用 | 较小（仅数组开销） | 较大（节点对象） | 较大（数组+节点） |
线程安全 | 不安全 | 不安全 | 不安全 |
适用场景 | 查询多、增删少 | 频繁头尾操作 | 键值对快速存取 |
扩容机制 | 1.5倍 | 无固定扩容 | 2倍，负载因子0.75 |
五、高频面试问题
Q1：HashMap为什么用红黑树不用AVL树？
- 红黑树优势：插入删除操作旋转次数更少（最多3次）树高约束较宽松（黑高度平衡）适合读多写少场景
Q2：HashMap如何解决哈希冲突？
- 链地址法：相同桶位置形成链表/树
- 再哈希法：通过扰动函数优化哈希值分布
- 扩容机制：减少单个桶的冲突概率
Q3：ArrayList与LinkedList性能对比误区
- 实际测试结果（百万次操作）：
操作 |
|
|
|
|
|
|
|
|
|
|
|
六、最佳实践建议
- ArrayList初始化：预估数据量设置初始容量
- HashMap优化：
// 避免频繁扩容
Map map = new HashMap<>(expectedSize);
// 或使用Guava工具
Maps.newHashMapWithExpectedSize(100); 遍历选择：ArrayList优先用for循环，LinkedList必须用Iterator，HashMap遍历entrySet效率最高
通过深入理解这些集合的底层实现，可以更高效地进行Java程序开发与性能优化。