【源码解析】扒开ArrayList的外衣

积千里跬步,汇万里江河;每天进步一点点,终有一天将成大佬。

本文内容

当然ArrayList里的方法不止这些,本文主要讲一些常用的方法

方法变量

Arraylist里的方法变量主要有以下几个

1. 构造方法

1.1 有参构造

1.1.1 传入数组的大小

1.1.1.1代码实现
List<String> list=new ArrayList<>(5);
1.1.1.2源码解析

1.1.2 传入一个list对象

其实这个就相当于把传入的list对象里的数据复制到新的ArrayList对象

1.1.2.1 代码实现
List<String> list=new ArrayList<>(Arrays.asList("z","m","h"));
这里用来Arrays工具类里的asList方法,它的源码里是直接返回一个List,有兴趣的可以去看看,这里就不介绍了
1.1.2.2 源码解析

1.2 无参构造

这个比较简单,直接赋值一个空数组

1.2.1代码实现

List<String> list=new ArrayList<>();

1.2.2源码解析

2. add方法

add一般常用的有两个方法,一个就是add(E e)在尾部添加数据,一个就是add(int index,E element)在指定位置插入元素

2.1 add(E e)

这个是Arrayist的主要方法,平时用的也是最多的方法之一,所以源码比较复杂,比较长

2.1.1 代码实现

List<String> list=new ArrayList<>();
list.add("灰灰HK");

2.1.2 源码解析

  • ensureCapacityInternal(int minCapacity)确保数组容量充足

  • calculateCapacity(Object[] elementData, int minCapacity)

  • 再回到ensureExplicitCapacity(int minCapacity)这个方法,这个方法先修改次数加1,然后判断size+1是不是比当前的数组容量大,如果比当前的数组容量大,则进行扩容操作,扩大容量为原数组的1.5倍
比如第二次调用add方法,此时size+1=2, elementData.length=10,为什么等于10呢?因为第一次默认把数组容量从0扩大到了10,这时size+1elementData.length小,就不会进行扩容操作

  • grow(int minCapacity)扩容
这里调用Arrays.copyOf()方法进行复制操作,当进一步深入这个方法时,发现是由System.arraycopy()这个方法实现复制功能的,这个方法由native关键字修饰,表示不是由Java语言实现的,一般是c/cpp实现

2.1.3 小结

到这里,add的方法流程就走完了,其核心步骤:

  • 每次添加元素时判断数组容量是否充足
  • 第一次添加元素,把数组容量扩容到10
  • 扩容时,除第一次,以后的每次扩容为原大小的1.5倍
  • 扩容后调用System.arraycopy()方法把原数组的元素复制到扩容后的新数组

2.2 add(int index, E element)

该方法为在指定位置插入元素,该位置及后面所有元素后移

2.2.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.add(0,"灰灰");

2.2.2 源码解析

可以看到,这边又用到了System.arraycopy()这个方法
  • rangeCheckForAdd(int index)判断是否越界
这里他是和size对比,而不是和数组的length对比,我个人认为这样第一节省了空间,第二方便后面移动的操作

  • System.arraycopy()拷贝数组
public static native void arraycopy(Object src,  int  srcPos,
                                     Object dest, int destPos,
                                    int length)
  • src 原数组对象
  • srcPos 原数组起始位置
  • dest 目标数组
  • destPos 目标数组起始位置
  • length 复制多少个数据

2.2.3 小结

插入方法其主要步骤如下:

  • 检查插入的位置是否越界
  • 检查数组容量是否充足,不充足进行扩容相关操作
  • 调用System.arraycopy()进行index及后面的元素后移

3. get方法

3.1 get(int index)

3.1.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.get(0);

3.1.2 源码解析

  • rangeCheck(int index)判断是否越界
get个add方法判断越界的方法是不一样的,这边是index>=size,多了个等于,为什么要多个等于呢?因为数组是从0开始的,而size相当于是开始的从1开始的
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
  • elementData(int index)直接返回对应下标的数组元素
E elementData(int index) {
    return (E) elementData[index];
}

3.1.3 小结

get方法比较简单,主要步骤为:

  • 检查是否越界
  • 返回对应元素

4. set方法

4.1 set(int index, E element)

4.1.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.set(0,"灰灰");

4.1.2 源码解析

5. remove方法

5.1 remove(int index)

5.1.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.remove(0);

5.1.2 源码解析

当删除的元素为最后一个元素时,numMoved就小于0了,就不会进行移动元素的操作

5.2 remove(Object o)

这个方法在实际中用的比较少,因为AraryList是可以保存重复的元素,所以删除是删除最早添加的元素

5.2.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.remove("hk");

5.2.2 源码解析

  • fastRemove(int index)删除元素
这个方法和remove(int index)内部的操作类似,不过这边不保存被删除的元素
private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

6. clear方法

6.1 clear()

6.1.1 代码实现

List<String> list=new ArrayList<>();
list.add("hk");
list.clear();

6.1.2 源码分析

总结

ArrayList底层扩容或者移动数组元素时都调用了System.arraycopy()来进行相关操作,平时进行我们进行数组复制或移动的时候也可以调用这个方法了,这个性能比循环复制性能高多了,特别是在大量数据的时候。

文章好几次出现了modCount++这个操作,这个modCount主要用户内部类的迭代器

Image placeholder
Lars
未设置
  74人点赞

没有讨论,发表一下自己的看法吧

推荐文章
Stylus系列——webpack-spritesmith配合stylus使用示例

一、前言基于Webpack的CSSSprites实现方案,若是直接在html中调用雪碧图图标已经很方便,但是实际开发过程可能遇到需要在伪元素中使用雪碧图,或者需要hover切换另一个图标,这种情况下就

HDFS 源码解读:HadoopRPC 实现细节的探究

桔妹导读:HDSF作为分布式文件系统,常常涉及DataNode、NameNode、Client之间的配合、相互调用才能完成完整的流程。为了降低节点之间的耦合性,HDFS将节点间的调用抽象成不同的接口,

vue源码解读(四)Vue中的异步更新策略

欢迎star我的github仓库,共同学习~目前vue源码学习系列已经更新了6篇啦~https://github.com/yisha0307/...快速跳转: Vue的双向绑定原理(已完成) 说说vu

程序员:我终于知道post和get的区别

IT界知名的程序员曾说:对于那些月薪三万以下,自称IT工程师的码农们,其实我们从来没有把他们归为我们IT工程师的队伍。他们虽然总是以IT工程师自居,但只是他们一厢情愿罢了。此话一出,不知激起了多少(码

JVM CPU Profiler技术原理及源码深度解析

本文介绍了JVM平台上CPUProfiler的实现原理,希望能帮助读者在使用类似工具的同时也能清楚其内部的技术实现。引言研发人员在遇到线上报警或需要优化系统性能时,常常需要分析程序运行行为和性能瓶颈。

学习IT的实用工具和网站推荐

对于一些学习IT的初学者来说,掌握一些实用的软件工具和学习网站是十分有必要的。本文要为大家推荐一些学习IT的相关的资源,像是鸠摩搜书和脚本之家等电子书搜索网站,还有冰点文库和文件搜索工具等实用工具以及

美团BERT的探索和实践

他山之石,可以攻玉。美团点评NLP团队一直紧跟业界前沿技术,开展了基于美团点评业务数据的预训练研究工作,训练了更适配美团点评业务场景的MT-BERT模型,通过微调将MT-BERT落地到多个业务场景中,

Fortinet的云安全观:上云≠安全 云安全市场或迎“又一春”!

近年来网络攻击事件频繁发生,企业对于网络安全的关注度已经到达前所未有的高度,如何保证业务的正常运转是每个企业最为关注的问题之一。而随着越来越多的企业将业务扩展到云端,云上安全问题也成为企业必谈的话题!

从reddit的一亿美元商业逆袭,看移动与PC产品的时代天堑

提起有“互联网头版”之称的reddit,你会联想到什么?想到这一网站上层出不穷的搞笑梗或meme图?还是程序员们经常制造出的各种有趣小发明?说起来在这个体量巨大、包容性极强、时刻制造着互联网新热点的论

从ResNet的诞生讲起:美公司在北京的AI研究所出了成果,中美究竟谁受益更多?

大数据文摘出品来源:macropolo编译:狗小白、Aileen中美之间摩擦不断,如今,AI竞争也成为了其中重要的组成部分。让我们假设这样一个场景:美国AI公司设立在中国的实验室取得了一些突破,谁从中

为什么说IPA智能流程自动化是企业IT的下一波浪潮?

提到IPA,可能很多人会立刻想到RPA。RPA,即机器人流程自动化,是企业IT过去两年最热门的技术之一。仅在2018年,就有三家公司拿到了总额超过十亿美金的风投,包括AnywhereAutomatio

30分钟让你掌握Git的黑魔法

本文转载自云效公众号在GitRevNews#48期的LightReading中有一篇文章写的不错,不仅干货满满而且还附带了操作视频。其中的内容不仅覆盖了很多git使用上的基础知识,也从使用角度上解答了

tomcat的重启

点击下方截图可插入当前视频播放画面,了解更多Mackdown语法可以点击上方?图标jsp运行不需要重启tomcat而servlet需要

如何改变react的行内样式

如何改变react的行内样式在react中,可以这样来设置行内样式:render(){ conststyles={color:"red",fontSize:"16px"}; return( ); }

vue和react的区别是什么?

vue和react的区别1、监听数据变化的实现原理不同Vue通过getter/setter以及一些函数的劫持,能精确知道数据变化。React默认是通过比较引用的方式(diff)进行的,如果不优化可能导

vue和react的主要区别是什么?

Vue是一套构建用户界面的渐进式框架。与其他重量级框架不同的是,Vue采用自底向上增量开发的设计,其核心库只关注视图层,并且非常容易学习,也易与其它库或已有项目整合。另一方面,Vue完全有能力驱动采用

基于ApiBoot的前后分离演示脚手架诞生了~

知识改变命运,撸码使我快乐,2020继续游走在开源界点赞再看,养成习惯给我来个Star吧,ApiBootAdmin源码仓库:https://gitee.com/minbox-projects/api-

vue基于vant的uploader上传图片

小白第一次使用有赞的vant组件库,这里记录一下个人在项目上的一些使用,方便以后查阅. {{item.goods_title}} {{item.sku_param_value}} 愉

JavaScript的DOM应用笔记

获取a标签:document.links获取img标签:document.images获取form标签:document.forms

JavaScript的DOM应用笔记

通过id获取:document.getElementById()写入HTML:innerHTML()内部outerHTML()外部

JavaScript的DOM应用笔记

操作元素属性:element.attribute=newvalueelement.setAttribute(attribute,value)element.getAttribute(attribute

JavaScript的运算符和流程控制笔记

"usestrict""usestrict""usestrict"严格模式

JavaScript的DOM应用笔记

通过id或标签名获取元素对象:getElementById(‘id’)getElementsByTagName(‘标签名’)getElementsByName(‘name’)getElementByC

JavaScript的DOM应用笔记

这里的修改className属性,因为长度会动态改变,所以需要将修改的下标设为0,