ArrayList源码分析以及自动扩容实现

ArrayList源码分析以及自动扩容实现

• ArrayList的三个构造方法
• ArrayList不同构造方法的自动扩容实现
• 总结

ArrayList的三个构造方法

在分析集合的源码实现之前，必须从构造方法入手，集合的初始化从此处开始，调用不同的构造方法将会发生不同的情况。
开始之前有必要对ArrayList的成员变量做个认识：

// ArrayList的核心，存储数据的Object数组
transient Object[] elementData;

// 内部默认的数组元素大小
private static final int DEFAULT_CAPACITY = 10;

/*
记录elementData中非空元素的个数，即实际ArrayList中元素个数
注意不是elementData.length
*/
private int size;

/*
记录ArrayList的改变次数，此成员变量不在ArrayList
定义在父类AbstractList内
*/
protected transient int modCount = 0;

/*
空数组，与DEFAULTCAPACITY_EMPTY_ELEMENTDATA类似
类似空数组的标记，后面会提到
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

// 空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

下面简单说一下EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA都是{}空的Object[]数组，为何设计两个：

1. 在实现扩容的时候，elementData赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组将会使用ArrayList内置的DEFAULT_CAPACITY = 10作为首次添加元素时的初始elementData.length。
2. 而elementData被赋值EMPTY_ELEMENTDATA时，自动扩容时会使用size即从0开始扩容。

这里也有个JDK7与JDK8的ArrayList的实现区别：
JDK7的指定初始化容量大小的构造方法实现为：

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                initialCapacity);
    /*
    此处如果指定了initialCapacity且不小于0的话
    JDK7会new一个大小为initialCapacity的Object[]数组
    无疑会增加内存开销
    
    而JDK8则将EMPTY_ELEMENTDATA赋值给elementData
    而在调用ArrayList的add()方法添加元素时才会自动扩容
    增加elementData的数组容量大小
    */
    this.elementData = new Object[initialCapacity];
}

1、指定了初始化大小的ArrayList(int initialCapacity)构造方法

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

该构造方法提供了指定了elementData数组初始容量大小的参数，代码可以看到，如果指定的initialCapacity大于0，则会new一个该大小的Object[]数组，此时elementData.length = initialCapacity，只不过里面存的都是null，否则initialCapacity = 0 时，elementData被赋值为EMPTY_ELEMENTDATA：this.elementData = EMPTY_ELEMENTDATA

2、空参构造方法

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

空参构造方法，会将内部的DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData，即初始化一个空的数组，记住这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA

3、提供Collection接口实现类参数的构造方法

public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            // replace with empty array.
            elementData = EMPTY_ELEMENTDATA;
        }
    }

该构造方法需要传入一个实现Collection接口的实例对象作为参数，这里分为两种情况，传入的集合对象中无元素与有元素。

1. 传入的集合参数包含元素时，会先去判断集合的类型Class是否为ArrayList类型，相同就把传入集合的实际元素存储数组Object[] a = c.toArray()赋值给elementData数组，不同则调用Arrays的copyOf进行数组元素复制以及类型转换为Object[]类型再赋值给elementData数组
2. 传入的集合参数没有元素时，会将内部的EMPTY_ELEMENTDATA空数组赋值给elementData，这里是该构造方法与空参构造方法处理空数组时的区别，这里前面也提到会影响ArrayList的自动扩容机制。

ArrayList不同构造方法的自动扩容实现

上面的构造方法可以看出，JDK8实现ArrayList的时候，如果没有指定初始化大小或者没有传入存在元素的集合实例化ArrayList的时候，其实际存储元素的elementData数组要么被指定为EMPTY_ELEMENTDATA，要么就被指定为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，在调用add()方法添加元素自动扩容时才提升容量。而JDK7的实现是：初始化时直接new一个大小为initialCapacity的Object[]，无疑这是一个ArrayList的JDK8实现的性能优化。
下面是ArrayList的add()方法以及自动扩容方法的实现

	// add()方法
	public boolean add(E e) {
		// 自动扩容方法
	    ensureCapacityInternal(size + 1);  // Increments modCount!!
	    elementData[size++] = e;
	    return true;
	}
	
	// 自动扩容方法
	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);
	     	}
	        return 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;
     // 大小增长为原大小的1.5倍
     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);
    }

下面看一下ArrayList调用不同构造方法的自动扩容情况

1. 调用指定初始化大小的构造方法

此时elementData要么为Object[initialCapacity]长度为initialCapacity，要么为空数组EMPTY_ELEMENTDATA

1. 在调用add()方法时，首先调用方法ensureCapacityInternal(size + 1)检查elementData的length并决定是否扩容，首次添加元素时，无疑size=0，即传入1
2. 随后进到calculateCapacity(Object[] elementData, int minCapacity)方法内，判断elementData是否为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，无疑不是，直接返回1
3. 再调用ensureExplicitCapacity(int minCapacity)方法，方法内包含真正实现扩容的grow(minCapacity)方法，条件是minCapacity - elementData.length > 0，这里如果指定的initialCapacity大于0的话，首次肯定是不需要扩容的。如果elementData.length为0的话，add()方法最少需要数组有一个位置，而elementData.length=0就需要扩容，不然就抛数组下标越界异常了，这里也是为什么ArrayList为什么使用数组实现，明明看着容量不够，却不会数组下标越界异常。
4. 再看看grow(int minCapacity)方法，传入值为1，里面的代码核心就是这句int newCapacity = oldCapacity + (oldCapacity >> 1)，将容量计算为原先容量的1.5倍，首次添加元素时，elementData的容量会被扩大为1，这是elementData = EMPTY_ELEMENTDATA的情况。
5. 如果elementData = Object[initialCapacity]长度大于0的话，则在ensureExplicitCapacity(int minCapacity)方法的判断if (minCapacity - elementData.length > 0)处决定是否需要扩容，即：当我添加元素需要这么大空间时，但是elementData.length的大小不够，就需要扩容了。

2. 调用空参构造方法

elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 空数组：this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

1. 调用add()方法，同样走到calculateCapacity(Object[] elementData, int minCapacity)方法内
2. 不同的是条件if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)成立，方法ensureExplicitCapacity(int minCapacity)入参minCapacity = 10
3. ensureExplicitCapacity(int minCapacity)内，条件if (minCapacity - elementData.length > 0)成立，即开始扩容grow(int minCapacity)
4. grow(int minCapacity)内部代码执行后elementData.length为DEFAULT_CAPACITY = 10
5. 即调用空参构造时，首次添加元素时，ArrayList的elementData的容量将被扩大至10，注意此时size=0，仅仅是elementData的长度变为10，且内部均是null元素。

3、调用传参Collection接口实现类的构造方法

调用此构造方法实例化时，也存在俩种情况，传入的集合size为0，或者集合存在元素。存在元素的情况与调用指定initialCapacity且大于0的情况相同，这里不再分析。当传入的集合无元素的时候：

1. elementData被直接赋值为EMPTY_ELEMENTDATA空数组： elementData = EMPTY_ELEMENTDATA。
2. 同样在添加元素调用add()方法的时候，判断是否需要扩容，这里与调用空参构造方法的区别是，空参构造的elementData被指定为：this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，而此处elementData 为EMPTY_ELEMENTDATA，在自动扩容前的方法calculateCapacity(Object[] elementData, int minCapacity)判断条件if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)不成立，return出的也就不是DEFAULT_CAPACITY = 10了，而是首次添加元素时的size+1 = 0，所以自动扩容的时候是从0开始，每次扩容1.5倍。

总结

1. ArrayList的三个构造方法，除了指定大于0的初始容量以及传入集合且size不为0，会创建指定大小的elementData，其他情况下elementData的长度均为0，要么为EMPTY_ELEMENTDATA，要么为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，并非是ArrayList的初始容量为10。
2. elementData赋值为EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA的一个区别是，首次add元素时，后者elementData数组长度会被初始化为DEFAULT_CAPACITY = 10，扩容每次1.5倍：0->10->15->22->33->...，而EMPTY_ELEMENTDATA会从elementData.length = 0开始扩容为1，扩容每次1.5倍：0->1->2->3->4->6->9->13->...。
3. 此处也可以看出“为什么阿里巴巴建议集合初始化时，指定集合容量大小”，因为当指定elementData = EMPTY_ELEMENTDATA的时候，扩容从0开始，前几次添加元素时，每次都需要扩容（0->1->2->3->4），耗费性能，而指定初始值为10的时候，下次elementData需要扩容时会扩大到15以此类推，而省去下次添加元素继续扩容。

以上为个人学习ArrayList源码的个人见解，如果错误敬请指正互相学习，谢谢！

本文地址：https://blog.csdn.net/weixin_43584430/article/details/110223055