从源码上分析 ArrayList
前言
ArrayList 是 List 接口的一个实现类，那么 ArrayList 的底层是如何实现的呢？让我们来一探究竟。
源码分析
属性
先来看看 ArrayList 中比较重要的两个属性：
transient Object[] elementData;
private int size;elementData用来存储ArrayList中的元素，其实ArrayList的底层是用Object[]数组来实现的。size指的是的逻辑长度，就好像一个水杯，容量是 600 毫升，但杯中只有 200 毫升的水，ArrayList容器就是水杯， 这个size属性表示的就是水杯中水的容积。
构造方法
无参构造方法：
123 | public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;} |
|---|
很简单，就一行语句，elementData 在上面我们已经知道是什么了，那 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 又是什么呢？
1 | private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; |
|---|
原来只是一个空的 Object[]。
指定容量的构造方法：
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_ELEMENTDATA 来初始化。
用一个 Collection 对象进行构造的的构造方法：
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;
}
}首先将传入的参数转为对象数组赋值给 elementData ，如果传入的 Collection 参数的长度为 0，则就将空的常量数组对象 EMPTY_ELEMENTDATA 赋给了 elementData。
常用方法
add
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}调用了 ensureCapacityInternal 函数:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}这里判断 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 表示如果如果为没有初始化容量时，用默认容量 DEFAULT_CAPACITY 也就是 10，来开启空间，也就是上面我们说的水杯的容量。
接下来看 ensureExplicitCapacity 方法：
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;
// 对 ArrayList 容量进行 1.5 倍扩容。
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容后的容量还不够实际占用的容量，那么需要扩容到实际占用容量的大小。
// 如当前 newCapacity 为 10，扩容后为 15，
// 但现在实际的元素数量为 16 个，那么至少应该先装下这 16 个。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 防止阔中的过大，过大时，则使用 Integer.MAX_VALUE 代替。
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);
}其实这段代码也很简单，就是动态扩容 ArrayList 的大小，每次扩容都为当前容量的 1.5 倍，当然也进行了扩容过大或过小的限制。 其扩容原理就是创建一个容量为当前容量 1.5 倍的新数组，将旧数组的内容拷贝给新数组。
add(int index, E element)
public void add(int index, E element) {
// 判断要插入的位置不小于 0 且不大于当前最大位置
rangeCheckForAdd(index);
// 容量扩容检测，具体参见 add(E e) 方法
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}看过了 add(E e) 的源码，这里也就很好理解了，先进行插入位置有效性判断，然后判断容量是否需要扩容，然后先将插入位置开始的所有元素向后移动一位，最后将需要插入的元素插入指定位置。
get
public E get(int index) {
rangeCheck(index);
return elementData(index);
}ArrayList 的底层是用数组实现的，那么获取元素也就很方便了，判断获取位置合法后，直接用下标获取即可。
set
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}这个方法其实就是修改指定位置的元素，先拿到要覆盖的元素，然后将新元素赋值上去，最后返回覆盖的元素即可。
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;
}先进行有效性判断，然后从要删除的元素开始的所有元素都向前拷贝一位，并将最后一位设值为 null。
indexOf
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;
}如果要找的内容 null，则依次用 == 判断是否为要找的元素，如果不为 null，则用 equals 来依次判断。
总结
根据上方的源码分析，我们可以得出 ArrayList 的一些特性：
ArrayList底层数据结构是对象数组，如不指定长度，则初始容量为 10。- 底层的对象数组是在第一次添加元素的时候才进行初始化的。
- 每次扩容为原来容量的 1.5 倍，扩容原理是将原来的数据拷贝到新数组中。
所以我们在使用时要注意：
- 如知道大概要存多少个数据，最好指定初始化容量，这样可以提高程序性能。
ArrayList查找元素很快，但删除元素和添加元素的效率相对较差。