【闲笔杂谈】ArrayList的构造与扩容机制

举报
未见花闻 发表于 2022/11/30 21:36:48 2022/11/30
【摘要】 ⭐️前面的话⭐️本篇文章将介绍Java中ArrayList的扩容机制,其实创建ArrayList对象的时候,系统并没有给ArrayList中数组开辟空间,第一次开辟空间的时机是第一次插入数据的时候。 1.谈谈你对构造ArrayList对象的理解。当构造ArrayList对象时,如果使用的无参的构造方法,ArrayList数组的空间大小为0,因为使用构造方法构造时,自己内部的保存数据的数组并没...

⭐️前面的话⭐️

本篇文章将介绍Java中ArrayList的扩容机制,其实创建ArrayList对象的时候,系统并没有给ArrayList中数组开辟空间,第一次开辟空间的时机是第一次插入数据的时候。

1.谈谈你对构造ArrayList对象的理解。

当构造ArrayList对象时,如果使用的无参的构造方法,ArrayList数组的空间大小为0,因为使用构造方法构造时,自己内部的保存数据的数组并没有申请空间,如何证明。源码就是最好的证明,在Java1.8版本中,调用ArrayList的无参数构造方法后,顺序表中的数组只是一个空数组,容量为0。

img

img

我们在来看看含参数的构造方法,ArrayList含有参数的构造方法有两个,一个给定容量来进行ArrayList对象的实例。

img

我们来分析一下代码的意思,大致的意思就是:

  • 如果给定的初始容量大于0,就会指定一个初始指定容量的数组。
  • 如果指定的初始容量等于0,那就相当于调用了无参的构造方法,顺序表中的数组仅仅只是一个空数组。
  • 其他情况,比如你给了一个负的初始容量,抛出一个IllegalArgumentException非法数据异常的大礼物送给你。

还有一个含参数的构造方法,那就是你可以传入其他的Collection对象,可以根据这个Collection对象保存的数据来构造ArrayList对象。

img

构造方法执行的基本逻辑如下:

  • 第一步,使用toArray方法将集合中的元素转换为数组。
  • 第二步,计算数组的大小,如果为0,则构造的顺序表中的数据只是一个空数组,如果大小不为0,则继续进行判断。
  • 第三步,判断原来集合的类型是否是ArrayList,如果是,那直接将转换的数组直接给构造的ArrayList对象,否则拷贝一个数组给构造的ArrayList对象。

(其实目前我还有点不理解为什么还要拷贝数组,直接将a数组对象赋值上去不好吗,还省资源)

2.谈谈对ArrayList扩容机制的理解。

我们知道使用无参构造方法构造ArrayList对象,里面的数组大小为0,当添加元素或者数组满时添加元素都是需要触发扩容操作的,我们来看一看ArrayList中add方法的执行逻辑:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

在正式添加元素之前,会先去确认数组是否已满,如果满了,则扩容,下面我们来看看具体判断是否需要扩容的方法ensureCapacityInternal,传入参数的含义是最小需要的容量minCapacity。

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

如果发现原来的数组就是一个空数组,就会返回默认容量DEFAULT_CAPACITY(默认为10)与所需最小容量其中一个较大的值,如果不是空数组,直接返回最小所需容量值。

最后就会根据ensureExplicitCapacity方法根据传入的数组与最小所需容量进行扩容

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

这个grow方法会先得到原来数组的1.5倍大小,如果比最小所需容量要小,则最终扩容的数组的大小为最小所需容量大小,否则最终扩容就是1.5倍扩容。

然后在判断最终扩容的容量是否比MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8大,如果比这个数大则调用hugeCapacity方法。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();    
    return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

hugeCapacity方法就会去判断最小所需容量是否溢出(就是验证是否<0),如果溢出,说明顺序表最大大小最大也不够用,直接抛出一个OutOfMemoryError错误。

否则最终的容量取决于最小所需容量minCapacity与MAX_ARRAY_SIZE的大小:

  • minCapacity>MAX_ARRAY_SIZE返回Integer.MAX_VALUE
  • 否则返回MAX_ARRAY_SIZE

3.总结

ArrayList扩容时,如果原数组不是空数组,会计算一个最小所需容量,就是插入元素后最小需要的容量,如果这个容量超过了原数组的大小,按照grow方法的逻辑进行扩容:

  • 如果最小所需容量大于1.5倍原容量,最终扩容的数组的大小为最小所需容量。
  • 如果最小所需容量不大于1.5倍原容量,最终扩容的数组大小为1.5倍原容量。
  • 如果得到的最终容量大小大于MAX_ARRAY_SIZE,则判断最小所需容量是否溢出,如果溢出就抛出异常,没有的话,最终扩容的容量取决于最小所需容量与的MAX_ARRAY_SIZE前者大就取最终容量大小为Integer.MAX_VALUE后者大最终扩容容量就取MAX_ARRAY_SIZE。

如果扩容之前的数组为空数组,则新的最小所需容量取原来得到的最小所需容量与默认容量DEFAULT_CAPACITY(默认为10)中的较大值,后面的扩容逻辑不变。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200