ArrayList扩容机制

简介: ArrayList 添加元素时,首先调用 `ensureCapacityInternal()` 确保容量足够。首次添加时,最小容量设为默认值10,触发扩容;后续添加若超出当前容量(初始10,每次扩容1.5倍),则调用 `grow()` 扩容。`grow()` 将容量增加50%,并通过 `Arrays.copyOf()` 创建新数组。注意:`length` 用于数组,`length()` 用于字符串,`size()` 用于集合。

image.png
再来看看ensureCapacityInternal()方法,可以看到add()方法首先调用了ensureCapacityInternal(size+1)
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//获取默认的容量和传入参数的较大值(第一次的较大值是DEFAULT_CAPACITY=10,minCapacity=1)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}

image.png
我们来仔细分析一下

  1. 当我们要add进第一个元素到ArrayList时,elementData.length为0(因为还是一个空的list,里面还没有数据,所以没有进行扩容,默认扩容10),因为执行了ensureCapacityInternal()方法,所以minCapacity此时为10。此时,minCapacity - elemetData.length > 0(minCapacity=10,elemetData.length=0)成立,所以会进入==grow(minCapacity)==方法。
  2. 当add第2个元素时,minCapacity为2,此时elementData.length(容量)在添加第一个元素后扩容成10了。此时,minCapacity - elementData.length > 0不成立,所以不会进入(执行)==grow(minCapacity)==方法。
  3. 添加第3、4…到第10个元素时,依然不会执行==grow()==方法,数组容量都为10。
    知道添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进行grow方法进行扩容
  4. grow方法
    private void grow(int minCapacity) {
    // oldCapacity为旧容量,newCapacity为新容量
    int oldCapacity = elementData.length;//(0,10,15)
    //将oldCapacity右移一位,其效果相当于oldCapacity/2;
    // 我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么久把最小需要容量当作数组的新容量
    if (newCapacity - minCapacity < 0)
     newCapacity = minCapacity;
    
    //判断新容量是否大于集合的最大容量(一般大不了)
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     newCapacity = hugeCapacity(minCapacity);
    
    // 给elementData从新赋值(10,15)
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
    int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍!

通过例子探究一下grow()方法
当add第一个元素时,oldCapacity为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity不比MAX_ARRAY_SIZE大,则不会进入hugeCapacity方法。数组容量为10,add方法中return true,size增为1。
当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中rerurn,true,size增为11。
以此类推…
这里补充一点比较重要,但是容易被忽视掉的知识点:
java中的length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了length这个属性。
java中的length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法。
java中的size() 方法是针对泛型集合说的,如果想看这个泛型有多少元素,就调用此方法类查看!

相关文章
|
5月前
|
缓存 测试技术 Go
腾讯新闻APP的消息推送Push架构技术重构实践
本文主要分享的是腾讯技术团队近年来对腾讯新闻消息推送PUSH系统做的架构优化和技术实践。
542 142
|
5月前
|
Java 关系型数据库 MySQL
基于springboot的二手物品交易系统
本研究聚焦二手交易平台的网络化转型,探讨其在社会经济快速发展背景下的必要性与意义。结合SpringBoot、Java、MySQL等技术,分析系统设计与实现路径,旨在提升平台管理效率、降低成本,推动二手交易向规范化、信息化发展,助力现代化服务体系建设。
|
5月前
|
存储 弹性计算 安全
阿里云“99套餐”活动解析:套餐相关规则及云产品及组合配置与价格参考
阿里云“99套餐”是阿里云为了助力个人和中小企业无忧上云而推出的套餐组合活动,目前活动截止日期已延长到2027年3月31日。“99套餐”为在选购云服务器的同时还需要选购AI建站、SSL证书、安全防护包、RDS数据库等云产品的用户提供了额外的组合购买套餐,包括建站礼包、加36元防护主机安全、加99元解锁弹性数据库、加99元享高效存储保障等套餐,帮助用户一键选购。本文为大家介绍活动的相关规则及组合套餐配置与价格,以供参考。
816 2
|
5月前
|
JavaScript 前端开发 Java
基于Springboot的图书馆在线占座系统
针对高校图书馆座位资源紧张、管理低效问题,本文设计并实现基于SpringBoot的在线占座系统。系统采用B/S架构,结合MySQL、Vue等技术,实现座位查询、预约、签到等功能,提升资源利用率与管理效率,为学生提供公平便捷的使用体验。
|
5月前
|
人工智能 运维 自然语言处理
别让 LLM 变成“甩锅发动机”——从安全、审计、隐私聊聊运维智能助手怎么落地
别让 LLM 变成“甩锅发动机”——从安全、审计、隐私聊聊运维智能助手怎么落地
528 117
|
5月前
|
机器学习/深度学习 人工智能 数据可视化
构建AI智能体:六十六、智能的边界:通过偏差-方差理论理解大模型的能力与局限
本文通过机器学习中的偏差-方差权衡理论,深入探讨了模型性能的优化方法。文章首先用学生类比解释了高偏差(死记硬背)、高方差(思维跳跃)和平衡状态(真正理解)三种学习模式,对应机器学习中的欠拟合、过拟合和理想状态。通过数学公式E[(y-ŷ)²]=Bias²+Variance+Noise,系统分析了误差来源。使用多项式回归案例展示了不同复杂度模型的表现:线性模型(高偏差)、15次多项式(高方差)、4次多项式(平衡)和正则化模型。最终指出,最佳模型应在理解本质(低偏差)和稳定发挥(适度方差)间取得平衡。。。
364 110
|
5月前
|
缓存 视频直播
基于flutter3.38构建高性能直播+短视频+聊天app
flutter3.38.2+dart3.10+getx+media_kit跨平台实战搭建短视频+直播+聊天app系统。
265 4
基于flutter3.38构建高性能直播+短视频+聊天app
@Documented注解
该注解可用于生成Javadoc文档,结合@Target、@Retention等元注解,是实现自定义注解的基础。掌握其用法可提升代码可读性与开发效率。详情可参考“自定义注解”教程。
|
5月前
|
Java 测试技术 Apache
安装Jmeter
JMeter依赖JDK,需先安装并配置JDK环境变量。前往Apache JMeter官网(http://jmeter.apache.org/download_jmeter.cgi)下载最新版本,解压后即可使用,适用于性能测试与负载模拟。

热门文章

最新文章