ArrayList 扩容机制剖析

1、ArrayList的构造方法

无参构造

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

有参构造

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执行过程

ArrayList list = new ArrayList();

for (int i = 1; i <= 10; i++) {
    list.add(i);
}

for (int i = 11; i <= 15; i++) {
    list.add(i);
}

list.add(100);
list.add(10,200);
list.add(null);
System.out.println(list);
ArrayList list = new ArrayList();

首先进行无参构造执行下面代码

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

其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA为一个空数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

elementData在初始化时为一个空数组

进入for循化

for (int i = 1; i <= 10; i++) {
    list.add(i);
}

首先对int基本数据类型进行装箱,进入Integer的 valueOf的方法

public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

接着执行进入add方法

public boolean add(E e) {    ensureCapacityInternal(size + 1);  // Increments modCount!!    elementData[size++] = e;    return true;}
  • 先确定是否要进行扩容

  • ensureCapacityInternal(size + 1); 
    
  • 然后在进行执行

  • elementData[size++] = e;
    

ensureCapacityInternal方法

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

calculateCapacity方法

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

ensureCapacityInternal方法首先执行力calculateCapacity方法 ,首先确认elementData是不是一个空数组,如果为空数组,则赋值为一个最小容量calculateCapacity方法返回值: minCapacity, 最小容量是求DEFAULT_CAPACITY 和 minCapacity中的最大值. 此时DEFAULT_CAPACITY的大小为10, 而minCapacity为1 .因此calculateCapacity方法大的返回值为10,calculateCapacity方法可以理解为先确定一个minCapacity. 因为到ensureExplicitCapacity(minCapacity)才是确定到底要不要进行扩容。

ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) {    modCount++;    // overflow-conscious code    if (minCapacity - elementData.length > 0)        grow(minCapacity);}
modCount++;//记录当前集合被修改的次数,为了多个线程同时修改它,如果同时修改或抛出一个异常
 if (minCapacity - elementData.length > 0)        grow(minCapacity);

如果最小容量减去当前实际容量大于零说明不够了,例如当前minCapacity为10,实际上容量需要十个,而elementData才为0个,是不够的,显然需要进行扩容。当进行到grow方法是才进行真正的扩容。

grow方法

grow方法是真的扩容方法

private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + (oldCapacity >> 1);  //oldCapacity  + 0.5oldCapacity  即扩容1.5倍    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);}

当第一次进入grow方法,首先将数组大小赋值给oldCapacity,即为0,接着进行判断,如果newCapacity减去minCapacity小于0,即将minCapacity赋值为newCapacity,第一次的时候没有真正使用1.5倍的扩容,即第一次直接扩容为10。

接着进行执行 elementData = Arrays.copyOf(elementData, newCapacity); 使用Arrays.copyOf的目的是为了在原先的基础上进行扩容,保护原来的数据。

接着一步步返回一直到add()方法。此时 elementData 已经变成了10个空间。

然后执行elementData[size++] = e; 此时size为0,即将元素放到下标为0的位置。注意size是先赋值后加加的

执行流程

ArrayList 扩容机制剖析

总结:

  • ArrayList中维护了一个Object类型的数组elementData。transient Object[] elementData;
  • 当创建ArrayList对象是,如果使用的是无参构造器,则初始elementData容量为0,第一次添加,则扩容elementData为10,如需要再次扩容,则扩容elementData为1.5倍。
  • 如果使用的是指定大小的构造器,则初始elementData容量为指定大小,如需要扩容,则直接扩容elementData为1.5。
上一篇:ArrayList返回值


下一篇:ArrayList