ArrayList扩容详解

ArrayList扩容详解本文探讨一下ArrayList的扩容过程ArrayList底层是数组elementData,用于存放插入的数据。初始大小是0,当有数据插入时,默认大小DEFAULT_CAPACITY=10。如果在创建ArrayList时指定了initialCapacity,则初始大小是ArrayList1.验证扩容的代码示例从示例中可以看到,当添加元素时,如果元素个数+1>当前数组长度【size+1>elementData.length】时,进行扩容,扩容后的数组大小是:oldC.

大家好,又见面了,我是你们的朋友全栈君。

本文探讨一下ArrayList的扩容过程

ArrayList底层是数组elementData,用于存放插入的数据。初始大小是0,当有数据插入时,默认大小DEFAULT_CAPACITY = 10。如果在创建ArrayList时指定了initialCapacity,则初始大小是ArrayList

1. 验证扩容的代码示例

从示例中可以看到,当添加元素时,如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时,进行扩容,扩容后的数组大小是: oldCapacity + (oldCapacity >> 1)

将旧数组内容通过Array.copyOf全部复制到新数组,此时新旧列表的size大小相同,但elementData的长度即容量不同

注意:扩容并不是严格的1.5倍,是扩容前的数组长度右移一位 + 扩容前的数组长度

public class SimpleTest {
    public static void main(String[] args) {
        ArrayList list = new ArrayList();
        int size = 0;
        for (int i = 0; i < 100; i++) {
            list.add(i);
            if(getCapacity(list)>size) {
                 System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size());
                size = getCapacity(list);
            }
        }
    }

    public static Integer getCapacity(ArrayList list) {
        Integer length = null;
        Class clazz = list.getClass();
        Field field;
        try {
            field = clazz.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] object = (Object[]) field.get(list);
            length = object.length;
            return length;
        } catch (Exception e) {
            e.printStackTrace();
        }
        return length;
    }
}

  运行结果如下:

capacity:10,size:1
capacity:15,size:11
capacity:22,size:16
capacity:33,size:23
capacity:49,size:34
capacity:73,size:50
capacity:109,size:74

2. 扩容相关的源代码

 public boolean add(E e) {
       //调用了一ensureCapacityInternal方法,确保数组下标不越界
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

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

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

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;
       //新容量扩大到原容量的大约1.5倍,右移一位相当于原数值除以2,扩容并不是严格的1.5位
        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);
    }

3. 为什么按大约1.5倍扩容

扩容因子的大小选择,需要考虑如下情况:

  1. 扩容容量不能太小,防止频繁扩容,频繁申请内存空间 + 数组频繁复制

  2. 扩容容量不能太大,需要充分利用空间,避免浪费过多空间;

为了能充分使用之前分配的内存空间,最好把增长因子设为 1<k<2.

k=1.5时,就能充分利用前面已经释放的空间。如果k >= 2,新容量刚刚好永远大于过去所有废弃的数组容量

并且充分利用移位操作(右移一位),减少浮点数或者运算时间和运算次数

详见参见: C++ STL 中 vector 内存用尽后, 为什么每次是 2 倍的增长, 而不是 3 倍或其他值?

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130890.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • how to catch error in make error message

    how to catch error in make error message

  • js操作元素属性_如何将ajax返回的网页加载出来

    js操作元素属性_如何将ajax返回的网页加载出来session时使用sessionStorage.Storage表示存储的意思。一.设置值sessionStorage.setItem(key,value);设置元素的值,setItem.类似于服务器端的setAttribute();二.得到值vardata=sessionStorage.getItem(key);类似于服务器端的getAttribute…

    2022年10月10日
  • pycharm如何连接远程服务器_pycharm如何使用远程解释器

    pycharm如何连接远程服务器_pycharm如何使用远程解释器1下载pycharm下载pycharm专业版,通过学校邮箱,注册账号,免费使用。2连接服务器详见参考链接。1Pycharm连接服务器

  • Modelsim SE 下载安装、注册详细教程「建议收藏」

    目录一、ModelsimSE下载及安装参考资料一、ModelsimSE下载及安装百度网盘下载链接:https://pan.baidu.com/s/1a9d-bq9RZmWrRV542X4IEA——提取码:ifte下载完成后,解压缩win64版的modelsim压缩包。双击可执行文件运行。点击【Next】。选择安装路径,然后点击【Next】。点击【Agree】。正在安装…弹窗添加环境变量,点击【允许】,这样就可以从DOS提示符执行Modelsim了。

  • Java中的cas(this关键字java)

    在JDK5之前Java语言是靠synchronized关键字保证同步的,这会导致有锁锁机制存在以下问题:(1)在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。(2)一个线程持有锁会导致其它所有需要此锁的线程挂起。(3)如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置,引起性能风险。volatile是不错的机制

  • Linux下修改配置文件内容

    Linux下修改配置文件内容文件操作之修改配置文件内容在一些系统或者游戏运行时经常遇到一些情况需要修改一下配置文件的内容,比如游戏中任务升级了,需要修改人物等级,那么这是怎么完成的呢?好,我还是老规矩先来介绍一个函数,strstr一样的查看手册可以看到,该函数有两个参数,第一个参数要查询的字符串,第二个参数是目标子字符串,返回值是一个指针,指向子字符串的开头,如果没有那么返回NULL,什么意思呢,举个例子,比如CHINAENGLISH字符串,我要查找ENGLISH,使用strstr后,返回一个字符指针,指到E位置。好,介绍完

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号