Java中的ArrayList容量及扩容方式

• 查看jdk1.8 arraylist的源代码
• 2、最大容量为 integer.max_value - 8
• java arraylist() 扩容原理
• 先看下 arraylist 的属性以及构造方法，这个比较重要

查看jdk1.8 arraylist的源代码

1、默认初始容量为10

   /**
     * default initial capacity.
     */
    private static final int default_capacity = 10;

2、最大容量为 integer.max_value - 8

    /**
     * the maximum size of array to allocate.
     * some vms reserve some header words in an array.
     * attempts to allocate larger arrays may result in
     * outofmemoryerror: requested array size exceeds vm limit
     */
    private static final int max_array_size = integer.max_value - 8;

原因：之前参考别人的，有待求证：

数组对象有一个额外的元数据，用于表示数组的大小；

数组长度size为int类型，共32位，有一位符号位，所以最大长度为integer.max_value=2^31= 2,147,483,648；

8bytes用来存储size；

3、扩容方式：

（1）首先传递进来一个希望的最小容量mincapacity；

（2）新容量newcapacity = oldcapacity + (oldcapacity >> 1)，即新容量等于原容量的1.5倍；

（3）如果mincapacity > newcapacity ，newcapacity = mincapacity ;

（4）如果 newcapacity > 最大容量 max_array_size ，newcapacity = hugecapacity(mincapacity);

（5）以新容量拷贝原数据

   /**
     * increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param mincapacity the desired minimum capacity
     */
    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);
    }
 
    private static int hugecapacity(int mincapacity) {
        if (mincapacity < 0) // overflow
            throw new outofmemoryerror();
        return (mincapacity > max_array_size) ?
            integer.max_value :
            max_array_size;
    }

java arraylist() 扩容原理

平常都是直接使用 arraylist()，今天特地看一下 arraylist() 的扩容原理。

先看下 arraylist 的属性以及构造方法，这个比较重要

先看下属性

// arraylist 默认容量大小
private static final int default_capacity = 10;
// 一个共享的空数组, 在空实例时使用
private static final object[] empty_elementdata = {};
// 一个共享的空数组, 在使用默认 size 的空实例时使用
private static final object[] defaultcapacity_empty_elementdata = {};
/*
存储 arraylist 元素的数组缓冲区
重点1: arraylist 的容量是数组缓冲区的长度
重点2: 从这个元素也可以看的出来 arraylist() 的底层就是一个 object[]  
add 第一个元素时, 任何带有 elementdata == defaultcapacity_empty_elementdata 的空 arraylist 都将被扩展为 default_capacity
*/
transient object[] elementdata;
// arraylist 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size
private int size;
// arraylist 最大
private static final int max_array_size = integer.max_value - 8;

再看构造器，带参构造器

/*
带参构造器, 参数为容量大小, 例如: 初始化一个容器为 20 类型为 integer 的 arraylist
arraylist<integer> list = new arraylist<>(20);
*/
public arraylist(int initialcapacity) {
 /*
 初始化容量 > 0, elementdata 初始化为初始化容量大小的数组
 初始化容量 = 0, elementdata = empty_elementdata (空数组)
 初始化容量 < 0, 直接抛出异常
 */
    if (initialcapacity > 0) {
        this.elementdata = new object[initialcapacity];
    } else if (initialcapacity == 0) {
        this.elementdata = empty_elementdata;
    } else {
        throw new illegalargumentexception("illegal capacity: "+
                                           initialcapacity);
    }
}

参数为 collection 的构造器

/*
将一个参数为 collection 的集合转换为 arraylist
*/
public arraylist(collection<? extends e> c) {
    // collection 转换为数组 object[] 类型 
    elementdata = c.toarray();
    // 判断当前对象大小是否和 collection 长度相等并且不等于 0, false 的话 elementdata 等于空数组了
    if ((size = elementdata.length) != 0) {
     // c.toarray() 可能不会正确地返回一个 object[] 数组，所以使用 arrays.copyof()
        if (elementdata.getclass() != object[].class)
            elementdata = arrays.copyof(elementdata, size, object[].class);
    } else {
        this.elementdata = empty_elementdata;
    }
}

不带参构造器

/*
不带参构造器就像我们平时使用一样, 直接 new 一个 arraylist 不需要传递任何参数
构造方法中直接将 elementdata 初始化为 defaultcapacity_empty_elementdata (空数组)
*/
public arraylist() {
    this.elementdata = defaultcapacity_empty_elementdata;
}

看到这里就发现，带参的构造器我们可以直接传递参数，而默认的构造器怎么怎么样初始化容量大小的呢？

add() 方法可以直接得到答案。

public boolean add(e e) {
 // 这一行是关键, 看下面
    ensurecapacityinternal(size + 1);
    // 将元素追加到集合的末尾 假如当前 size = 10 size++ 追加到第 11 位
    elementdata[size++] = e;
    return true;
}

ensurecapacityinternal() 方法调用

private void ensurecapacityinternal(int mincapacity) {
 /*
 calculatecapacity() 方法, 刚初始化时会返回 10, 其他情况返回当前 size + 1
 ensureexplicitcapacity() 方法, 调用扩容
 */
    ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
private static int calculatecapacity(object[] elementdata, int mincapacity) { 
 /*
 使用无参构造器创建创建 arraylist 的集合, 此时一定是相等的
 */
    if (elementdata == defaultcapacity_empty_elementdata) {
     /*
     两数相比返回最大值, 此时 math.max(10, 1); 
     默认容量, 由此而来
     */
        return math.max(default_capacity, mincapacity);
    }
    // 不相等的话只有返回当前的 size + 1
    return mincapacity;
}
private void ensureexplicitcapacity(int mincapacity) {
    // 增量, 记录修改/更新次数
    modcount++;  
    
     // 初始化: 10 - 0 > 0
     // 其他: size + 1 > 0
    if (mincapacity - elementdata.length > 0)
     // 扩容操作
        grow(mincapacity);
}
private void grow(int mincapacity) {
    // 老的长度, 初始化时为 0, 
    int oldcapacity = elementdata.length;
    // 新的长度此时 0 + (0 >> 1), newcapacity = 0
    int newcapacity = oldcapacity + (oldcapacity >> 1);
    // 初始化场景: 0 - 10 < 0 ? true newcapacity = 10
    if (newcapacity - mincapacity < 0)
        newcapacity = mincapacity;
    // 初始化场景: 10 - 2147483639 > 0 返回 false
    if (newcapacity - max_array_size > 0)
     // 超大长度才可以执行这个方法, 必须大于 max_array_size 一般不会
        newcapacity = hugecapacity(mincapacity);
    // 复制原数组中的元素, 并扩容
    elementdata = arrays.copyof(elementdata, newcapacity);
}

上看说的是初始化场景，下面看一下其他场景，也是相当简单

private void ensurecapacityinternal(int mincapacity) {
 /*
 calculatecapacity() 方法, 正常扩容返回 size + 1, 比如 10 + 1, 因为默认长度为 10 当再次新增数据时就会出发扩容
 ensureexplicitcapacity() 方法, 调用扩容
 */
    ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
private static int calculatecapacity(object[] elementdata, int mincapacity) { 
    if (elementdata == defaultcapacity_empty_elementdata) {
        return math.max(default_capacity, mincapacity);
    }
    /*
 elementdata 不等于空数组
 返回当前的 size + 1, 即 10 + 1 返回 11
 */
    return mincapacity;
}
private void ensureexplicitcapacity(int mincapacity) {
    // 增量, 记录修改/更新次数
    modcount++;  
    
    // 其他: 11 - 10 > 0 true, 触发扩容, 如果当前下表是 5 的话 5 + 1 =6, 6 < 10 是, 此时不会出发扩容
    if (mincapacity - elementdata.length > 0)
     // 扩容操作
        grow(mincapacity);
}
private void grow(int mincapacity) {
    // 老的长度 10
    int oldcapacity = elementdata.length;
    // 新的长度此时 10 + (10 >> 1), newcapacity = 15
    int newcapacity = oldcapacity + (oldcapacity >> 1);
    // 15 - 11 < 0 ? false
    if (newcapacity - mincapacity < 0)
        newcapacity = mincapacity;
    // 15 - 2147483639 > 0 返回 false
    if (newcapacity - max_array_size > 0)
     // 超大长度才可以执行这个方法, 必须大于 max_array_size 一般不会
        newcapacity = hugecapacity(mincapacity);
    // 复制原数组中的元素, 并扩容 newcapacity = 15
    elementdata = arrays.copyof(elementdata, newcapacity);
}

结论

1、 触发扩容的关键是

当前 size + 1 是否大于当前容量，如果大于容量则证明，集合不够用了，需要扩容。如果小与当前容量则证明集合还有容量不需要扩容！

2、 每次扩容的大小是

oldcapacity + (oldcapacity >> 1) 即: 10 + (10 >> 1)

即：当前容量的 1.5 倍！

以上为个人经验，希望能给大家一个参考，也希望大家多多支持。