Java集合基于JDK1.8的ArrayList源码分析

2020-02-02 16:02:58来源：博客园阅读 ()

Java集合基于JDK1.8的ArrayList源码分析

本篇分析ArrayList的源码，在分析之前先跟大家谈一谈数组。数组可能是我们最早接触到的数据结构之一，它是在内存中划分出一块连续的地址空间用来进行元素的存储，由于它直接操作内存，所以数组的性能要比集合类更好一些，这是使用数组的一大优势。但是我们知道数组存在致命的缺陷，就是在初始化时必须指定数组大小，并且在后续操作中不能再更改数组的大小。在实际情况中我们遇到更多的是一开始并不知道要存放多少元素，而是希望容器能够自动的扩展它自身的容量以便能够存放更多的元素。ArrayList就能够很好的满足这样的需求，它能够自动扩展大小以适应存储元素的不断增加。它的底层是基于数组实现的，因此它具有数组的一些特点，例如查找修改快而插入删除慢。本篇我们将深入源码看看它是怎样对数组进行封装的。首先看看它的成员变量和三个主要的构造器。

//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
 
//空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
 
/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
//对象数组
private transient Object[] elementData;
 
//集合元素个数
private int size;
 
//传入初始容量的构造方法
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);
    }
}
 
//不带参数的构造方法
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
 
//传入外部集合的构造方法
public ArrayList(Collection<? extends E> c) {
    //将外部集合庄户安慰数组
    elementData = c.toArray();
    //如果传入的集合长度不为0
    if ((size = elementData.length) != 0) {
        //判断引用的数组类型, 并将引用转换成Object数组引用
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

可以看到ArrayList的内部存储结构就是一个Object类型的数组，因此它可以存放任意类型的元素。在构造ArrayList的时候，如果传入初始大小那么它将新建一个指定容量的Object数组，如果不设置初始大小那么它将不会分配内存空间而是使用空的对象数组，在实际要放入元素时再进行内存分配,被扩展成大小为DEFAULT_CAPACITY长度的数组,DEFAULT_CAPACITY值为10。下面再看看它的增删改查方法。

//增(添加)
public boolean add(E e) {
    //添加前先检查是否需要拓展数组, 此时数组长度最小为size+1
    ensureCapacityInternal(size + 1);
    //将元素添加到数组末尾
    elementData[size++] = e;
    return true;
}
 
 
//增(插入)
public void add(int index, E element) {
    //插入位置范围检查
    rangeCheckForAdd(index);
    //检查是否需要扩容
    ensureCapacityInternal(size + 1);
    //挪动插入位置后面的元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    //在要插入的位置赋上新值
    elementData[index] = element;
    size++;
}
 
//删
public E remove(int index) {
    //index不能大于size
    rangeCheck(index);
    modCount++;
    E oldValue = elementData(index);
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        //将index后面的元素向前挪动一位
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    //置空引用
    // clear to let GC do its work
    elementData[--size] = null;
    return oldValue;
}
 
//改
public E set(int index, E element) {
    //index不能大于size
    rangeCheck(index);
    E oldValue = elementData(index);
    //替换成新元素
    elementData[index] = element;
    return oldValue;
}
 
//查
public E get(int index) {
    //index不能大于size
    rangeCheck(index);
    //返回指定位置元素
    return elementData(index);
}

每次添加一个元素到集合中都会先检查容量是否足够，否则就进行扩容，扩容的细节下面会讲到。我们先看具体增删改查要注意的地方。

增(添加)：仅是将这个元素添加到末尾。操作快速。
增(插入)：由于需要移动插入位置后面的元素，并且涉及数组的复制，所以操作较慢。
删：由于需要将删除位置后面的元素向前挪动，也会设计数组复制，所以操作较慢。
改：直接对指定位置元素进行修改，不涉及元素挪动和数组复制，操作快速。
查：直接返回指定下标的数组元素，操作快速。

通过源码看到，由于查找和修改直接定位到数组下标，不涉及元素挪动和数组复制所以较快，而插入删除由于要挪动元素，涉及到数组复制，操作较慢。并且每次添加操作还可能进行数组扩容，也会影响到性能。下面我们看看ArrayList是怎样动态扩容的。


private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果此时还是空数组
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //和默认容量比较, 取较大值
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    //对数组进行检查操作
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //如果最小容量大于数组长度就扩增数组
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/**
 * The maximum size of array to allocate.
 * Some VMs reserve some header words in an array.
 * Attempts to allocate larger arrays may result in
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
//集合最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
//增加数组长度
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);
}

private static int hugeCapacity(int minCapacity) {
    //如果最小容量已经超过int的最大值,变为负数,则抛出异常
    //要求的数组长度已经超过jvm的长度限制
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //此时以最小容量进行判断
    //如果最小容量还是正数,并且大于数组最大容量,则返回int最大值,否则返回数组最大容量
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

每次添加元素前会调用ensureCapacityInternal这个方法进行集合容量检查。

先计算出本次操作需要的最小容量.如果当前集合内部数组还是个空数组,则最小容量则是DEFAULT_CAPACITY为10.如果不是空数组则最小容量就是传递过来的最小容量minCapacity

接着调用ensureExplicitCapacity方法检查当前数组的容量是否满足这个最小所需容量，如果要求的最小容量小于等于elementData数组的长度,则不进行扩容,否则的话就调用grow方法进行扩容。

在grow方法内部可以看到，每次扩容都是增加原来数组长度的一半oldCapacity >> 1，扩容实际上是新建一个容量更大的数组，将原先数组的元素全部复制到新的数组上，然后再抛弃原先的数组转而使用新的数组。

grow方法的逻辑.如果newCapacity大于等于minCapacity,则newCapacity为newCapacity,否则newCapacity为minCapacity,所以计算后的newCapacity总是大于等于minCapacity.将计算后的newCapacity与MAX_ARRAY_SIZE进行比较,如果newCapacity小于等于数组的最大值MAX_ARRAY_SIZE,则按照newCapacity扩容,否则执行hugeCapacity方法.

hugeCapacity方法则以允许的最小容量进行比较.首先对最小容量进行判断,如果最小容量超出int的最大值变为负数,则抛出异常OutOfMemoryError,显示要求的数组长度已经超过jvm的长度限制.如果最小容量为正数,且大于MAX_ARRAY_SIZE,则返回int的最大值为新的容量,否则返回MAX_ARRAY_SIZE为新的容量

至此，我们对ArrayList中比较常用的方法做了分析，其中有些值得注意的要点：

1. ArrayList底层实现是基于数组的，因此对指定下标的查找和修改比较快，但是删除和插入操作比较慢。
2. 构造ArrayList时尽量指定容量，减少扩容时带来的数组复制操作，如果不知道大小可以赋值为默认容量10。
3. 每次添加元素之前会检查是否需要扩容，每次扩容都是增加原有容量的一半。
4. 每次对下标的操作都会进行安全性检查，如果出现数组越界就立即抛出异常。
5. ArrayList的所有方法都没有进行同步，因此它不是线程安全的。
6. 以上分析基于JDK1.8，其他版本会有些出入，因此不能一概而论。