透过源码分析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)方法的作用是设置指定下标的元素值；第一步检查索引是否合法，然后获取之前的值，并将之前下标的值更改为当前数据，返回老数据

巴特西