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)


相关推荐

  • java 环境变量配置_java环境变量的详细配置「建议收藏」

    java 环境变量配置_java环境变量的详细配置「建议收藏」前言学习java的第一步就要搭建java的学习环境,首先是要安装JDK,JDK安装好之后,还需要在电脑上配置”JAVA_HOME”、”path”、”classpath”这三个环境变量才能够把java的开发环境搭建好。在没安装过jdk的环境下,path环境变量是系统变量,本来存在的,而JAVA_HOME和classpath是不存在的。一、配置JAVA_HOME变量操作步骤(win7系统):计算机…

  • JavaSwing_2.3: JRadioButton(单选按钮)「建议收藏」

    JavaSwing_2.3: JRadioButton(单选按钮)「建议收藏」JRadioButton,单选按钮。

  • goland2021 激活码[在线序列号]「建议收藏」

    goland2021 激活码[在线序列号],https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • Windows操作系统双因素身份认证解决方案

    Windows操作系统双因素身份认证解决方案Windows桌面帮助企业将办公桌面快速、集中部署在平台上,方便进行管理维护且节省企业成本,能让员工随时随地登录到自己的windows桌面环境中,实现移动办公。安全事件频发的现在,在单一的静态密码登录验证机制下,非法入侵者若窃听到桌面登录账号的用户名及密码,即可通过合法访问权限访问内部系统,企业信息安全面临挑战;企业为防止账号信息泄露,通常强制要求员工定期更换登录密码,给员工及IT运维人员带来许多不必要的麻烦;其次没有及时收回的账号,离职员工仍然有桌面的合法访问权限,因此额外增加了IT部门的账号回收管理

    2022年10月28日
  • Python 类继承,__bases__, __mro__, super

    Python 类继承,__bases__, __mro__, super

    2021年12月14日
  • 成功鲜有偶然:一览IT名人的教育成长经历

    成功鲜有偶然:一览IT名人的教育成长经历由于篇幅有限,只列举受公共认知度较高的创始人(百度百科对应人物词条被顶超过1000次)国内三强:李彦宏(百度创始人):本科就读于北京大学,硕士就读于布法罗纽约州立大学。曾任Infoseek工程师。马云(阿里巴巴创始人):本科就读于杭州师范学院。马化腾(腾讯创始人):本科就读于深圳大学。大三门户网站:王志东(新浪创始人):本科就读于北京大学,点击科技创始人。丁磊(网易创始人):本科就读于电子科

发表回复

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

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