美文网首页
ArrayList的动态扩容

ArrayList的动态扩容

作者: 叫我小码哥 | 来源:发表于2018-04-14 13:03 被阅读0次

        ArrayList的底层是动态数组,初始容量为10,增长因子为1.5。在JDK1.7的时候默认的初始容量是在无参的构造方法中给出,在JDK1.8的时候默认容量是在第一次调用add方法时设置初始化的。本篇文章主要写的是ArrayList在jdk1.8时的扩容。

jdk1.7的时候

数组的大小

private static final int DEFAULT_CAPACITY = 10;

默认空数组元素

transient Object[] elementData;

默认初始化容量

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

记录被修改的次数执行add或者remove方法

private int size;

public ArrayList() {    

        super();

        this.elementData = EMPTY_ELEMENTDATA;

}

public ArrayList(int initialCapacity) {       

         super();        

        if (initialCapacity < 0)            

        throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);       

         this.elementData = new Object[initialCapacity];

}

jdk1.8

数组的大小

private static final int DEFAULT_CAPACITY = 10;

默认空数组元素

transient Object[] elementData;

默认初始化容量

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

记录被修改的次数执行add或者remove方法private int size;

初始容量为0

public ArrayList() {

this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}

调用add方法时进行size+1,在调用ensureCapacityInternal方法

public boolean add(E e) {

ensureCapacityInternal(size +1);// Increments modCount!!

    elementData[size++] = e;

return true;

}

ensureCapacityInternal方法主要进行数组的初始化工作,将数组的初始化为10,初始化完成后去执行ensureExplicitCapacity方法

private void ensureCapacityInternal(int minCapacity) {

if (elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

ensureExplicitCapacity(minCapacity);

}

进入ensureExplicitCapacity方法首先进行modCount自增,然后判断当前数组元素的个数是否大于数组的长度,如果不大于则不需要进行扩充,如果大于则需要grow方法进行扩充。

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;

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

}

总结:

jdk1.8时ArrayList的扩充规则为。当第一次调用add方法时,首先对数组中元素的个数进行增加,其次调用ensureExplicitCapacity方法进行数组的初始化工作,接着调用ensureExplicitCapacity方法查看已有的元素是否大于数组的长度,如果不大于则不进行扩充,如果大于则进行调用grow方法进行扩充。扩充一共分为5步,第一步先获取原数组容量,然后设置新数组的容量是原数组容量的1.5倍,如果新容量小于老容量则将老容量的值设置给新容量。如果新容量的值大于数组的最大值调用hugeCapacity方法。最后调用copyOf在原数组上增加容量。

相关文章

网友评论

      本文标题:ArrayList的动态扩容

      本文链接:https://www.haomeiwen.com/subject/cpxlkftx.html