基于jdk1.8 的ArrayList的源码分析
基于jdk1.8 的ArrayList的源码分析
作者：Orange_橙子先生
前言：一说到ArrayList的大家可能立马想到的就是：有序、可重复、查找快但是增删慢、线程不安全。但是具体的原因都不是很清楚，本文就会根据这些问题和大家一起去学习。主要会从ArrayList的构造方法、增加元素、删除元素、获取元素、查询元素、清空元素、判断元素是否存在以及ArrayList的遍历进行入手分析。
一：ArrayList的具体实现 1.1：构造函数ArrayList list = new ArrayList();
ArrayList list2 = new ArrayList(10);
1.2：成员变量
//默认初始化的容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
//共享的空数组实例，用于默认大小的空实例。这个上面的区别在于这个有默认的容量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储ArrayList的元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
//任何具有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList添加第一个元素时，
//将扩展 为DEFAULT_CAPACITY。
transient Object[] elementData;
//ArrayList的大小（它包含的元素数）。
private int size;
解析：transient这个字段当对象被序列化时（写入字节序列到目标文件）时，transient阻止实例中那些用此关键字声明的变量持久化；当对象被反序列化时（从源文件读取字节序列进行重构），这样的实例变量值不会被持久化和恢复。
//方法一：
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("Illegal Capacity: "+
initialCapacity);
}
}
解析：这两个方法基本是一样的，区别的在于一个有默认的容量，一个是空的数组。从这里我们可以看出来ArrayList底层是通过数组来实现的，因为这里真正存储元素的是通过elementData数组来实现的。
//方法三：（不常用）
public ArrayList(Collection 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;
}
}
解析：第三个方法我们使用的很少，这里也做一点解析。这里主要通过Collection.toArray()方法得到一个对象数组，然后赋值给elementData，通过判断数组的长度来进行初始化。首先把数组的长度赋值给size，接着做判断，如果数组的长度不为空的话，那么就通过Arrays.copyOf() 来复制集合c中的元素到elementData数组中，如果为空的话，那么就会将EMPTY_ELEMENTDATA空数组赋值给elementData。下面进到Arrays.copyOf()方法中去看一眼。
public static T[] copyOf(U[] original, int newLength, Class newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
解析：这里主要是通过传输过来的数组、以及size来完成从旧数组到新数组的拷贝过程。首先会根据Class类型来判断是new对象还是通过反射来创造对象并放置到新的数组中。接着就是数组拷贝的一个过程，System.arraycopy()源码如下：
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
解析：这个方法下面会一直使用，弄明白后在研究下面的内容。这里具体的实现就是，将src数组从下标为srcPos的元素开始拷贝，拷贝length个元素到dest数组中去，dest数组从destPos下标开始加入元素。需要注意的是：src 和 dest都必须是同类型或者可以进行转换类型的数组。
1.4：增加元素增加元素有如下四种：我们逐一进行分析。
arrayList.add(Object element); boolean
arrayList.add(int index, Object element); void
arrayList.addAll(Collection c); boolean
arrayList.addAll(int index,Collection c); boolean
1.4.1：arrayList.add(Object element)源码解析：
//表示int的最小值
public static final int MIN_VALUE = 0x80000000;
//表示int的最大值
public static final int MAX_VALUE = 0x7fffffff;
//要分配的最大数组大小。
//数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8字节。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
public boolean add(E e) {
//赋值初始长度，判断是否扩容，当前长度为 size+1
ensureCapacityInternal(size + 1); // Increments modCount!!
//新增元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果数组长度为0，就会在10和size+1中选择一个大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
//记录修改次数(默认为0)，迭代中不一致会触发fail-fast机制,因此在遍历中删除元素应该使用Iterator.remove()
modCount++;
// overflow-conscious code
//如果初始长度大于元素的长度就需要扩容
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
//旧容量
int oldCapacity = elementData.length;
//新容量 = 旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果新容量小于一开始指定的容量，就把开始的容量赋值给新容量
if (newCapacity - minCapacity 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//数组的转换赋值，上面有提到过
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
//如果初始指定容量小于0，直接报错
if (minCapacity MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
1.4.2：arrayList.add(int index, Object element)源码解析：
public void add(int index, E element) {
//判断数组是否会下标越界
rangeCheckForAdd(index);
//赋值初始长度，判断是否扩容，当前长度为 size+1 (上面已经详细解析过)
ensureCapacityInternal(size + 1); // Increments modCount!!
//将原来的数组中从index位置开始后的size-index个元素统一后移一位，给新来的元素腾出位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在腾出来的位置上赋值
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
//如果小标大于数组现有的size或者下标小于0，则跑抛出下标越界异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1.4.3：arrayList.addAll(Collection c)源码解析：
public boolean addAll(Collection c) {
//转换成数组
Object[] a = c.toArray();
int numNew = a.length;
//赋值初始长度，判断是否扩容，当前长度为 size+ numNew (上面已经详细解析过)
ensureCapacityInternal(size + numNew); // Increments modCount
//将该collection中的所有元素添加到此列表的尾部
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
1.4.4：arrayList.addAll(int index, Collection c)源码解析：
public boolean addAll(int index, Collection c) {
//判断下标是否越界
rangeCheckForAdd(index);
//转换成数组
Object[] a = c.toArray();
int numNew = a.length;
// //赋值初始长度，判断是否扩容，当前长度为 size+ numNew (上面已经详细解析过)
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
//当数组的size大于index的时候，将源数组中从index位置开始的后numMoved个元素统一后移numNew位
//然后将新的数组就会占用index到index+numNew的位置
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
综上所述：arrayList在新增数据的时候，涉及到索引的时候会判断下标是否会越界，正常情况下都会判断是否需要扩容，扩容的话，每次会扩原来的1.5倍，但是当新扩展数组大小已经达到了最大值时，就会取到最大值。
1.5：删除元素删除元素常用的有如下三种，我们逐一进行分析：
arrayList.remove(Object o); boolean
arrayList.remove(int index); String
arrayList.removeAll(Collection c); boolean
1.5.1：arrayList.remove(Object o) 的源码解析：
public boolean remove(Object o) {
//arrayList里面可以存储null，所以做了如下判断
//所删元素为null
if (o == null) {
//找到第一个需要删除的元素，
//因为arrayList可以存储相同的元素，所以删除的是第一个
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
//所删元素不是null
for (int index = 0; index 0)
//数组的赋值操作，将数组elementData中index位置之后的所有元素向前移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//交给GC去处理末尾的空数据
elementData[--size] = null; // clear to let GC do its work
}
1.5.2：arrayList.remove(int index) 的源码解析：
public E remove(int index) {
//检查下标是否越界
rangeCheck(index);
modCount++;
//记录返回删除的元素
E oldValue = elementData(index);
//检查删除元素的合理性
int numMoved = size - index - 1;
if (numMoved > 0)
//将原数组的index之后的元素全部往前移一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//交给GC去处理末尾的空数据
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
1.5.3：arrayList.removeAll(Collection c) 的源码解析：
//把arrayList中的包含c里面的元素全部删掉
public boolean removeAll(Collection c) {
//检查c是否为空
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public static T requireNonNull(T obj) {
//如果为空就直接抛空指针异常
if (obj == null)
throw new NullPointerException();
return obj;
}
private boolean batchRemove(Collection c, boolean complement) {
//用来存储过滤后的元素
final Object[] elementData = this.elementData;
//双指针，r 用来遍历，w 用来记录过滤后元素的个数
int r = 0, w = 0;
//用来记录这次是否有修改，有修改会返回true
boolean modified = false;
try {
for (; r < size; r++)
//1:complement参数传入就是false
//2:如果c中包含数组中的值，那么只有 r 在自增，如果c中不包含数组中的值，那么 r 和 w 都在自增
//3:就是一个往前赋值的过程。
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//一般情况下 r 会等于 size，当出现异常的时候，则会导致 r !=size
//则将出现异常处后面的数据全部复制覆盖到数组里。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//当 w 不等于 size 的时候说明有数据被删除了
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
// w 记录了过滤后元素的个数，所以后面的数据就可以置为null交给GC处理
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
1.6：修改元素
arrayList.set(int index, E element)
1.6.1：arrayList.set( int index, E element)的源码解析：
public E set(int index, E element) {
//检查下标是否越界
rangeCheck(index);
//存储旧元素
E oldValue = elementData(index);
//在指定下标下覆盖旧值
elementData[index] = element;
//返回旧值
return oldValue;
}
1.7：获取元素
arrayList.get(int index);
1.7.1：arrayList.get(int index)的源码解析：
public E get(int index) {
//判断下标是否越界
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
//返回指定下标的元素
return (E) elementData[index];
}
1.8：清空元素
arrayList.clear();
1.8.1：arrayList.clear()源码解析：
public void clear() {
modCount++;
// clear to let GC do its work
//将全部的元素置为null，然后交给GC处理
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
1.9：是否包含指定元素
arrayList.contains(Object o);
1.9.1：arrayList.contains(Object o)源码解析：
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
//为null
if (o == null) {
//遍历找到为null的下标后返回
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//不为null，找到具体下标后返回
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//没有指定元素就返回 -1
return -1;
}
1.10：arrayList的迭代器iterator()方法
arrayList.iterator();
1.10.1：arrayList.iterator()迭代器的源码解析：
public Iterator iterator() {
return new Itr();
}
private class Itr implements Iterator {
//Itr实现了Iterator接口，得到了Iterator接口的hasNext、next方法
//记录下一个元素的下标
int cursor; // index of next element to return
//记录上一次元素的下标
int lastRet = -1; // index of last element returned; -1 if no such
//记录修改的次数
//当进到ArrayList的iterator方法时，expectedModCount就已经初始化了，但是当用户在进行
//add和remove的时候modCount的值就会发生改变，下次比对的时候就不相等了，就会抛出并发修改异常
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
//如果下一个元素的下标不等于size说明还有元素
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//检查并发修改异常
checkForComodification();
int i = cursor;
//当i大于size或者数组的长度的时候就说明有并发操作导致，会抛出并发修改异常
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
//当修改次数，与期望的修改次数（调用iterator方法时候的修改次数）不一致的时候，就会发生并发修改异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
二：ArrayList相关问题的解析
2.1：ArrayList为什么查找快，增删慢？
解析：从源码我们可以看的出来，查找的时候直接找到相应下标元素就可以获取到具体元素后返回，但是增加元素可能会导致扩容机制，还会涉及到两个集合的赋值操作，因此会变慢。
2.2：ArrayList为什么时线程不安全的？解析：线程安全就是说多线程访问同一代码（对象、变量等），不会产生不确定的结果。 但是通过源码的解读我们可以看出来ArrayList.add()方法在使用的时候就会出现不确定的结果。
public boolean add(E e) {
//赋值初始长度，判断是否扩容，当前长度为 size+1
ensureCapacityInternal(size + 1); // Increments modCount!!
//新增元素
elementData[size++] = e;
return true;
}
从上面来看 elementData[size++] = e 就可能会导致线程不安全的问题，这一步可以拆分成两步完成
elementData[size] = e;
size = size + 1;
当多线程开始添加元素的时候，线程1号开始增加元素 A ，此时线程1号把元素A放在下标为0的位置上，线程2号此时进来也添加元素B，进来发现下标为0的位置上没有数据，线程2号也把数据放在了下标为0的位置，线程1号和2号继续他们的运行，接下来线程一号会将size增加到1，当线程2号再次进来的时候就会将size增加到2，但是此时的实际情况是size为2，但是下标为0的位置变成了B，下标为1的位置上为null，并且下次添加元素会从下标为2的位置上开始增加。 综上：ArrayList是线程不安全的。
2.3：如何规避ArrayList的线程不安全问题。解析：
第一种方法：使用Vertor集合
Vector arrayListSafe1 = new Vector();
第二种方法：使用Collections.synchronizedList
List list = new ArrayList();
//可以改成
List data=Collections.synchronizedList(new ArrayList());
至此，ArrayList的源码研究告一段落，欢迎大家一起讨论学习。
了解更多干货，欢迎关注我的微信公众号：爪哇论剑
作者：Orange_橙子先生
