Java集合ArrayList实现原理

java.util.ArrayList是Java开发最常用的类之一，但是对具体的实现不太了解，通过源码来分析下ArrayList的具体实现。

初始化

ArrayList提供2个初始化方法不带参数的和带参数的ArrayList(int initialCapacity)，其中capacity 是ArrayList的默认大小。
源码如下：

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

   /**
     * 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) {
            //默认数组，空数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

下面我们先看一下ArrayList 的 add方法。
add方法有2个 分别是插入到末尾和插入到指定位置对应的方法是
1.add(E e)

2. add(int index, E element)
   首先我们先看一下插入到末尾的方法

    /**
     * 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) {
        //size是当前的list 容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

首先是调用ensureCapacityInternal()方法把arraylist做扩容处理。进入方法

/**
 * 确定list容量
 * minCapacity = size + 1
 */
private void ensureCapacityInternal(int minCapacity) {
        //计算得到新的容量
        int newCapacity = calculateCapacity(elementData, minCapacity);
        //确定新的容量
        ensureExplicitCapacity(newCapacity);
}
//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
         //如果list中没有数据，则获取list默认容量和计算容量(size+1)中较大的作为list新的容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
   //记录修改次数
   modCount++;
    // overflow-conscious code
    //如果计算出的新容量 大于原容量，则执行扩容操作
    if (minCapacity - elementData.length > 0)
             //扩容
            grow(minCapacity);
}

具体的操作逻辑可以看上面注释，已经标记的很明白了。
下面我们看一下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;
        //扩容之后的容量不超过最大容量(虚拟机限制)，超过之后会有OOM
        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);
    }

我们再看一下copyOf方法Arrays.copyOf(elementData, newCapacity),这个方法接收2个参数

 /**
     * Copies the specified array, truncating or padding with nulls (if necessary)
     * so the copy has the specified length.  For all indices that are
     * valid in both the original array and the copy, the two arrays will
     * contain identical values.  For any indices that are valid in the
     * copy but not the original, the copy will contain <tt>null</tt>.
     * Such indices will exist if and only if the specified length
     * is greater than that of the original array.
     * The resulting array is of exactly the same class as the original array.
     *
     * @param <T> the class of the objects in the array 
     * @param original the array to be copied 原始数组
     * @param newLength the length of the copy to be returned 扩容之后的容量
     * @return a copy of the original array, truncated or padded with nulls
     *     to obtain the specified length
     * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
     * @throws NullPointerException if <tt>original</tt> is null
     * @since 1.6
     */
    @SuppressWarnings("unchecked")
    public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }

举个栗子：

/**
     * 测试调用array list 的 add(index,element)方法
     */
    private static void testAddArrayCopy() {

        Object[] src = new Object[]{1,2,3,4};
        Object[] newSrc = Arrays.copyOf(src,5);
     
        for (Object i : newSrc) {
            System.out.print(i+ ",");
        }
    }

这个方法的运行结果：1,2,3,4,null,

回到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) {
        //size是当前的list 容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //执行到了这里，此时的elementData是已经扩容之后的数组了。
        //将要添加的元素放到数组的末尾
        elementData[size++] = e;
        return true;
    }

我们看到扩容完成之后

  elementData[size++] = e;

这行代码中 size 为数组扩容前的容量，size + 1就是把要添加的元素放到数组的最后一个。