程序员经验分享-hwhale

【源码】走一遍源码弄清ArrayList容器的扩容机制

2023-11-01

【源码】走一遍源码弄清ArrayList容器的扩容机制

首先我们来看看ArraysList容器在整个Java集合框架中所处的位置

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jI1Xup14-1633074971386)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001132014326.png)]

由此可见ArrayList是Java集合框架中，两大派系中Collection接口的子接口List的实现类

我们从源码入手可以看到ArrayList底层数据结构实际上是一个**Object类型的数组**，由于Object是所有类的父类，所以ArrayList集合可以存放任意类型的元素，并且存放的元素是有序的、可重复的、可随机访问的。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-orhkLlTo-1633074971388)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001132428227.png)]

接下来我们就以add()方法为突破口，来解读一下ArrayList的源码，以及它的扩容机制

我们要想向ArrayList结合添加元素，首先得创建出一个ArrayList对象出来，ArrayList的构造方法有3种：

  • 无参构造器

    使用无参构造器创建一个对象时，默认创建的是一个空集合，它的初始容量是10。什么鬼？空集合怎么还容量为10，这不自相矛盾吗？我这里说的空集合指的是，这个集合刚创建出来，在还没有调用add()方法向集合中添加第一个元素之前，这个集合是空的。而所说的初始容量为10，指的是当你调用add()方法向集合中添加第一个元素时，这个集合的容量大小会被扩容到10，这个10就是指的初始容量。可以我们为向容器中添加了一个元素，为什么要扩容到10呢？这不浪费内存空间吗？实际上这是考虑的扩容的问题，你创建这个容器肯定不止存放一个元素，我们之所以冗余了一些空间，就是为了防止不断频繁扩容导致性能低下的问题。
    在这里插入图片描述

  • 带初始容量参数的构造函数

    我们在创建一个容器时，在构造方法中可以传入初始容量大小，如果传入的初始容量大小为0的话，就会创建一个空的容器。

    注意！这里的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和无参构造方法中的EMPTY_ELEMENTDATA虽然都是空集合，但是这两个空集合是有区别的，DEFAULTCAPACITY_EMPTY_ELEMENTDATA在添加第一个元素时，明确指定了扩容到默认的初始容量大小。而EMPTY_ELEMENTDATA由于指定的初始容量为0，所以在扩容的时候，会调用grow()方法走扩容的流程。
    在这里插入图片描述

  • 传入一个集合参数的构造器

    在创建ArrayList容器时，可以给构造器传入一个集合参数，利用Arrays.copy()方法复制这些集合中元素，原来创建一个新的集合
    在这里插入图片描述

现在我们利用构造器创建出来了一个ArrayList容器，接下来就调用add()方法开始向容器中添加元素。

在向容器中添加元素时，首先会调用ensureCapacityInternal()方法确保容器容量足够，得到最小扩容量

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jsPei1fJ-1633074971422)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001144621620.png)]

如果是使用默认的无参构造器创建的容器，并且是添加第一个元素，minCapacity 为 10，也就是当前添加元素的操作，需要容器的容量大小为minCapacity

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NzZWNQAn-1633074971437)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001145214600.png)]

确定了最小容器容量之后，就调用ensureExplicitCapacity()方法根据得到的最小容量来判断到底需不需要进行扩容

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Huikp9Zf-1633074971441)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001145526590.png)]

只有当需要的最小容量大于当前容器的最大容量时，最大的容量也就是数组的长度，就会调用grow()方法进行扩容

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-uiv3B3N6-1633074971445)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001145730014.png)]

从grow()方法可以看出ArrayList容器的扩容机制是变为原来容量的1.5倍

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ebLMi0dt-1633074971453)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001150741500.png)]

为了防止在添加第一个元素时，由于空集合的容量为0，扩大1.5倍之后计算出的新的容量还是0,这样情况，源码中还通过比较扩容后的新的容量与需要的最小容量，来判断是否是第一次添加元素，如果是就直接将扩容后的新的容量改成需要的最小容量。这样就避免了第一次扩容扩不起来的问题。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VMpvetZV-1633074971458)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001151222536.png)]

如果说扩容后的容量超过了ArrayList的最大容量，也就是扩容1.5倍后的容量大于了Integer.MAX_VALUE - 8。此时就需要判断需要的最小容量是否超过了ArrayList的最大容量。
在这里插入图片描述

如果需要的最小容量超过了ArrayList最大容量，此时我们就不能按照1.5倍扩容了，直接返回Integer.Max_VALUE，如果说没有超过ArrayList最大容量，就返回最大容量

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CkZ0Wvab-1633074971469)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001151857218.png)]

扩容完之后，就调用Arrays.copyOf()方法，开始将原来容器中的所有元素复制到扩容后的容量中

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yzCyC8pi-1633074971473)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001152303747.png)]

Arrays.copyOf()方法底层调用的实际上是System.arraycopy()本地方法，将原数组中的数据进行拷贝,并返回新的数组
在这里插入图片描述

至此，ArrayList容器的扩容流程就完成了！

我们注意到ArrayList的增删改查相关的方法都没有使用Synchronized同步关键字，或者说没有使用其他同步机制，因此ArrayList容器是线程不安全的！

与ArrayList容器对标的是Vector这个容器

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-KTloW2OQ-1633074971476)(C:\Users\Jian\AppData\Roaming\Typora\typora-user-images\image-20211001152904024.png)]

Vector的底层实现和ArrayList的底层实现类似，也是使用Object类型的数组存放元素。而且默认初始容量也为10
在这里插入图片描述

与ArrayList不同的地方在于Vector的扩容的方法使用了Synchronized同步关键字，因此是**线程安全的！**而且Vector扩容机制是扩大2倍！而ArrayList是扩大1.5倍！
在这里插入图片描述

一般开发中都是使用ArrayList容器，Vector容器基本上不再使用，虽然Vector使用Synchronized保证了线程安全，但是效率十分低下，如果考虑到线程安全问题，可以使用JUC并发集合！

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Java

JUC

面试汇总

ArrayList

【源码】走一遍源码弄清ArrayList容器的扩容机制 的相关文章

随机推荐

  • JavaScript(js)

    js 基础语法 1 与html结合使用 内部JS 定义

  • OpenCV学习第十三篇：提取水平和垂直线（去除干扰线）

    1 结构元素 可以是任意形状的结构元素 矩形 圆 直线 磁盘形状 砖石形状等 2 提取步骤 输入图像彩色图像imread 转换为灰度图像cvtColor 转换为二值图像adaptiveThreshold 定义结构元素 开操作 腐蚀 膨胀 提

  • mysql-8.0.17-winx64 安装包 与 安装教程

    初步安装教程 https www cnblogs com cyl048 p 11305642 html 安装时可能需要使用的命令 进入到mysql安装包的bin目录下 cd d D Program Files x86 mysql 8 0 1

  • redis-benchmark

    redis benchmark Redis自带一个叫redis benchmark的工具来模拟N个客户端同时发出M个请求 影响 Redis 性能的因素 有几个因素直接决定 Redis 的性能 它们能够改变基准测试的结果 所以我们必须注意到它

  • TensorFlow之模型保存与加载

    模型在训练过程中或者在训练之后 模型的执行过程能被保存 也就是 模型能从暂停中恢复以免训练的时间过长 因此 被保存的模型可以被共享 其他人可以重新构建相同的模型 被保存的模型以如下的两种方式进行共享 创建模型的代码 被训练模型的权重或者参数

  • STL——Vector模板类常见函数

    由于经常在做题中遇到 所以记录下 include

  • ubantu下vim的配置

    配置vim的作用 是为了更加方便我们在Linux系统下编程 在没有配置过的vim里 我们只能做最简易的操作 vim编辑器也不能像主机其他c编译器那样给我们自动补充和提示等帮助 而我们配置完vim后 通过我们的配置指令 vim环境就会跟普通的

  • PyTorch实现Softmax回归

    1 导入模块 import torch from torch utils data import DataLoader import torch nn as nn import torchvision datasets as Dataset

  • 3d效果技术java,java3D技术展示

    java3D技术依靠Java自身所带的API函数 来构建3D模型 不同于C 中的OpenGL函数 他显得跟简单 依靠观察者视觉的不同改变观察角度 主要是固定某些属性 通过mul函数合并属性 universe getViewingPlatfo

  • 在谈天津2023年高考压轴题：斯特林公式数列极限

    证明单调性 转化为数列极限问题 利用斯特林公式求极限

  • python _简易版本web_server

    学习目标 做个简易版的web server玩玩 学习内容 coding utf 8 import sys os subprocess from http server import BaseHTTPRequestHandler HTTPSe

  • 将两个列表转换成字典

    想象一下您有 keys name age food values Monty 42 spam 产生以下字典的最简单方法是什么 a dict name Monty age 42 food spam 1楼 您还可以在 2 7的Python中使用

  • Javassist操作方法总结

    参考手册 1 读取和输出字节码 ClassPool pool ClassPool getDefault 会从classpath中查询该类 CtClass cc pool get test Rectangle 设置 Rectangle的父类

  • 动态添加列 表格_只用过Excel表格？其实PowerBI中也有更强大的表格

    在PowerBI的可视化对象中 还有两个 表格 对象 表格的作用不仅可以在报表提供明细数据 还经常用来测试度量值的返回结果 因为它们使用起来十分简单 就是把字段拖进去就可以显示出来数据 看起来和Excel表格也没有什么不同 刚开始接触Pow

  • 从入门到放弃系列--如何成为全栈工程师01

    写个序言 计算机的书 有一个神秘的系列 不管写什么的 编程类的 比如 C语言 JAVA PHP 操作系统类的 比如windows98 2000 XP ME VISTA 7 8 10 LINUX 软件类的 比如word wps excel p

  • Cesium Terrain Builder 非压缩瓦片

    Cesium Terrain Builder 输出瓦片默认是zib压缩后的 在业务中如果传输不是问题 反而增加浏览器的解压处理 希望能支持输出非压缩瓦片 针对此需求 修改代码并重新编译 一 代码分析 1 输出数据对象 文件格式 主要为hei

  • 服务器上的文件怎么共享给学生机,云服务器对应学生机

    云服务器对应学生机 内容精选 换一换 当您创建的弹性云服务器规格无法满足业务需要时 可以变更云服务器规格 升级vCPU 内存 具体接口的使用 请参见本节内容 变更规格时 部分规格的之间不能互相变更 您可以参见查询云服务器规格变更支持列表查询

  • 重磅：饶毅正式举报裴钢院士！

    点击上方 CVer 选择加 星标 置顶 重磅干货 第一时间送达 来源 饶议科学 科技部 科奖中心 编辑 考博圈 学长 经过将近一年的严肃调查处理 1月21日 科研诚信建设联席会议联合工作机制发布 有关论文涉嫌造假调查处理情况的通报 以下简称

  • 【zedboard找不到COM串口bug】驱动下载地址

    今天在使用zedboard过程中出现了sdk终端没有COM串口的问题 解决方法见 zedboard串口bug最终解决办法 zynq开发 在SDK 终端Teminal找不到COM3 COM5等接口 无法连接uart串口 ZYNQ驱动问题 解决

  • 【源码】走一遍源码弄清ArrayList容器的扩容机制

    源码 走一遍源码弄清ArrayList容器的扩容机制 首先我们来看看ArraysList容器在整个Java集合框架中所处的位置 由此可见ArrayList是Java集合框架中 两大派系中Collection接口的子接口List的实现类 我们

热门标签