本次笔记研究ArrayList源码。ArrayList的使用就不讲了，太简单了；ArrayList的本质是对数组的简单包装，直接撸源码，先来看下类信息:
//ArrayList继承自AbstractList，AbstractList的父类
//实现了Collection接口，ArrayList同时实现了List接口
//注意，ArrayList实现了RandomAccess接口，现该接口的
//List支持快速随机访问，主要目的是使算法能够在随机和顺
//序访问的list中表现的更加高效；可以通过简单的for循环
//来访问数据比使用iterator访问来的高效快速。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
* 初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*
* 空数组；创建ArrayList的时候可以指定他的初始容量是0
* 这种场景下，ArrayList的数组就指向下面这个空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*
* 空数组，当我们调用new ArrayList()创建ArrayList
* 的时候，ArrayList里面的数组就指向下面这个空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*
* 元素数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* ArayyList里面的元素个数
* @serial
*/
private int size;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*
* 带有容量的构造函数
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//直接创建一个指定长度的空数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果指定初始容量是0，那么将ArrayList的数组指向EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
//如果传过来一个负数，那就死给你看
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*
* 最常用的构造函数，默认素数组是空数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*
* 基于一个Collection对象构造一个ArrayList
*/
public ArrayList(Collection<? extends E> c) {
//把Collection对象转化成数组，赋值给elementData
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;
}
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*
* ArrayList的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
ArrayList的信息还是蛮好理解的；国际惯例，先看添加元素的方法add:
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//首先确定ArrayList的容量是否足够，不够就扩容，注意，这里
//虽然还没有真的把元素添加进去，但是他把元素个数 + 1传进去
//然后用这个相加后的长度去判断是不是需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//将元素存入到数组的末尾
elementData[size++] = e;
return true;
}
往ArrayList添加元素，其实就是往数组添加元素，非常简单，但是还有个容量判断的步骤，非常重要，分析下：
private void ensureCapacityInternal(int minCapacity) {
//参数minCapacity是添加元素后总的元素个数
//如果数组是空数组，也就是第一次往ArrayList添加元素
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//确定最小的容量，在传进来的长度和默认容量之间取最大值
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
ensureCapacityInternal方法没什么好说的， 就是确定一个容量而已，继续看ensureExplicitCapacity：
private void ensureExplicitCapacity(int minCapacity) {
//modCount自增，跟HashMap是一个道理
modCount++;
// overflow-conscious code
//只有新增元素后的长度大于当前数组长度的情况下才会扩容
if (minCapacity - elementData.length > 0)
//真正扩容的地方
grow(minCapacity);
}
ensureExplicitCapacity也很简单，直接看真正的扩容方法grow:
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
//老的容量
int oldCapacity = elementData.length;
//新的容量，他是老容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果上面计算的容量还不够元素个数，那么元素个数将作为新的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量比最大值还大，那么新的容量将取值Integer的最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//复制数组，完成扩容。copyOf最后会调到Native层，分析不了
elementData = Arrays.copyOf(elementData, newCapacity);
}
总的来说，add方法还是很简单的；add的时候将元素个数 + 1，然后去判断要不要扩容；如果扩容的话，要么扩容到元素个数 + 1那么大，要么就是原来的1.5倍(一般是1.5倍)；扩容动作是在System类的arraycopy方法实现的，没代码，分析不了。
添加元素的方法分析完了，继续分析获取的方法，其实就是去数组获取一个元素，想想都不会太难：
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
//首先检查传进来的索引是不是越界了，一旦越界就抛出威
//震江湖的IndexOutOfBoundsException异常，怕了没？
rangeCheck(index);
//返回指定索引的数组元素
return elementData(index);
}
get方法太简单了，下面看下remove方法：
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查传进来的索引是否越界
rangeCheck(index);
//modCount自增
modCount++;
//拿到数组元素
E oldValue = elementData(index);
//数组的删除回导致后面的元素的内存移
//动，numMoved就是计算移动的元素个数
int numMoved = size - index - 1;
//如果真的需要移动，那么调用System的arraycopy
//方法去实现移动，扩容操作最后也是调到这个方法
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将数组的最后一个位置的元素置空，以便垃圾回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
remove方法是非常简单的；还有一个重载的remove方法，传入的是Object对象，过程也很简单，不单独分析了。
总的来说，ArrayList是非常简单的，他本身没什么好讲的，毕竟是操作数组，没有其他复杂的数据结构，这一点大家应该都是轻车熟路了；但是他的排序方法sort有点复杂，暂时没有时间研究；下面看下之前没有研究过的知识点，迭代器。ArrayList的迭代器使用如下：
Iterator<String> it = set.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
当然了，<String>根据实际情况自己选择类型，这里仅仅是举个列子，废话不多说，直接撸源码:
/**
* An optimized version of AbstractList.Itr
*/
private class Itr implements Iterator<E> {
//游标，也就是下个元素的索引
int cursor; // index of next element to return
//最近返回的元素的索引，如果没有返回，那么值是-1
int lastRet = -1; // index of last element returned; -1 if no such
//modCount，迭代之前会把modCount保存到迭代器
int expectedModCount = modCount;
//hasNext()的实现非常简单，就是看下个元素的所以
//是不是等于size，如果相等，说明元素迭代完了，退出
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//检查modCount，一些操作，比如add，remove的时候，都会修改modCount
//如果在修改的过程中去迭代ArrayList，那么迭代的结果肯定是错误的，所以
//每次迭代之前都要检查modCount；如果ArrayList的modCount和迭代器的
//modCount不一样，说明有别的线程正在修改ArrayList；此时就要抛出异常
checkForComodification();
//把游标赋值给i
int i = cursor;
//游标肯定不能比数组个数大
if (i >= size)
throw new NoSuchElementException();
//拿到元素数组
Object[] elementData = ArrayList.this.elementData;
//游标肯定不能比数组长度还长
if (i >= elementData.length)
throw new ConcurrentModificationException();
//先把游标+1，让他指向下个元素，下次迭代的时候就能拿到下个元素
cursor = i + 1;
//返回刚刚迭代到的元素
return (E) elementData[lastRet = i];
}
......
}
