ArrayList源码分析
ArrayList源码分析
源码解析第一步：简单了解其特性
ArrayList是可重复,有顺序的,其内部实现是数组.随机读取速度快,插入删除慢,
源码解析第二步：提出自己的疑问，带着问题去读源码
- ArrayList是怎么扩容的?
- ArrayList是如何实现有序的?
- ArrayList为什么读取速度快,而插入删除慢?
- ArrayList是会因为删除而容量减小吗?
- ArrayList的set()可以随机插入数据吗?
源码解析第三步：解读其继承与实现
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
它继承了AbstractList抽象类，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
继承AbstractList抽象类,主要就是抽象出一些共有方法,例如:add()/get()/set()/remove()/clear()
RandomAccess只是标记接口，用来表明其支持快速（通常是固定时间）随机访问.
Cloneable(浅克隆)表示当前类的实例可被克隆,ArrayList的clone方法:
public Object clone() { try { ArrayList<?> v = (ArrayList<?>) super.clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }此处使用的是浅克隆,因为具体elementData中的对象是没有被克隆的,所以它只能是浅克隆.
关于深克隆和浅克隆:
浅克隆是指拷贝对象时仅仅拷贝对象本身（包括对象中的基本变量），而不拷贝对象包含的引用指向的对象。
深克隆不仅拷贝对象本身，而且拷贝对象包含的引用指向的所有对象。
如何实现克隆 :
- 对象的类实现Cloneable接口；
- 覆盖Object类的clone()方法 （覆盖clone()方法，访问修饰符设为public，默认是protected）；
- 在clone()方法中调用super.clone()；
总结 : 浅拷贝在拷贝时,遇到引用对象的时候不会再次拷贝,而是直接引用.深拷贝在遇到引用对象时,会重新复制出一个新的对象.
Object中有一个clone方法，为什么还必须要实现Cloneable接口呢?
这就是cloneable接口这个标志接口的意义，只有实现了这个接口才能实现复制操作，因为jvm在复制对象的时候，会检查对象的类是否实现了Cloneable这个接口，如果没有实现，则会报
CloneNotSupportedException异常。为什么要重写clone()？
如果一个目标类应用了Clonable接口但并未重写clone()方法，它“看起来”像是可以克隆。但一般不这么做，理由如下：
- 如果不重写，在不同包下，由于Object根类clone()是protected修饰的，别的类即使用目标类的对象也不能访问目标类继承的clone()方法，只能在目标类范围内使用，局限性大，这也是为什么一般重写都扩大成public范围。
- Object.clone()只是提供了浅层拷贝，对于基本类型的字段，可以说它成功克隆了。但对于对象型字段，它并没有实现克隆的功能，仅仅把对象的引用复制了，并没有创建新的对象，所以含有对象类型的话要“定制”完成深度克隆。
Serializable允许ArrayList可以序列化,Serializable 用来标识当前类可以被 ObjectOutputStream 序列化，以及被 ObjectInputStream 反序列化。
序列化与反序列化的目的?
序列化：得到的字节序列可以方便在网络上传输或者持久化——编码。
反序列化：主要从网络/磁盘读取读取字节序列然后转化为对象或者数据结构。——解码
Serializable 接口的基本使用
通过 ObjectOutputStream 将需要序列化数据写入到流中，因为 Java IO 是一种装饰者模式，因此可以通过 ObjectOutStream 包装 FileOutStream 将数据写入到文件中或者包装 ByteArrayOutStream 将数据写入到内存中。同理，可以通过 ObjectInputStream 将数据从磁盘 FileInputStream 或者内存 ByteArrayInputStream 读取出来然后转化为指定的对象即可。
Serializable 接口的特点
1. 序列化类的属性没有实现 Serializable 那么在序列化就会报错java.io.NotSerializableException
2. 在反序列化过程中，它的父类如果没有实现序列化接口，那么将需要提供无参构造函数来重新创建对象。
3. 一个实现 Serializable 接口的子类也是可以被序列化的。
4. 静态成员变量是不能被序列化
5. transient 标识的对象成员变量不参与序列化
6. Serializable 在序列化和反序列化过程中大量使用了反射，因此其过程会产生的大量的内存碎片
Externalizable 接口
Serializable 接口内部序列化是 JVM 自动实现的，如果我们想自定义序列化过程，就可以使用
Externalizable接口来实现
源码解析第四步：了解其成员变量
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 用于默认大小的空实例的共享空数组实例。
* 我们将其与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时扩容多少。
* MARK:无参构造函数使用该数组初始化,与EMPTY_ELEMENTDATA的区别主要是区分作用，EMPTY_ELEMENTDATA用来减少空数组的存在，优化内存使用1.8后的优化
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 实际数据的存储数组
transient Object[] elementData; // non-private to simplify nested class access
// 长度
private int size;
ArrayList中EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别
EMPTY_ELEMENTDATA : 用来取代多个elementData置为{}的情况,防止创建很多空数组
DEFAULTCAPACITY_EMPTY_ELEMENTDATA : 无参构造时,使用{}进行初始化
源码解析第五步：了解其构造器
-
无参构造器
public ArrayList() { //初始化数据 = {} this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }将elementData设置为空
-
ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }将传入的集合转换为数组,复制数据.
-
ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity); } }
源码解析第六步：阅读源码，寻找答案
1. ArrayList是怎么扩容的?
(1) 确保内部容量ensureCapacityInternal()。
private void ensureCapacityInternal(int minCapacity) {
// calculateCapacity(elementData, minCapacity) 获取默认的容量和传入参数的较大值
// ensureExplicitCapacity 检查是否需要扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
(2) 检查是否需要扩容ensureExplicitCapacity()
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 这个用来确保迭代器正常使用的字段
// overflow-conscious code
// 如果最小容量减去elementData的长度 > 0
if (minCapacity - elementData.length > 0)
// 已经真正开始扩容了
grow(minCapacity);
}
分析 :
- 当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了
ensureCapacityInternal()方法 ，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)方法。 - 当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，
minCapacity - elementData.length > 0不成立，所以不会进入 （执行）grow(minCapacity)方法。 - 添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
(3) 扩容grow()
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新容量扩容为 : 原容量 + 原容量/2 = 1.5倍原容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
//如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
(4) hugeCapacity()
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
System.arraycopy() 和 Arrays.copyOf()方法
System.arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置copyOf()是系统自动在内部新建一个数组，并返回该数组。
Arrays.copyOf()实际调用了System.arraycopy()方法,主要是为了给原有数组扩容.
2.ArrayList是如何实现有序的?
public boolean add(E e) {
// 确保容量
ensureCapacityInternal(size + 1); // Increments modCount!!
// 默认add方法是在size后插入数据 , 又因为数组的数据结构,所以它可以保证插入顺序
elementData[size++] = e;
return true;
}
3.ArrayList为什么读取速度快,而插入删除慢?
(1) 首先看一下get()
public E get(int index) {
rangeCheck(index);
// 直接使用索引从数组中拿,所以速度是很快的
return elementData(index);
}
// elementData(index)
E elementData(int index) {
return (E) elementData[index];
}
直接使用索引从数组中拿,所以速度是很快的
(2) add()和remove()
- add()
add() 增加至末尾
public boolean add(E e) {
// 如果扩容涉及复制
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
add() 增加至指定位置
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 插入时,可能索引位置在中间,所以使用arraycopy将后面的元素向后移动并复制
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
- remove()
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
// 删除指定索引位置的元素,后面的元素向前移动并复制
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后面的元素设置为空,等待GC释放资源
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
由此可见,不管是add()还是remove()都可能涉及复制数组,因此速度会慢一些.
4.ArrayList是会因为删除而容量减小吗?
不会。如果你需要减少数组列表的容量（通常不会使用）使用
trimToSize()。原因可能是因为每次改变容量的时候，都需要新建一个数组，然后把旧数组里面的元素复制到新数组里面去，这种操作是损耗性能的，而往往ArrayList里面的元素会经常会在一定范围内变化，因此这种操作将带来很大的性能损耗，我们为什么不能损耗一点内存来提高服务的响应速度呢？从这个角度来看，也是一种空间换时间的体现。另外，在新建ArrayList的时候，设置一个合理的容量也会对我们系统的服务性能有一定的帮助。
5.ArrayList的set()可以随机插入数据吗?
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
// rangeCheck()
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
不可以。从rangeCheck()我们可知,如果我们传入的index大于等于size这时会报错.
源码解析第七步：总结与思考
- ArrayList创建时实际是一个容量为10的数组；
- 容量不够时扩容1.5倍，1.5倍扩充速度最快；
- 添加元素时都是追加在数组末尾，所以实现了有序，可以重复；
- 访问时直接通过下标，效率较高；
- 增删时需要将数组复制到新数组（尽管是自己复制自己）；
- 转数组时其实是将现数组复制到新数组返回；
源码解析第八步：还有需要思考的?
转换数组 toArray（）
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
就是复制到新数组而已
清空 clear()
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
数组循环置为null ,size置为0.
通过索引区间删除 removeRange(int fromIndex, int toIndex)
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
其实也就是先复制,然后循环置为null