ArrayList的扩容机制

【饿了么、美团】外卖红包领取地址 >> 能省一点是一点

前提:基于1.8的源码进行分析。

在ArrayList中,是使用一个Object[]数组elementData进行数据的存储的,而一个ArrayList的容量就是这个数组elementData的长度length。

观察ArrayList的2个构造函数源码:

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

无参的构造函数,elementData直接为一个默认的特殊的空数组(相当于一个特殊标记,后续扩容代码中发现这个标记会直接扩容为默认的容量10)
指定初始容量的构造函数,elementData会直接实例化一个指定容量的数组;如果初始容量为0,则elementData赋值为一个默认的空数组。

当我们往ArrayList中添加数据时,会通过一个ensureCapacityInternal函数来保证容量的可用性,也就是说ArrayList是先扩容(如果需要的话)后插入数据的

/**
 * 确保最小容量,如不够则进行扩容
 * @param minCapacity
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算得出需要保证的容量
 * 这里正常情况下都是直接返回入参minCapacity的值,只有当elementData的值为上述提到的无参构造函数中设置的特殊数组时,才会返回默认的容量
 * @param elementData
 * @param minCapacity
 * @return
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * 这里会进行一个判断,只有当前elementData数组小于所需的容量时,才会调用grow进行扩容
 * @param minCapacity
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

从上方的源码以及注释来看,扩容的代码主要是在grow这个函数中:

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

函数的逻辑其实也不复杂,主要是对elementData的长度进行一个1.5倍的扩容,这里使用了一个位运算来实现,效率比用乘号来的高效。

int newCapacity = oldCapacity + (oldCapacity >> 1);

原理是:oldCapacity右移1位,因为是二进制,所以右移1位相当于除以2,再加上原来的oldCapacity,所以得到新的newCapacity相当于是oldCapacity的1.5倍(当然这里面有一个向下取整的精度问题,忽略不计)

grow函数在通过位运算计算出新数组的长度之后,因为oldCapacity可能为0,以及1.5倍向下取整的问题,得到的新容量newCapacity可能还是会比所需容量小,这种情况下新数组容量会直接等于所需容量。额外在考虑一下MAX_ARRAY_SIZE的情况,最终可以得到一个扩容后的新容量。

获取到扩容之后的新容量值,接下来就是直接创建一个新数组并进行一个数据的拷贝,ArrayList的扩容就结束了。


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

金隆兴 【5本装】牛皮纸科目本 B5初中高中生课堂错题本作业本笔记本记事本本子 语数英作文综合本5本装 7511
¥16.80
晨光(M&G)文具A4/20页儿童图画本 美术绘画本 妙想世界系列卡通画画本 10本装APYUWR78考试用品
¥31.50
晨光(M&G)文具16k/58张缝线本 记事本笔记本子 安然时光系列软抄本日记本 4本装APYFA14
¥18.90
海昌(HYDRON)优氧Easyday日抛隐形眼镜10片装官方大牌保湿水润舒适天天抛近视透明眼镜片 10片装【入会享会员活动】 250度
¥38.00
晶华 Console调试线控制线USB转RJ45配置线适用于腾达思科华为TP-LINK路由器交换机 USB转console调试线【进口芯片】3米
¥43.60
励展(LIZHAN) 成人医用外科口罩白色一次性防护防尘口罩轻薄透气独立包装
¥18.80
2022新学霸提分笔记中考必刷题组英语教材全解初一二三中考复习辅导资料初中七八九年级同步练习册英语
¥45.45
闪魔 iPad pro钢化膜2021/2022款air4/5保护膜mini6高清抗蓝光平板类纸膜 【护眼版^滕森抗蓝光】 2022款iPadair5/air4通用
¥37.80