ArrayList源码分析

首先还是先来看下ArrayList的UML关系图

image.png

图中可以看出ArrayList继承AbstractList抽象类以及四个接口List、Cloneable、Serializable、RandomAccess，其中AbstractList又是继承了List接口，实际上ArrayList就是继承了List接口的增删改查遍历相关的接口；而继承的RandomAccess接口又是一个空接口，搜索代码发现其主要作用其实可以理解为是作为一个标识，判断list是否具有随机访问的功能，有的话优先使用for循环get(index)的方式遍历集合，不是的话则选择Iterator.next遍历循环集合（搜索代码可搜到 list instanceof RandomAccess）。

下面我们接着来看arraylist的对象创建以及增加数据的逻辑；当我们创建一个新的ArrayList对象时，经常使用以下代码

//不指定数组大小
List<String> arr1 = new ArrayList<>();
//指定数组大小
List<String> arr2 = new ArrayList<>(2);

当我们创建一个不指定数组大小的ArrayList对象时，会调用ArrayList的无参构造方法，并初始化elementData数值

transient Object[] elementData;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

从上面代码我们也可以知道，实际上new一个ArrayList对象的时候，是实例化了一个空的Object数值，ArrayList底层存放数据的时候实际上用的是数组来实现的。当初始化一个指定大小的ArrayList对象时，则初始化的逻辑也不同

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);
    }
}

当指定了数组大小时，实际上只是初始化时，指定了Object数组的大小；除了这两个构造方法外还有一个传入集合对象的构造方法，初始化的时候是调用集合的toArray赋值给elementData，并且设置size值

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;
    }

以上我们已经讲完了创建ArrayList对象的部分，接下来讲下ArrayList的add方法，下面是源码部分

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

调用add方法时，会先调用ensureCapacityInternal方法判断是否需要扩容，然后再将传入的e对象设置到数组的最后一个位置，size+1；接下来我们来继续看下扩容的这个方法的源码实现，当ArrayList对象add第一个数值进来前，size默认值为0，此时调用ensureCapacityInternal方法传入的minCapacity=1；

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

进入ensureCapacityInternal方法先调用了calculateCapacity方法

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
    }

因为此时elementData还为空数组，minCapacity=1，所以返回默认数值10，再进入ensureExplicitCapacity方法，传入参数minCapacity=10

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这个时候elementData还是一个空的Object数组，所以length=0，minCapacity - elementData.length=10 大于0，进入grow方法进行扩容，minCapacity=10

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方法进入到底层的grow方法时，oldCapacity = 0，newCapacity = 0，所以新扩容的newCapacity 最终会被赋值为默认的10，然后调用Arrays.copyOf返回一个新的Object数组，长度为10，即ArrayList第一次扩容的长度默认即为10；当增加第11个元素进入到ArrayList时，进入ensureExplicitCapacity方法的参数minCapacity=11，此时minCapacity - elementData.length > 0，会再次进行扩容，扩容计算方式按照：旧数组长度10+旧数组长度右移1位（即除以2），所以最终扩容是在原来的容量值基础上*1.5进行扩容，即第二次扩容后数组长度为10+10/2=15，后面扩容方式都是以此类推。

至此介绍完ArrayList的主要部分，如果有哪里说错麻烦指正，谢谢！

ArrayList源码分析

推荐阅读更多精彩内容