首页 > 代码库 > ArrayList源码分析
ArrayList源码分析
ArrayList的声明
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
泛型声明，继承于AbstractList，实现了若干个接口。
AbstractList是List的虚基类不多说，List接口是Colloection的子接口。
RandomAccess是List所实现的标记接口，用来表明其支持快速（通常是固定时间）随机访问。
随机访问我的理解就是通过索引（index）进行访问。
Cloneable也是标记接口，表示可以合法调用clone()方法而不抛出异常，clone()也会正常执行，复制所有自断。
Serializable表示可以被序列化和反序列化，在io中用来传递数据有用。
ArrayList的域
1 private static final long serialVersionUID = 8683452581122892189L; 2 3 private static final int DEFAULT_CAPACITY = 10; 4 5 private static final Object[] EMPTY_ELEMENTDATA = http://www.mamicode.com/{};>serialVersionUID是和Serializable接口配套使用的，用来确保序列化和反序列化的正常运行。
DEFAULT_CAPACITY默认初始化容量。容量是指尚未扩充前，最大存储数据的多少。
EMPTY_ELEMENTDATA 和DEFAULTCAPACITY_EMPTY_ELEMENTDATA 基本都是用作初始化时赋予的空的数组，区别只是在于添加首个元素的时候进行区分，参照下面。
elementData数组用作存储数据。
size表示已经占用了多少数据。
发现elementData是用transient修饰的，意思是不参与序列化过程，为什么要这样设计呢？
序列化过程中其实是调用了private void writeObject(java.io.ObjectOutputStream s)方法，
因为ArrayList中的elementData其实并不是全部都存放数据的，仅仅存放了size个数据，那如果全部用作序列化和反序列化会导致效率变低，
于是就只把实际存在的数据进行序列化就能使效率变高。
ArrayList的构造方法
1 public ArrayList() {2 this.elementData = http://www.mamicode.com/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;>无参的构造方法，将elementData设为空的数组，没有其他附加操作。
1 public ArrayList(int initialCapacity) { 2 if (initialCapacity > 0) { 3 this.elementData = http://www.mamicode.com/new Object[initialCapacity];"Illegal Capacity: "+ 8 initialCapacity); 9 }10 }带有一个int型参数的构造方法，设一个默认的初始化参数，构建一个以该参数长度为大小的空数组，
当设的参数不能作为数组的初始化参数时会抛出IllegalArgumentException。
1 public ArrayList(Collection<? extends E> c) { 2 elementData = http://www.mamicode.com/c.toArray();>带一个Collection型参数的构造方法，将Collection内的元素用c.toArray()转换为数组直接传给elementData。
当发现传入长度不为0的时候还要检测其类型是否正确转为Object[]，因为JDK编号6260652的BUG，若没有正确转换，还需要调用Arrays.copyOf(elementData, size, Object[].class);来进行转换。
当传入的是一个空的集合的时候将elementData设为默认空数组。
ArrayList的关键方法
1 public boolean add(E e) { 2 ensureCapacityInternal(size + 1); // Increments modCount!! 3 elementData[size++] = e; 4 return true; 5 } 6 7 public void add(int index, E element) { 8 rangeCheckForAdd(index); 9 10 ensureCapacityInternal(size + 1); // Increments modCount!!11 System.arraycopy(elementData, index, elementData, index + 1,12 size - index);13 elementData[index] = element;14 size++;15 }16 17 private void ensureCapacityInternal(int minCapacity) {18 if (elementData =http://www.mamicode.com/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {>添加元素的方法感觉十分容易，但是ArrayList的本质是数组，
添加一个元素有可能意味着数组越界，越界的解决方法就是将原来的数组扩容，这里层层调用了3个private方法。
首先调用ensureCapacityInternal(int minCapacity)，这个方法判断了该数组是否是用了无参的构造方法，如果是，就取默认的容量和现在要求的容量的较大值最为下个函数的参数。
ensureExplicitCapacity(minCapacity)判断要求的容量和当前容量的大小，即判断是否需要扩容，不需要扩容则直接添加，否则就调用扩容的核心方法。
grow(minCapacity)就是扩容的核心方法，
int newCapacity = oldCapacity + (oldCapacity >> 1);将新的容量（数组大小）设定成为旧的容量的1.5倍。
然后比较新的容量和请求的容量的大小，如果仍小于请求容量的大小，就把新容量改为请求容量的大小。
如果新的容量已经超过了ArrayList设置的最大容量大小private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
就把新的容量设置为最大的容量，最后调用Arrays.copyOf(elementData, newCapacity)把原来的数据复制到新扩容的数组中，数组长度为新的容量。
最后才是把指定的元素添加到所想要添加的位置上。
简单的public boolean add(E e)就仅仅是在最后一个元素后面添加，没什么好说的。
public void add(int index, E element)的添加若是在已有数据的中间添加，则需要将后面的元素逐个后移。
JDK采取的方法是调用System.arraycopy(elementData, index, elementData, index + 1,size - index);
这是个本地（native）方法，方法的用处是将index后size-index个数据复制到index+1后。
1 public boolean addAll(Collection<? extends E> c) { 2 Object[] a = c.toArray(); 3 int numNew = a.length; 4 ensureCapacityInternal(size + numNew); // Increments modCount 5 System.arraycopy(a, 0, elementData, size, numNew); 6 size += numNew; 7 return numNew != 0; 8 } 9 10 public boolean addAll(int index, Collection<? extends E> c) {11 rangeCheckForAdd(index);12 13 Object[] a = c.toArray();14 int numNew = a.length;15 ensureCapacityInternal(size + numNew); // Increments modCount16 17 int numMoved = size - index;18 if (numMoved > 0)19 System.arraycopy(elementData, index, elementData, index + numNew,20 numMoved);21 22 System.arraycopy(a, 0, elementData, index, numNew);23 size += numNew;24 return numNew != 0;25 }增加多个元素其实和增加单个元素的思路是相似的，都是先确保容量大小，
然后都是调用了System.arraycopy的方法进行添加和后移。
1 public E remove(int index) { 2 rangeCheck(index); 3 4 modCount++; 5 E oldValue = http://www.mamicode.com/elementData(index);>删除单个元素ArrayList提供了两个方法，一个是删除指定索引的方法，另一个则是删除ArrayList中第一次出现的特定对象（如果存在）。
删除指定索引的方法记录了一个numMoved，即需要移动的元素，和add一样是调用了System.arraycopy(elementData, index+1, elementData, index,numMoved);来将元素逐个向前移动。
最后把size减一的同时置为null留给GC来处理。
删除指定对象的方法都先是遍历整个ArrayList，找到对象的索引，然后调用一个fastRemove(int index)方法，
该方法和删除指定索引的方法基本相同（除了记录返回值和参数检测之外），就不再赘述了。
1 public void clear() {2 modCount++;3 4 // clear to let GC do its work5 for (int i = 0; i < size; i++)6 elementData[i] = null;7 8 size = 0;9 }删除所有元素和删除单个元素的思路是一样的，就是置为null，让GC去处理。
注意到删除元素并没有对数组的容量进行改变。
1 protected void removeRange(int fromIndex, int toIndex) { 2 modCount++; 3 int numMoved = size - toIndex; 4 System.arraycopy(elementData, toIndex, elementData, fromIndex, 5 numMoved); 6 7 // clear to let GC do its work 8 int newSize = size - (toIndex-fromIndex); 9 for (int i = newSize; i < size; i++) {10 elementData[i] = null;11 }12 size = newSize;13 }另外发现一个有趣的代码，删除从fromIndex到toIndex的所有元素，看上去是一个挺有用的功能，
但是令人感到奇怪的是他的修饰符居然是protected，意味着程序员无法在程序中直接调用，
其实是因为removeRange(int fromIndex, int toIndex)和sublist(int fromIndex,int toIndex).clear()方法的效果是相同的，
所以并不需要额外增加一个可以被调用的方法，那为什么还要设计这个方法呢？
首先要知道，这个方法是从AbstractList中继承过来的，
而在AbstractList中对此方法的说明是
此方法由此列表及其 subList 上的 clear 操作调用。重写此方法以利用内部列表实现可以极大地 改进此列表及其 subList 上 clear 操作的性能。
1 public void clear() {2 removeRange(0, size());3 }但是在ArrayList中的实现并没有像AbstractList中这样实现，反而是自己另外实现了，那这个方法是不是就没有用了呢？
并不是如此，ArrayList还在自己的内部添加了一个内部类SubList。
private class SubList extends AbstractList<E> implements RandomAccess
这个类只有在其外部ArrayList调用subList方法后才会生成一个特定的实例
1 public List<E> subList(int fromIndex, int toIndex) {2 subListRangeCheck(fromIndex, toIndex, size);3 return new SubList(this, 0, fromIndex, toIndex);4 }对应的构造方法
1 SubList(AbstractList<E> parent,2 int offset, int fromIndex, int toIndex) {3 this.parent = parent;4 this.parentOffset = fromIndex;5 this.offset = offset + fromIndex;6 this.size = toIndex - fromIndex;7 this.modCount = ArrayList.this.modCount;8 }而他的removeRange方法
1 protected void removeRange(int fromIndex, int toIndex) {2 checkForComodification();3 parent.removeRange(parentOffset + fromIndex,4 parentOffset + toIndex);5 this.modCount = parent.modCount;6 this.size -= toIndex - fromIndex;7 }现在一切揭晓了，修改ArrayList的removeRange方法同时也是在修改其内部类SubList的removeRange方法，
而内部类SubList并没有覆盖父类的clear方法，即和AbstractList的clear方法相同，也就和JDK的说明完全符合。
1 public void trimToSize() {2 modCount++;3 if (size < elementData.length) {4 elementData = http://www.mamicode.com/(size == 0)>这个方法用作将数组的容量变为数组的元素数量，可以使ArrayList所占内存空间达到最小。
具体实现是调用了Arrays.copy方法将数据复制到一个长度为size的数组中。
ArrayList的迭代器
介绍迭代器前首先要介绍一个从AbstractList中继承的实例域modCount，这个modCount在前面也经常出现。
JDK的解释是
已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小，或者打乱列表，从而使正在进行的迭代产生错误的结果。
这是一个并发操作的问题，例如我在遍历的时候删除一个元素，是否返回这个元素是未知的，即返回的结果可能出错也可能没错。
在之前的很多算法中我们也发现了这个modCount的出现，在后面的方法中，modCount经常会进行检测，发现错误会抛出ConcurrentModificationException。
但这个异常的抛出是尽力而为的，因为是并发操作，这个就被称为“快速失败”。
下面对出现modCount的代码就不再做解释了。
Iterator的声明
private class Itr implements Iterator<E>
继承自Iterator，不必多说。
Iterator的域
1 int cursor; // index of next element to return2 int lastRet = -1; // index of last element returned; -1 if no such3 int expectedModCount = modCount;
cursor表示光标，用来指示下一个元素的索引。
lastRet表示上一个返回元素的索引，初始为-1表示没有。
expectedModCount用作和modCount进行对比，初始和modCount相等。
Iterator的关键方法
1 public boolean hasNext() { 2 return cursor != size; 3 } 4 5 public E next() { 6 checkForComodification(); 7 int i = cursor; 8 if (i >= size) 9 throw new NoSuchElementException();10 Object[] elementData = http://www.mamicode.com/ArrayList.this.elementData;>hasNext直接范围其和size的比较值，若和size相等即表示到达最后，没有下一个元素。
next先判断是否有下个元素，如果没有就抛出NoSuchElementException，
用i保存cursor，增加cursor然后直接返回ArrayList.this.elementData[i]（当前对象的elementData），并将i的值赋给lastRet。
remove方法先判断是否有上个返回的元素，没有则抛出IllegalStateException，
调用当前对象的remove方法删除上个元素，并把光标前移，将lastRet设为-1。
1 public void forEachRemaining(Consumer<? super E> consumer) { 2 Objects.requireNonNull(consumer); 3 final int size = ArrayList.this.size; 4 int i = cursor; 5 if (i >= size) { 6 return; 7 } 8 final Object[] elementData = http://www.mamicode.com/ArrayList.this.elementData;>这是JAVA8添加了的一个缺省方法，只是遍历所有元素然后用consumer.accept接受该元素。
另外还有相应的listiteror的实现，也仅是增加了hasPrevious和previous以及set和add方法，
前两个和hasNext及next实现大同小异，后两种也仅是调用了ArrayList对应的方法，在此就不作赘述。
ArrayList源码分析