文章目录

ArrayList简介ArrayList源码整体结构标记接口RandomAccessCloneableSerializable AbstractList Body分析Add扩容机制 RemoveFail-Fast机制可分割迭代器

ArrayList简介

The ArrayList class extends AbstractList and implements the List interface. ArrayList supports dynamic arrays that can grow as needed. Standard Java arrays are of a fixed length. After arrays are created, they cannot grow or shrink, which means that you must know in advance how many elements an array will hold. Array lists are created with an initial size. When this size is exceeded, the collection is automatically enlarged. When objects are removed, the array may be shrunk. – WIIKIBOOKS

也就是说ArrayList继承了AbstractList，具有List的特点。同时底层又是通过数组实现，其最大的特点就是上面所说的自动扩容。

ArrayList源码

整体结构

打开源代码（这里用到的是jdk1.8，虽然都已经13了，捂脸），首先映入眼帘的就是

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

这个可是好东西，只要有了它。我们大概就能知道它会有哪些功能。下面是个简单的类图

标记接口

先从右边三个看起，这三个都有一个特点，就是它们都是空接口。没错，就是里面什么都没有，因此也被称为标记接口。它又是怎么实现的呢，简单看下例子

RandomAccess

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }

很明显，是否实现了该接口，最后它们的检索方式是不一样的。

Cloneable

public Object clone() throws CloneNotSupportedException { if (this instanceof Cloneable) { return super.clone(); } else { throw new CloneNotSupportedException(); } }

如果实现了该接口，可以是实现clone；否则抛出CloneNotSupportedException异常。

Serializable

if (obj instanceof String) { writeString((String) obj, unshared); } else if (cl.isArray()) { writeArray(obj, desc, unshared); } else if (obj instanceof Enum) { writeEnum((Enum<?>) obj, desc, unshared); } else if (obj instanceof Serializable) { writeOrdinaryObject(obj, desc, unshared); } else { if (extendedDebugInfo) { throw new NotSerializableException( cl.getName() + "\n" + debugInfoStack.toString()); } else { throw new NotSerializableException(cl.getName()); } }

如果以上都不是，直接抛出NotSerializableException。但注意到其中的当家数组elementData竟然是transient，原来里面已经做了定制，避免不必要传输，只传输真实的数据

// Write out all elements in the proper order. for (int i=0; i<size; i++) { s.writeObject(elementData[i]); }

此处用的是size，而不是elementData.length。

AbstractList

它继承自AbstractCollection，同时实现了List接口。由于也实现了Iterable，所以自然可以通过迭代器进行访问。下面直接通过ArrayList分析

Body分析

Add

Add大致四种。有直接追加在list的末尾的，比如下面这个

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

当然谈到add，我们就不得不谈到ArrayList的扩容机制。

扩容机制

我们按捺住狂热且激动的心情，伸出颤抖着小手果断点开那段充满忧郁的蓝色代码，那应该就是扩容的入口

private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }

minCapacity是希望的最小容量，当采用无参构造函数时，默认容量就是DEFAULT_CAPACITY（10），数组就是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，这里只是对minCapacity根据情况重新赋值。于是继续往下看

private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

这里只要希望的容量已经大于目前的长度，那么就进行扩容。这整个构成了扩容机制，其中grow函数对如何扩容做了深刻而又全面的阐述

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); }

一般情况下新的容量将会是之前容量的1.5倍。若1.5倍的容量还是小于希望的容量，那新的容量就是minCapacity；还有中情况1.5倍的容量大于最大数组长度，要么发生OutOfMemoryError，要么就设置成最大值。最后通过Arrays.copyOf拷贝原数组elementData中的元素，并返回一个长度为newCapacity的新数组。 也有指定插入的，比如

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++; }

这里需要说明的是add操作都会有扩容机制，如果带有索引，会有范围检查。通过System.arraycopy轻松实现了数组的后移，然后再相应的位置插入元素。 对集合的操作

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; }

既然底层是数组，那自然将其转化为数组进行操作。通过arraycopy完成数据复制，最后用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; }

Remove

说完了Add，接着在看下Remove。总的来说，也就两种，单个移除和批量移除。首先来看下移除具体位置上的数据。思路很简单，把索引后的数据依次前移，最后一位置null，便于GC

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; }

另一种定点移除，就是直接移除遇到的第一个元素。但移除的时候仍然需要借助了索引，首先找到该元素的索引，接着在利用之前的移除方法。 移除集合，要求集合不能为空，否则将会抛出NullPointerException

public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); }

这里的batchRemove通过是否包含集合中的元素（也就是通过后面的false变量控制，默认移除没在Collection中的元素），接着移除方式也是和上面的类似。

Fail-Fast机制

这里还需要说明的是ArrayList是线程不安全的，并且支持Fail-Fast快速失败机制。之前有个变量一直出现，但却没有提及，就是modCount。它在这里起到了至关重要的作用。在每一次增加或者移除都会加1，没错，它就是记录的是修改的次数。

if (modCount != expectedModCount) { throw new ConcurrentModificationException(); }

其中expectedModCount是final型。而一旦modCount和期望的修改值不一致，就会抛出ConcurrentModificationException。

可分割迭代器

在1.8的版本中首次增加了可分割迭代器，是为并行遍历元素而这设计的，相对于顺序遍历。具有late-binding和fail-fast的特点，每次可将之前的Spliterator平分成两份，从而可实现并行遍历

public ArrayListSpliterator<E> trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : // divide range in half unless too small new ArrayListSpliterator<E>(list, lo, index = mid, expectedModCount); }