欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-28 16:27:52
ArrayList源码分析以及自动扩容实现ArrayList的三个构造方法1、指定了初始化大小的ArrayList(int initialCapacity)构造方法2、空参构造方法3、提供Collection接口实现类参数的构造方法ArrayList不同构造方法的自动扩容实现1. 调用指定初始化大小的构造方法2. 调用空参构造方法功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建...

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_ELEMENTDATADEFAULTCAPACITY_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_ELEMENTDATAthis.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一个大小为initialCapacityObject[],无疑这是一个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)检查elementDatalength并决定是否扩容,首次添加元素时,无疑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.lengthDEFAULT_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,而此处elementDataEMPTY_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_ELEMENTDATADEFAULTCAPACITY_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

相关标签: Java 源码