ArrayList源码浅析

ArrayList的可以看做是一个动态的数组，更复杂的数组，其实ArrayList的底层也是用数组来实现的，下面我们来看一下ArrayList常用方法的实现，以及自定义一个自己的ArrayList。源码参考版本1.6.

ArrayList初始化：

List list = new ArrayList();

源码为：

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

我们可以看出在初始化的时候，在内部创建了一个空的数组。注意：在JDK1.5之前，源码是这样的：

    public ArrayList(){
        this(10);
    }
    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);
        }
    }

在初始化的时候创建一个十个元素的数组，而在JDK1.6之后，这个动作放在了第一次add的时候。

add()方法

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

整个add的操作是通过上面四个方法来实现的，重点是第三个和第四个方法。下面我们来逐一分析一下：
ensureCapacityInternal 方法：

这个方法主要的工作是第一次add的时候，为内部数组进行初始容量赋值。为什么把初始容量的赋值放到这个地方呢？我觉得是这样的，如果在new 的时候就先指定一个数组大小的话，你有可能不对它进行其他的操作，而导致内存空间的浪费。

ensureExplicitCapacity 方法

这个方法需要特别注意的是 modCount++这个操作，这句话的作用是用来记录对ArrayList的每一次操作，也就是说你对ArrayList的每一次操作它都会进行++，不管是add、remove等等。我们知道在对集合进行迭代的时候，不能对集合进行remove的操作，它就是通过对比这个值来判断的。 接下来的这个if也很关键，当你add的时候，如果ArrayList的 size+1 > 数组的长度的时候，它就会对ArrayList内部的数组进行扩容了。

grow 方法

grow这个方法是非常关键的方法，在这个方法里实现了对ArrayList内部数组的扩容。扩容原则是：先扩为原来的1.5倍，如果是大容量，则取大容量的值，再利用Arrays.copy()方法，进行扩容。接下来是最为关键的一步：elementData[size++] = e;为数组中的元素赋值，赋值完成之后就完事了吗？当然没有，要size+1，为什么要size+1呢？因为size方法，返回的就是这个size的值！

size 方法

这个方法的实现也是很简单的，就一句话：

    public int size() {
        return size;
    }

isEmpty 方法

这个方法的实现也很简单，也是一句话：

    public boolean isEmpty() {
        return size == 0;
    }

get 方法

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

这个方法有两步，第一步先校验传进来的索引是否大于等于size或者索引小于0，如果是，则抛出异常，如果否，则返回数组中响应下标的元素。

remove方法

    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    private void fastRemove(int index) {
        modCount++;
        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
    }

循环匹配，匹配到了之后，则从下个位置的元素copy的原来数组的位置上，并把最后一个元素让垃圾回收器回收掉。

addAll方法

    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

和add的实现异曲同工，几乎没有什么差别的地方。

其他的有兴趣的可以自己翻看一下，我觉得知道它的底层是数组之后，再看源码实现就会非常简单了。我觉得ArrayList的源码实现是集合类中最简单的了。有时间我会把LinkedList的源码实现大致的说一下。附上一段自己写的小代码：

package com.zkn.newlearn.collection;

import java.util.Arrays;

/**
 * 这个类用来模仿实现ArrayList的功能
 * @author zkn 2016-06-20
 *
 */

public class ImitateArrayListTest01 {
    /**
     * 一个初始化的数组数据
     */
    private Object[] elementData;
    /**
     * 一个空的数组对象
     */
    private static final Object[] EMPTY_ARRAY = {};
    /**
     * 默认初始为空
     */
    private static final Object[] DEFAULT_EMPTY_ARRAY = {}; 
    /**
     * 用来记录元素的个数
     */
    private int size;
    private static final int DEFAULT_INIT = 10;
    /**
     * 构造函数
     */
    public ImitateArrayListTest01(){
        //默认初始化10参数
        //1.6之后 设置初始因子 放到了第一次add的时候
        this(DEFAULT_INIT);
    }
    
    public ImitateArrayListTest01(int initialCapacity){
        if(initialCapacity < 0)
            throw new IllegalArgumentException("请传入大于0的值");
        if(initialCapacity == 0)
            this.elementData = EMPTY_ARRAY;
        this.elementData = new Object[initialCapacity];
    }
    /**
     * 元素的个数
     */
    public int size(){
        
        return this.size;
    }
    /**
     * 添加元素
     */
    public void add(Object obj){
        if(elementData == DEFAULT_EMPTY_ARRAY)
            elementData = new Object[DEFAULT_INIT];
        if((this.size+1) > elementData.length){
            int oldLength = elementData.length+1;
            //增加一倍
            int newLength = oldLength + (oldLength >> 1);
            if(newLength - DEFAULT_INIT < 0)
                //如果新长度小于默认值，则扩长为默认值的长度
                newLength = DEFAULT_INIT;
            //去掉大容量的逻辑
            //扩展数组
            elementData = Arrays.copyOf(elementData, newLength);
        }
        elementData[size++] = obj;
    }
    /**
     * 获取数组中的值
     * @return
     */
    public Object get(int index) {
        checkIndex(index);
        return elementData[index];
    }
    private void checkIndex(int index) {
        if(index >= size)
            throw new IndexOutOfBoundsException("取值范围过大");
    }

    /**
     * 是否为空
     * @return
     */
    public boolean isEmpty(){
        
        return size == 0;
    }
    
}