您好,登录后才能下订单哦!
# Java集合中ArrayList源码解析是怎样的
## 一、ArrayList概述
### 1.1 ArrayList基本特性
ArrayList是Java集合框架中最常用的动态数组实现,位于`java.util`包中。作为List接口的可变数组实现,它提供了所有可选的列表操作,并允许存储所有元素(包括null)。
主要特点:
- **动态扩容**:容量自动增长以适应新增元素
- **非线程安全**:多线程环境下需要外部同步
- **快速随机访问**:基于数组实现,get/set操作时间复杂度O(1)
- **插入删除成本高**:平均时间复杂度O(n)
### 1.2 类继承关系
```java
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
关键接口实现:
- RandomAccess
:标记接口,支持快速随机访问
- Cloneable
:支持浅克隆
- Serializable
:支持序列化
transient Object[] elementData; // 实际存储元素的数组
private int size; // 当前元素数量
transient
修饰符表示序列化时此字段不会被自动处理elementData.length
,数组实际长度size
,当前存储的元素数量private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException(...);
}
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
private Object[] grow() {
return grow(size + 1);
}
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(
oldCapacity,
minCapacity - oldCapacity, // 最小增长量
oldCapacity >> 1); // 默认增长50%
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
扩容策略:
1. 首次添加元素时扩容到DEFAULT_CAPACITY(10)
2. 后续每次扩容为原容量的1.5倍
3. 使用Arrays.copyOf
进行数组复制
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index, elementData, index + 1, s - index);
elementData[index] = element;
size = s + 1;
}
modCount
用于快速失败机制(fail-fast)public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null; // 清除引用,帮助GC
}
private class Itr implements Iterator<E> {
int cursor; // 下一个元素索引
int lastRet = -1; // 最后返回的元素索引
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
快速失败机制通过比较modCount
和expectedModCount
实现
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
System.arraycopy
高效复制数据public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
trimToSize()
释放多余空间List list = Collections.synchronizedList(new ArrayList<>());
特性 | ArrayList | Vector |
---|---|---|
线程安全 | 非线程安全 | 线程安全 |
扩容策略 | 增长50% | 增长100% |
迭代器 | 快速失败 | 安全失败 |
性能 | 更高 | 较低 |
ArrayList作为Java集合框架的核心实现: 1. 基于动态数组实现,支持快速随机访问 2. 自动扩容机制平衡了空间和时间效率 3. 非线程安全设计带来了更好的单线程性能 4. 合理的初始化容量能显著提升性能
理解其底层实现有助于: - 正确选择和使用集合类 - 编写更高效的Java代码 - 在面试中展现扎实的基础知识
本文基于JDK 17源码分析,不同版本实现可能略有差异 “`
注:由于篇幅限制,这里提供的是精简后的核心内容框架。实际5400字文章需要: 1. 补充更多方法实现的详细解析 2. 增加性能测试数据对比 3. 添加更多使用示例和注意事项 4. 扩展与其他集合类的对比分析 5. 增加内存布局和GC影响的讨论
需要完整长文可告知具体扩展方向。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。