ArrayList类源码解析——ArrayList动态数组的实…

2019-04-18 08:57:23来源：博客园阅读 ()

一、基本概念

ArrayList是一个可以添加对象元素，并进行元素的修改查询删除等操作的容器类。ArrayList底层是由数组实现的，所以和数组一样可以根据索引对容器对象所包含的元素进行快速随机的查询操作，其时间复杂度为O(1)。但是和数组不同的是，数组对象创建后数组长度是不变的，ArrayList对象创建后其长度是可变的，所以ArrayList也称为动态数组，那么ArrayList的动态数组数据结构又是如何实现的呢?接下来打开ArrayList源码看看。

二、源码分析

2.1、ArrayList类的继承与实现

图2.1 ArrayList类的继承与实现（不包括继承ArrayList的类）

从继承接口可以发现，ArrayList继承了AbstractCollection抽象类，实现了List接口，并且实现还实现了RandomAccess，Cloneable和Serializable三个标记接口，所以ArrayList的的对象具有能根据索引对元素进行快速随机访问、可以调用Object的clone()方法、可以进行序列化的特性。有关Java的标记接口是什么，在上一篇文章

《Java的四个标记接口Serializable、Cloneable、RandomAccess和Remote接口》进行了总结

2.2、ArrayList的属性

通过源码可以知道ArrayList主要有以下属性

 private static final long serialVersionUID = 8683452581122892189L;//用于ArrayList对象序列化的版本ID

 private static final int DEFAULT_CAPACITY = 10;//ArrayList对象的默认容量大小

 private static final Object[] EMPTY_ELEMENTDATA = {};//用于Null的ArrayList对象
   
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//用于创建一个默认容量大小的ArrayList对象

 transient Object[] elementData; //用于创建动态大小的ArrayList对象，这个实例变量引用的数组可以说就是ArrayList容器
 
 private int size;//ArrayList对象的尺寸

2.3、ArrayList类的三个构造函数

一个无参构造函数，一个传入一个int 量指定容量的构造函数和一个传入一个容器对象来进行初始化的构造函数

    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初始容量的构造器

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//一个默认容量的ArrayList无参构造器
   
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
          
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
//一个参数为一个容器对象的构造器，将该容器对象转化为一个数组对象后，将ArrayList对象内的数组引用elementData初始化为这个数组对象（Object[]）

2.4、ArrayList动态数组的具体实现细节

ArrayList对象创建后，是怎么改变这个对象的容量实现动态数组的呢，来看看动态数组实现的几个重要方法

grow方法。实现了ArrayList对象容量增加的方式，一般ArrayList新的容量为原容量的1.5倍大小，源码如下

  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//int整型的最大值减8
private void grow(int minCapacity) {
    
        int oldCapacity = elementData.length;//原ArrayList对象的容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);//新的容量变为原容量+原容量/2,也就是新的容量增大为原来的1.5倍
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
//新的容量如果还是小于指定容量，则新容量的值更新为指定容量
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
//如果新容量大于int整数的最大值减8的值，则调用hugeCapacity(minCapacity)，新的容量为Interger.MAX_VALUE,即最大的Int整数
        elementData = Arrays.copyOf(elementData, newCapacity);
//创建一个数组长度为newCapacity，包含所有原ArrayList内elementData所有元素的新的elementDate数组

hugeCapacity方法，在grow方法中被调用

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

View Code

trimToSize方法。将ArrayList对象内的elementData对象的长度变为size，size变量保存了ArrayList对象所含元素个数。使用这个方法可以使ArrayList对象内的elementData数组长度为元素个数，以避免不必要的内存占用。

public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
        }
//当size小于elementData，如果size=0，令elementData为一个空数组；size>0,使elementDate数组变量指向包含原elememtData所有元素，且长度为元素个数size的新数组
    }

ensureExplicitCapacity方法，在参数minCapacity大于elementDate引用的数组的长度时，调用grow方法来增加容量

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

ensureCapacity方法，如果构造ArrayList对象时调用的是无参构造器，此时elementDate数组还没创建，这个方法调用后可以确保ArrayList对象容量至少为10（默认值），且不小于minCapacity参数指定的值

    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

ensureCapacityInternal方法，在调用add方法增加元素时，调用这个方法来确保元素个数+1(size+1)小于或等于elementDate数组的长度，若size+1大于element.length，在ensureExplicitCapacity方法中会调用grow方法对ArrayList对象进行扩容

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

}

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

/*Arraylist类调用无参构造器初始化后，elementData数组初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA（一个空对象数组Object{}），若elementDate为初始化的值这里返回的是默认容量和minCapacity中的较大值*/
}
return minCapacity;//若elementDate不是初始化的值，这个方法直接返回minCapacity的值
}

add(int index)方法，实现了在指定的索引处添加元素，时间复杂度为O(n)

public void add(int index, E element) {
        rangeCheckForAdd(index);//先检测索引是否越界

        ensureCapacityInternal(size + 1); //确保ArrayList的容量，即elementData数组的长度，在添加元素前大于size+1
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
//将从index处以及后面的元素的都向后移动一位，索引+1。所以调用这个方法的时间复杂度为O(n)
        elementData[index] = element;
//将元素element添加到索引为index的位置
        size++;//元素个数加一
    }

remove(int index)方法，实现了在指定的位置删除元素，时间复杂度为O(n)

 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);
//将这个元素后面的元素的前移一位，索引减一，原来index处的元素（要被删除的元素）被后面一位的元素覆盖。所以这个方法的时间复杂度为O(n)
        elementData[--size] = null;

//数组索引为size处没有元素，使其为空，元素个数size-1
        return oldValue;
//将删除的元素作为方法的返回值
    }