正文
JDK1.8源码学习-ArrayList
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
JDK1.8源码学习-ArrayList
目录
一、ArrayList简介
为了弥补普通数组无法自动扩容的不足，Java提供了集合类，其中ArrayList对数组进行了封装，使其可以自动的扩容或缩小长度，相当于动态数组。
ArrayList封装了一个动态的可以重新分配的Object[]数组，其中每一个类的对象都有一个capacity属性，表示了它们所封装的Object[]数组的长度，当向ArrayList中添加元素的时候，该属性会自动的添加。如果想要添加大量元素的时候，可以使用ensureCapacity方法一次性增加capacity,减少数组的重新分配次数，提高效率。
二、ArrayList工作原理和数据结构
ArrayList 是基于数组来实现的
对于数组，这里就不进行过多叙述了。 想要说明的是ArrayList集合中底层数组元素的类型为Objec类型，即可以存放所有类型的数据。我们对ArrayList类的实例的操作，也都是基于数组的。
三、ArrayList源码分析
3.1、继承关系分析
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList继承自AbstractList,实现了List、RandomAccess、Cloneable、Serializable接口，其中List中定义了一些基本的增删查改的功能,实现RandomAccess接口则具有随机读写的功能，实现了Cloneable接口，可以被克隆，实现了Serializable可以使ArrayList实现序列化。
3.2、成员变量分析
//定义的序列化id，主要是为了标识不同版本的兼容性
private static final long serialVersionUID = 8683452581122892189L;
//默认的数组存储容量为 10
private static final int DEFAULT_CAPACITY = 10;
//当指定数组的容量为0的时候使用这个变量赋值，空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认的实例化的时候使用此变量赋值，空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正存放数据的对象数组，并不被序列化 （前面加有transient关键字）
transient Object[] elementData;
//数组中的真实元素个数它小于或等于elementData.length
private int size;
//数组中最大存放元素的个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
3.3、构造函数分析
3.3.1无参构造函数
ArrayList无参构造函数，默认初始化容量是10。
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //默认值：10
}
在这里注释上说明构造一个容量为10的空的list，但是并没有看到数组的容量变为10，而是一个空的数组，实际上当有元素被加入(add方法)的时候，才会被初始化为10的数组。
3.3.2传入初始化容量构造函数
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);
}
}
创建一个initialCapacity大小的数组。
3.3.3传入初始化元素的构造函数
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//判断引用的数组类型，并将引用转换成Object数组引用
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//替换为空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
传入一个集合类(Collection的子类即可)，转为list。
总结：可以看出ArrayList的内部存储结构就是一个Object类型的数组，因此它可以放任意类型的元素。在构造ArrayList的时候，如果传入初始大小，那么它将新建一个指定容量的Object数组，如果不设置初始大小，那么它将不会分配内存空间而是使用对象数组，在实际要放入元素的时候再进行内存分配。
3.4、add()方法分析
ArrayList中提供了四种方式的添加：1.直接添加；2.指定位置添加；3.添加全部；4.在指定位置添加全部。
1.直接添加
public boolean add(E e) {
//添加前先检查是否需要拓展数组, 此时数组长度最小为size+1
ensureCapacityInternal(size + 1);
//将元素添加到数组末尾
elementData[size++] = e;
return true;
}
add(E e)调用涉及的方法：
1.private void ensureCapacityInternal(int minCapacity) {
//判断数组是不是一个长度为0的空数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果是的话则给容量赋值为默认的容量大小10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
2. private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//判断当前容量是否大于数组当前的长度
if (minCapacity - elementData.length > 0)
//如果数组容量过小则进行扩容
grow(minCapacity);
}
3.private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//扩容的长度是增加了原来数组的一半大小
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断是否达到了数组扩容的上限
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//把旧数组里面的数据拷贝到新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
4.private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
//如果minCapacity还大于MAX_ARRAY_SIZE,那么就将Integer.MAX_VALUE返回,反之将MAX_ARRAY_SIZE返回。
//因为maxCapacity是三倍的minCapacity,可能扩充的太大了,就用minCapacity来判断了。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
2.指定位置添加
public void add(int index, E element) {
//插入位置范围检查
rangeCheckForAdd(index);
//检查是否需要扩容
ensureCapacityInternal(size + 1);
//挪动插入位置后面的元素（将elementData中的元素从index开始，拷贝到index+1的位置，拷贝size-index个元素）
System.arraycopy(elementData, index, elementData, index + 1, size - index);
//在要插入的位置赋上新值
elementData[index] = element;
size++;
}
在指定位置进行添加，必然会影响到该位置的元素以及后续元素，因为是数组结构，所以只能进行元素的后移了，同时要首先检查入参的元素的位置(index)是否在范围内。
其中System.arraycopy(Object src,int srcPos,Object dest,int destPos,int length)方法中的参数的含义：src(原数组)、srcPos(从原数组的起始位置开始)、dest(目标数组)、destPos(目标数组的起始位置)、length（要copy的数组的长度）
3.添加一个集合中的全部元素
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal(size + numNew);
//进行元素拷贝
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
4.在指定位置上添加一个集合中的全部元素
public boolean addAll(int index, Collection<? extends E> c) {
//插入位置范围检查
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
//检查是否需要扩容
ensureCapacityInternal(size + numNew);
//复制元素的个数
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
3.5、set()方法分析
修改的方法比较简单，就是给数组的下标重新赋值。
public E set(int index, E element) {
//index不能大于size
rangeCheck(index);
E oldValue = elementData(index);
//替换成新元素
elementData[index] = element;
return oldValue;
}
确保set的位置(index)小于当前数组的长度(size)并且大于0，获取指定位置（index）元素，然后放到oldValue中存放，将需要设置的元素放到指定位置(index)上。
3.6、remove()方法分析
1. E remove(int index):根据下标进行删除
public E remove(int index) {
// 检查下标是否越界
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
//最后 -1 是为了数组下标不越界
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //置空引用，让GC进行回收
return oldValue;
}
2.boolean remove(Object o):根据传入对象进行删除
// 删除成功返回true, 失败false
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
} // 快速删除指定下标的元素, 无越界检查
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //置空引用,让GC进行回收
}
3. boolean removeAll(Collection<?> c):根据传入集合进行删除
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 如果complement为false, 则c集合包含本集合中的元素, 则不进行操作, 这就是保留不属于c集合中的所有元素.
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
如果传入的集合c中包含本集合中的元素，则对元素进行处理，把匹配的元素（c.contains(elementData[r])==complement）进行保留，不需要保留的下标置为null，其中利用complement属性，来决定含有的元素是删除还是保留。
3.7、get()方法分析
public E get(int index) {
//检查是否越界
rangeCheck(index);
//返回指定位置上的元素
return elementData(index);
}
四、ArrayList总结
1、ArrayList底层实现是基于数组的，因此对指定下标的查找和修改比较快，但是删除和插入操作比较慢。
2、构造ArrayList的时候尽量指定容量，减少扩容所带来的数组复制操作，如果不知道大小可以采用默认值10。
3、每次添加元素之前会检查是否需要扩容，每次扩容都是增加原有容量的一半。
4、ArrayList中的所有的方法都没有进行同步，因此它不是线程安全的。
5、在查找给定元素索引值等方法中，源码都将该元素的值分为null和不为null两种情况进行处理，ArrayList中允许元素为null。
