JDK源码阅读笔记之ArrayList
前言：
ArrayList是我们经常使用的数据结构，对于ArrayList的get，add方法应该是使用最多的了。但是ArrayList的其他方法，以及内部的实现是怎样的呢？我们通过阅读ArrayList的源码了解下。
ArrayList基本介绍
- ArrayList是一种可变的数组的集合实现。允许填充所有元素，包括null值。并且实现了集合的所有操作。
- size，isEmpty，get，set，iterator，listIterator操作时间复杂度是O(1)常量时间
- add操作耗费是平摊常量时间（为何是平摊常量时间的解释请看这个讨论）
- 简单比较LinkedList和ArrayList：LinkedList在add操作上时间复杂度是O(1)，get操作时间复杂度是O(n)。ArrayList在add操作均摊时间复杂度是O(n)，get操作是O(1)级别。所以在需要大量随机访问的时候，用ArrayList比较合适。在添加删除操作比较多的情况使用LinkedList比较合适。
- 每个ArrayList对象都会有一个capacity属性(初始是10)。capacity属性是用来标示ArrayList能够存储的元素个数。capacity对我们来说是透明的，当容量不够的时候ArrayList会自动扩容。官方文档建议我们在大量添加元素的时候，可以事先调用ensureCapacity方法。这样可能会减少再分配所消耗的时间。（一般在初始化ArrayList的时候，我会初始化大致存储的元素个数。）
- ArrayList不是线程安全的，所以不要在多线程环境下进行读写操作。
- 如果在多线程环境下并发操作ArrayList，并且至少有一个线程改变了list的结构（改变结构指的是任何添加，删除元素或者改变了list内部array的大小的操作），那么就必须要在外部加锁。如果不加锁，我们还可以使用Collections.synchronizedList方法来包装list List list = Collections.synchronizedList(new ArrayList(...));
- iterators方法会返回class的iterator。如果在当前iterator创建后，调用非iterator方法改变了list的结构。那么iterator会抛出ConcurrentModificationException异常。
ArrayList的父类和接口：
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
...
}
- ArrayList继承了AbstractList。ArrayList重写了父类的大部分方法，更加适应自己的操作。以下方法继承自父类：
- ArrayList实现了RandomAccess，Cloneable，Serializable。这些接口的作用是用来表示ArrayList的随机访问，克隆和序列化功能。List接口的话是一定要实现的了。
ArrayList的属性
ArrayList的所有属性如下图所示：
- DEFAULT_CAPACITY是ArrayList默认的初始化容量。
- EMPTY_ELEMENTDATA是ArrayList数据是一个empty的数组，表示ArrayList的数据为empty。
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA是ArrayList数据初始化时为empty的时候的默认数组。
- elementData是用来真正存储元素的数组。
- size表示当前ArrayList中的元素个数。
- MAX_ARRAY_SIZE是对ArrayList能添加的元素数量进行限制
- modCount是一个标识变量，支持iterator的fail-fast特性。当iterator的方法执行时会对这个变量进行检查，得到ArrayList的结构是否发生改变。
ArrayList的构造方法
ArrayList有三个构造方法
1 默认的构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
不是说默认的初始化大小是10吗？怎么是一个null的数组。一开始我也不明白，等到后面看到add方法的代码就明白了。
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);
}
}
通过参数初始化ArrayList大小的构造方法。大于0初始化对应大小的数组。等于0用使用默认的empty数组。小于0处于非法状态。
3 复制功能的构造函数:
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//这段代码是因为不同的集合对toArray实现的方式不一样，所以导致返回的类型不一样
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
将传入的集合拷贝到内部的elementData中。拷贝的集合如果是emtpy集合使用EMPTY_ELEMENTDATA代替。
ArrayList的部分方法解读：
- trimToSize: 将ArrayList的容量减少到当前的size大小
public void trimToSize() {
modCount++; //说明这个操作改变了ArrayList的结构
if (size < elementData.length) { // size小于当前的容量时执行
elementData = (size == 0) //size等于0 elementData等于null数组。不等0初始化size大小的数组，
? EMPTY_ELEMENTDATA //并拷贝elementData的元素，并重新赋给elementData
: Arrays.copyOf(elementData, size);
}
}
2.ensureCapacity：对ArrayList进行扩容，参数是期望的最小容量。从代码可得，要满足期望最小容量大于内部元素数量（minCapacity > elementData.length），同时内部元素不处于默认的元素状态（elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA）并且期望最小容量要大于默认容量（10）（minCapacity <= DEFAULT_CAPACITY） 。如果比默认容量小当然就不需要扩容了。这个操作也会改变ArrayList的结构，所以modCound++。满足以上条件就会进行扩容操作了。
public void ensureCapacity(int minCapacity) {
if (minCapacity > elementData.length
&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
&& minCapacity <= DEFAULT_CAPACITY)) {
modCount++;
grow(minCapacity);
}
}
3.indexOf：判断元素在ArrayList内的索引位置。如果不在就返回-1。首先判断是否为null，如果为null对内部元素是否为null进行遍历。否则使用equals方法进行遍历返回元素所在位置。没有返回-1。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
4.clone：ArrayList对clone方法进行了重写。支持对ArrayList本身进行clone，但是对elementData进行的是浅拷贝，所以在调用ArrayList的clone方法时，如果是基本类型可以直接使用，但是对引用类型要注意。
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
5.toArray：将ArrayList转化成对应类型的Array。转换的时候如果a的容量小于List的数量，那么直接进行拷贝。但是如果大于会将size位置的索引设置为null，然后返回a。
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
6.get：获取指定索引处的元素。首先对想要获取的索引进行检查是否越界。然后对返回内部存储的数据里面对应的元素。
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
7.set：设置目标索引位置的元素。设置的索引位置不能超过当前size。符合条件会修改对应位置的元素。
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
8.add：在ArrayList内添加新元素。如果新添加的元素超过了当前的容量那么会扩容至当前容量的1.5倍。(int newCapacity = oldCapacity + (oldCapacity >> 1);)
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
9.remove：移除对应索引处的元素。主要逻辑在fastRemove方法。首先检查移除索引是否越界。如果移除元素不是末尾元素，那么就要将索引后面的元素向前拷贝。然后将原size处的元素置为null。以后对数组进行删除操作可以参考这里的代码。很高效～
public E remove(int index) {
Objects.checkIndex(index, size);
final Object[] es = elementData;
@SuppressWarnings("unchecked") E oldValue = (E) es[index];
fastRemove(es, index);
return oldValue;
}
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
总结：
从这里开始研究JDK源码的第一步了～JDK的代码是很多大师来操刀实现的，没事多看看，一方面对这些工具可以更加熟悉，另一方面可以学习当中的思想。对ArrayList的分析就到这里了，还有很多函数式的接口，在以后函数式系列文章一起写吧。