ArrayList源码分析
本文基于JDK1.8源码分析来分析，ArrayList顾名思义，数组的结构来表示一个List，先上一张图抛砖引玉：
arraylist结构
这张图表示的就是申请了容量
capacity为10的array buffer，但是有效容量size为1的情况。开始分析源码：
1. 属性及构造方法
先来看他的几个属性和构造方法：
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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;
}
}
相信大家看完这个代码的第一个疑问肯定是为什么要搞两个空Object数组出来。
EMPTY_ELEMENTDATADEFAULTCAPACITY_EMPTY_ELEMENTDATA
这两个都是空数组，其实要搞清楚这个问题看一下他们分别在什么地方使用就好了。
1、首先是EMPTY_ELEMENTDATA，他所有被使用的地方都是在初始化的时候size为0的时候被赋值给elementData，所以它的作用就是在size为0的时候不用去创建一个空数组了，而是提前创建好了放在那儿，方便被使用。
2、再看DEFAULTCAPACITY_EMPTY_ELEMENTDATA，他被使用的场景是在默认构造方法的时候被赋值给elementData，然后在add扩容的时候，被用来做判断。也就是说它的意义是告诉后面的代码当前是空的，需要被扩容成默认大小DEFAULT_CAPACITY = 10。
其实深一点说它的作用是做一个时间上的延后处理，我们每次new ArrayList()的时候其实这个时候并没有给我们申请内存，只有在add的时候才会申请10个内存空间，它的意义在这里。
那我们来看构造方法，三个构造方法，其实没什么好说的，看完上面我们的一个解释其实大家应该好理解了。
这里要注意的是如果我们调用了一个new ArrayList(20)，是直接申请了一个20的数组，而不是从0开始扩容，即使是new了一个ArrayList(Integer.MAX_VALUE)也是这样，并没有触发扩容，后面add的时候才会扩容。
好的，那既然是集合类，那我们分别来看它的增删改查方法~
2. add
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
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;
}
四个add方法，分为两种用法：
add单个addAll
我们发现这些方法都调用到了一个叫做ensureCapacityInternal的方法，下面看它的代码：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//初始化成DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时候容量赋值成DEFAULT_CAPACITY
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //①
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) //②
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? //④
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
首先先回顾一下上面我们说的add的时候关于赋值成
DEFAULTCAPACITY_EMPTY_ELEMENTDATA用来做延后申请内存的知识，在calculateCapacity方法里面.
2.1. 扩容
下面就到了ArrayList的核心方法grow扩容。
我们先从最不边界的情况看起，先了解一个最简单的扩容机制，capacity容量和size都为10的时候再add一个是怎么触发grow的，grow方法里面真正起作用的就是下面两句了。
// 15 = 10 + (10 >> 1) = 10 + 5
int newCapacity = oldCapacity + (oldCapacity >> 1);
//拷贝数据
elementData = Arrays.copyOf(elementData, newCapacity);
看起来也不难，那其实写东西理清了思路逻辑就那么一点，其实真正难处理的和容易出问题的都在边界上。我们看到在grow方法里面有一些if来解决边界条件，我在上面的if后面标了①②③④的注释，我们分别看一下能触发这些if的条件。
①、因为每次都会调用查看是否需要扩容，那判断只有大于elementData.length的时候才需要扩容。
②，这句是说oldCapacity扩容1.5倍之后如果比需要的minCapacity还要小，那就直接用minCapacity作为newCapacity来做扩容。这个其实很好理解，在addAll的时候如果需要add的集合很大的时候就会出现这种情况，比如：
List src = new ArrayList(10);
List tar = new ArrayList(10);
src.addAll(tar);
那很明显oldCapacity = 10; 扩容1.5后newCapacity = 15，而minCapacity = 20。
③④，这俩其实是一起的。如果扩容后的newCapacity大于MAX_ARRAY_SIZE，也就是大于Integer.MAX_VALUE - 8或者干脆大于Integer.MAX_VALUE最大值，这个时候就直接赋值为Integer.MAX_VALUE。
这个时候其实我们还注意到hugeCapacity这里有这么一个判断：
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
那什么时候会小于零呢？我们知道java里面int是没有所谓的unsigned的概念的，也就是无符号的概念。这里可以看一下我写过的一篇文章一次与或非操作实战，也就是说超过了Integer.MAX_VALUE就变成负数了。所以如果请求的超过最大值就直接抛OOM了。
那其实看完扩容，add就很简单了，不解释了，直接上图。
2.2. add(E e)
add单个元素：
2.3. add(int index, E element)
2.4. Collection<? extends E> c
这里需要注意的是addAll的时候，不管被add的List的size是多大的，只会扩一次容。一次性到需要的capacity。
3. get set
那其实getset就简单的很了，没几句代码，因为是ArrayList，优势就是在能够以O(1)的时间复杂度找到需要的位置，很简单就不解释了。
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
4. 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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
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; // clear to let GC do its work
}
那看代码来说，remove(int index)跟remove(Object o)绝对是效率不一样的，一个O(1)一个是O(n)。这是remove单个的时候，就是找到需要移除的index的方式不一样，那找到之后的工作量都是由System.arraycopy来完成的，附图：
remove one
那removeAll的代码如下
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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++)
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;
}
我也是在看的时候才发现有retainAll这么个方法，跟removeAll的区别只有一个标志位。那意义就是完全相反的，我们知道removeAll是把目标集合全部移除掉，retainAll刚好相反，是只保留目标集合里的元素.
就比如说有listA: [0, 1, 2, 3, 4]，同时有listB: [1, 2, 3]。
listA.removeAll(listB) => listA: [0, 4]
listA.retainAll(listB) => listA: [1, 2, 3]
那我们来看removeAll，complement为false，关键方法batchRemove，这里面有两个变量r和w，我们还是拿listA.removeAll(listB)来举例子：
r会循环0 ... 4，
- 第一遍循环，
r= 0且w = 0，这时listB包含elementData[0]=0不成立，所以把elementData[0]赋值给elementData[w=0]，然后w++之后w = 1 - 第二遍循环，
r= 1且w = 1，这时listB包含elementData[1] = 1成立，不做赋值 - 第三遍循环，
r= 2且w = 1，这时listB包含elementData[2] = 2成立，不做赋值 - 第四遍循环，
r= 3且w = 1，这时listB包含elementData[3] = 3成立，不做赋值 - 第五遍循环，
r= 4且w = 1，这时listB包含elementData[4] = 4不成立，elementData[4]赋值给elementData[w=1]，然后w++之后w = 2
循环结束。这时候removeAll操作就完成了。retainAll的操作就是刚好相反，下面附一张图，更直观：
removeAll
