透过源码分析ArrayList运作原理
List接口的主要实现类ArrayList，是线程不安全的，执行效率高；底层基于Object[] elementData 实现，是一个动态数组，它的容量能动态增加和减少。可以通过元素下标访问对象，使用于快速检索场景时使用。
基于JDK1.8，通过ArrayList几个常用的方法，分析ArrayList原理。
属性及继承关系
- public class ArrayList<E> extends AbstractList<E>
- implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
- private static final long serialVersionUID = 8683452581122892189L;
- private static final int DEFAULT_CAPACITY = 10;
- private static final Object[] EMPTY_ELEMENTDATA = {};
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
- transient Object[] elementData;
- private int size;
- }
ArrayList继承AbstractList类，并实现List接口；
RandomAccess：是一个标记接口，继承了RandomAccess接口的集合支持随机快速访问
Cloneable：继承Cloneable接口，重写clone()方法，能实现拷贝功能
Serializable：支持序列化，可存储和传输
空构造函数及带参构造函数
ArrayList()
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
当我们new ArrayList()时会初始化elementData属性为空数组{}，此时底层的数组并没有被实例化，所以操作ArrayList其实就是围绕elementData这个数组而进行。
ArrayList(int initialCapacity)
- 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);
- }
- }
当使用带参构造函数 initialCapacity ；可以从源码看出如果 initialCapacity 大于 0 ，会实例化一个指定长度的Object数组赋值给elementData ；如果 initialCapacity 等于 0 则依然赋值为空；否则抛出异常信息。
通过以上两个构造函数，可以很明确ArrayList底层其实是一个Object[] 数组，而调用ArrayList提供的方法，其实就是操作数组。
add(E e)
- public boolean add(E e) {
- ensureCapacityInternal(size + 1);
- elementData[size++] = e;
- return true;
- }
add(E e) 方法的作用是添加一个元素到列表末尾，方法第一行调用ensureCapacityInternal(size + 1); 代码如下：
- private void ensureCapacityInternal(int minCapacity) {
- if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
- minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
- }
- ensureExplicitCapacity(minCapacity);
- }
判断elementData为空数组时则返回DEFAULT_CAPACITY, minCapacity这两个中的最大值，接着调用ensureExplicitCapacity(minCapacity)；代码如下：
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- if (minCapacity - elementData.length > 0)
- grow(minCapacity);
- }
可以看出这里其实就是判断是否需要进行扩容，条件是当我们所需要的数组长度减去数组的长度大于0时，会调用grow(minCapacity)进行扩容；代码如下：
- private void grow(int minCapacity) {
- int oldCapacity = elementData.length;
- int newCapacity = oldCapacity + (oldCapacity >> 1);
- if (newCapacity - minCapacity < 0)
- newCapacity = minCapacity;
- if (newCapacity - MAX_ARRAY_SIZE > 0)
- newCapacity = hugeCapacity(minCapacity);
- elementData = Arrays.copyOf(elementData, newCapacity);
- }
声明一个newCapacity属性，值为原数组长度的1.5倍且进行判断，如果扩容后的长度减去我们需要的数组长度小于0则使用扩容后的长度，如果扩容后的长度减去MAX_ARRAY_SIZE大于0则使用Integer的最大值（Integer.MAX_VALUE） ，这里的MAX_ARRAY_SIZE 实则是Integer.MAX_VALUE – 8，接下来就是拷贝一个新的数组
通过add(E e)方法的源代码，又可以很明确知道当我们在对ArrayList集合添加元素的时候，其实会对底层elementData数组的长度进行判断并动态调整且产生一个新的数组回来
remove(int index)
- 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;
- return oldValue;
- }
remove(int index)方法的作用是按照索引位置删除并返回元素；第一行代码rangeCheck(index);检查索引是否越界，代码如下：
- private void rangeCheck(int index) {
- if (index >= size)
- throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
- }
E oldValue = elementData(index);获取指定下标的数据，计算出需要移动的位置，调用native方法进行数组移动，改变size长度，且将–size位置置空等待GC回收，最终返回之前的值
get(int index)
- public E get(int index) {
- rangeCheck(index);
- return elementData(index);
- }
get(int index)方法的作用是获取指定下标的元素；第一步检查索引是否合法，根据下标获取elementData数组中的数据并返回
set(int index, E element)
- public E set(int index, E element) {
- rangeCheck(index);
- E oldValue = elementData(index);
- elementData[index] = element;
- return oldValue;
- }
set(int index, E element)方法的作用是设置指定下标的元素值；第一步检查索引是否合法，然后获取之前的值，并将之前下标的值更改为当前数据，返回老数据