JAVA源码系列-ArrayList
前言
ArrayList是一个基于数组的数据结构，Java1.8版本加入了Lambda匿名内部类的新特性。而ArrayList实现了java.util.function的接口，进而为了支持Lambda表达式的应用。对于集合类来说，集合内部扩容机制，数据结构，并发场景，锁机制是我们日常所要面对思考的。废话不多说，现在我们来解析一下ArrayList的源码。
- * 概述：
- * List接口可调整大小的数组实现。实现所有可选的List操作，并允许所有元素，包括null，元素可重复。
- * 除了列表接口外，该类提供了一种方法来操作该数组的大小来存储该列表中的数组的大小。
- * 时间复杂度：
- * 方法size、isEmpty、get、set、iterator和listIterator的调用是常数时间的。
- * 添加删除的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。
- * 容量：
- * 每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10。
- * 容量可以自动增长。
- * 如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。
- * 也可以通过带初始容量的构造器初始化这个容量。
- * 线程不安全：
- * ArrayList不是线程安全的。
- * 如果需要应用到多线程中，需要在外部做同步
- * modCount：
- * 定义在AbstractList中：protected transient int modCount = 0;
- * 已从结构上修改此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。
- * 此字段由iterator和listiterator方法返回的迭代器和列表迭代器实现使用。
- * 如果意外更改了此字段中的值，则迭代器（或列表迭代器）将抛出concurrentmodificationexception来响应next、remove、previous、set或add操作。
- * 在迭代期间面临并发修改时，它提供了快速失败 行为，而不是非确定性行为。
- * 子类是否使用此字段是可选的。
- * 如果子类希望提供快速失败迭代器（和列表迭代器），则它只需在其 add(int,e)和remove(int)方法（以及它所重写的、导致列表结构上修改的任何其他方法）中增加此字段。
- * 对add(int, e)或remove(int)的单个调用向此字段添加的数量不得超过 1，否则迭代器（和列表迭代器）将抛出虚假的 concurrentmodificationexceptions。
- * 如果某个实现不希望提供快速失败迭代器，则可以忽略此字段。
- * transient：
- * 默认情况下,对象的所有成员变量都将被持久化.在某些情况下,如果你想避免持久化对象的一些成员变量,你可以使用transient关键字来标记他们,transient也是java中的保留字(JDK 1.8)
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;
|
数组大小 |
|
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; |
数组长度最大值 |
以上可以清楚的认识到ArrayList是一个初始为空的Object数组了，与我们所定义的数组相同，它本身也是必须有固定长度的数组，并且数组中的缓存元素的值不能被序列化（被transient修饰）。下面来看一下ArrayList的构建过程。
ArrayList的构建过程
//带有初始大小的有参构造器
public ArrayList(int initialCapacity) {
// 如果初始化时ArrayList大小大于0
if (initialCapacity > 0) {
// new一个该大小的object数组赋给elementData
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果大小为0
// 将空数组赋给elementData
this.elementData = EMPTY_ELEMENTDATA;
} else {// 小于0
// 则抛出IllegalArgumentException异常
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
//不带参数的构造方法
public ArrayList() {
// 直接将空数组赋给elementData
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}通过以上代码，可以看到构建ArrayList的过程就是构建一个Object数组的过程。
ArrayList添加元素过程
//添加一个值到数组的末尾，首先会确保容量
public boolean add(E e) {
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将e赋值给elementData的size+1的位置
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果数组为空，则选取默认容量和数组大小两者中的最大值
//即如果默认容量为10，那么前十个元素的插入不会进行验证
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果最小需要空间比elementData的内存空间要大，则需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 获取到ArrayList中elementData数组的内存空间长度
int oldCapacity = elementData.length;
// 扩容到原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 判断一下新数组的长度容量够不够，够了就直接使用这个长度创建数组
// 不够就将数组长度设置为需要的长度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判断预设值的大小是否超过了默认的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 调用Arrays.copyOf方法将elementData数组指向新的内存空间时newCapacity的连续空间
// 并将elementData的数据复制到新的内存空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 检查是否溢出，若没有溢出，返回最大整数值(java中的int为4字节，所以最大为0x7fffffff)或默认最大值
*
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}如果还觉得有些涩会难懂，我们不如画张图来理解
此外，其他的对ArrayList的方法，例如get、set、remove等都是相当于对数组的操作，所以不在此赘述。
在ArrayList中并没有对线程安全问题进行解决，所以ArrayList是默认非线程安全的集合类。(希望后来者能少走弯路吧！所有的意见和建议我都会在第一时间回复。)
下一篇： ecmascript 是什么