浅谈ArrayList动态扩容

浅谈ArrayList动态扩容环境:eclipse,jdk1.8简介ArrayList实现了List接口,继承了AbstractList,底层是数组实现的,一般我们把它认为是可以自增扩容的数组。它是非线程安全的,一般多用于单线程环境下(与Vector最大的区别就是,Vector是线程安全的,所以ArrayList性能相对Vector会好些),它实现了Serializable接口,因此它支持序列化,能够通过序列化传输

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

环境:eclipse,jdk1.8
简介
ArrayList实现了List接口,继承了AbstractList,底层是数组实现的,一般我们把它认为是可以自增扩容的数组。它是非线程安全的,一般多用于单线程环境下(与Vector最大的区别就是,Vector是线程安全的,所以ArrayList 性能相对Vector 会好些),它实现了Serializable接口,因此它支持序列化,能够通过序列化传输(实际上java类库中的大部分类都是实现了这个接口的),实现了RandomAccess接口,支持快速随机访问(只是个标注接口,并没有实际的方法),这里主要表现为可以通过下标直接访问(底层是数组实现的,所以直接用数组下标来索引),实现了Cloneable接口,能被克隆。
ArrayList:
浅谈ArrayList动态扩容
浅谈ArrayList动态扩容
RandomAccess:
浅谈ArrayList动态扩容
浅谈ArrayList动态扩容

初始化
ArrayList一共提供了三个初始化的方法:
public ArrayList()
public ArrayList(Collection<? extends E> c)
public ArrayList(int initialCapacity);

首先看看源码里
无参构造方法的实现:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
上面的注释表示他会默认提供容量为10的数组,但是实际并不是在这一步实现。可以看看这里的DEFAULTCAPACITY_EMPTY_ELEMENTDATA和elementData:
浅谈ArrayList动态扩容
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
浅谈ArrayList动态扩容
只是一个空数组。所以这一步实际上只是将elementData指向一个空数组而已。
再来看看
带参数的构造方法
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
这个方法是直接将一个集合作为ArrayList的元素,很容易看懂,不多做解释,此时elementData即为集合c转为的数组,size即为elementData的长度。这里size是ArrayList的一个int型私有变量,用于记录该list集合中当前元素的数量,注意不是容量。
再来看看带初始化容量的构造方法:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
从源码里可以看出:首先对传进来的初始化参数initialCapacity进行判断,如果该参数大于0,在elementData进行初始化,初始化为一个容量为initialCapacity的数组,如果传进来的参数initialCapacity等于0,则将elementData指向了EMPTY_ELEMENTDATA,从这个名字也可以猜出,是个空数组:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
add方法的实现
说了这么多,还没有说到无参构造函数默认是空数组,为什么注释说是容量为10的数组,也还没说到当容量不足时,是如何实现动态扩容的,下面就通过add方法来说明这些问题。(add方法是list接口中声明的通用方法)。ArrayList的add方法实现如下:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
size是当前集合拥有的元素个数(未算进准备新增的e元素),从源码看出,调用了ensureCapacityInternal来保证容量问题,传进去的参数是size+1,来保证新增元素后容量满足要求。
接下来进入
ensureCapacityInternal方法查看其实现:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
可以看到代码段:
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
通过这一步来判断,当前
elementData是否为空数组(即初始化容量为0或者调用了无参构造函数后的结果),如果是,则使用
Math.max(DEFAULT_CAPACITY, minCapacity)进行选择一个较大的,其中,DEFAULT_CAPACITY是ArrayList定义的静态常量10:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
可以看出,这里如果minCapacity小于10的话(如果elementData为空的话,size+1即minCapacity一般为1),返回的是10,所以如果没有指定大小的话,默认是初始化一个容量为10的数组。然后在调用
ensureExplicitCapacity方法:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
可以看到modCount++,这里可以暂时不管它,这个参数主要是用在集合的Fail-Fast机制(即快速失败机制)的判断中使用的。(以后有空再补充这方面的内容)
在这个方法里进行判断,新增元素后的大小minCapacity是否超过当前集合的容量elementData.length,如果超过,则调用
grow方法进行扩容。我们进入该方法进行查看:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
在这里可以很清楚的看到扩容容量的计算:int newCapacity = oldCapacity + (oldCapacity >> 1),其中oldCapacity是原来的容量大小,oldCapacity >> 1 为位运算的右移操作,右移一位相当于除以2,所以这句代码就等于int newCapacity = oldCapacity + oldCapacity / 2;即容量扩大为原来的1.5倍(注意我这里使用的是jdk1.8,没记错的话1.7也是一样的),获取newCapacity后再对newCapacity的大小进行判断,如果仍然小于minCapacity,则直接让newCapacity 等于minCapacity,而不再计算1.5倍的扩容。然后还要再进行一步判断,即判断当前新容量是否超过最大的容量 if (newCapacity – MAX_ARRAY_SIZE > 0),如果超过,则调用hugeCapacity方法,传进去的是minCapacity,即新增元素后需要的最小容量:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
如果minCapacity大于MAX_ARRAY_SIZE,则返回Integer的最大值。否则返回MAX_ARRAY_SIZE。
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
然后回到grow方法,调用Arrays.copyof方法,即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。
到这里,应该可以很清楚的知道ArrayList底层扩容的原理了。与Vector不同的是,Vector每次扩容容量是翻倍,即为原来的2倍,而ArrayList是1.5倍。看似1.5倍增长的很慢,那经常增加大量元素会不会导致经常扩容,数组重新分配导致效率低下呢?其实不然,每次增长为原来的1.5倍实际增长的量会越来越大的,可以看看网友统计的数据(参考:
http://blog.csdn.net/java2000_net/article/details/5215882):
1千需要分配 11次
1万一级需要分配17次
10万 需要分配23次
100万需要分配28次
当然,如果一开始知道数据量很大的话,可以在初始化时预先指定容量。
get方法
浅谈ArrayList动态扩容
浅谈ArrayList动态扩容
很明显是通过数组下标索引来指定返回的数组,这里不多做解释。
浅谈ArrayList动态扩容

验证
无参构造函数,add三个元素,
按照理解,此时默认容量应该为10:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
可以看出:elementData容量为10,size为3。

无参构造函数,增加12个元素:
测试代码:
           List<Integer> list = new ArrayList<>();
           for (int i = 0 ; i < 12; i ++) {
                list.add(i);
           }

           System.out.println("ok");

通过debug查看结果:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
看到elementData扩容为15(10+10/2 = 15),而集合元素size为12。

无参构造函数,增加原来的1.5倍扩容量的数据:
测试代码:
           List<Integer> list = new ArrayList<>();           List<Integer> newList = new ArrayList<>();           for (int i = 0 ; i < 5; i ++) { 初始5个                list.add(i);           }           for (int i = 5 ; i < 20; i ++) {                newList.add(i);            }           list.addAll(newList);  //一次性增加15个           System.out.println("ok");
浅谈ArrayList动态扩容
浅谈ArrayList动态扩容

正常情况下,新增5个后,容量为10,再次新增,会变为原来的1.5倍,即15,但是这里新增15个,明显超过,按照上面的理解,应该直接让新容量等于需要的最小容量20,从测试截图可以看到,结果正确。

带集合参数构造函数:
测试代码:
           List<Integer> newList = new ArrayList<>();           for (int i = 5 ; i < 20; i ++) {                newList.add(i);           }           List<Integer> list = new ArrayList<>(newList);           System.out.println("ok");

测试结果:
浅谈ArrayList动态扩容

浅谈ArrayList动态扩容
可以看到,结果elementData的容量即为集合参数的大小。
总结
总之,ArrayList默认容量是10,如果初始化时一开始指定了容量,或者通过集合作为元素,则容量为指定的大小或参数集合的大小。每次扩容为原来的1.5倍,如果新增后超过这个容量,则容量为新增后所需的最小容量。如果增加0.5倍后的新容量超过限制的容量,则用所需的最小容量与限制的容量进行判断,超过则指定为Integer的最大值,否则指定为限制容量大小。然后通过数组的复制将原数据复制到一个更大(新的容量大小)的数组。
附:
size和modCount的区别

可能看了源码有时候还分不清size和modCount的区别,那么这里就用例子来说明。
size是ArrayList的变量。modCount是ArrayList的父类AbstractList中的变量,默认值为0。
size记录了ArrayList中元素的数量,modCount记录的是关于元素的数目被修改的次数。modCount在ArrayList的普通操作里可能并没有看出多大用处,但是在涉及到fail-fast就主要是依靠它了。
直接用下面这段代码进行测试:
           List<Integer> list = new ArrayList<>();           list.add(1);           list.add(2);           list.add(3);           list.add(4);           list.remove(2);           list.add(5);           list.set(1, 100);           list.remove(4);           System.out.println(list.size());
当执行完 list.add(4)时,此时modCount和size都为4:
浅谈ArrayList动态扩容

当执行完list.remove(2)时,此时元素数量发生了修改,所以modCount++即5,而size记录集合中元素的个数,移除了一个后,size=size-1即3:
浅谈ArrayList动态扩容

当执行完list.add(5)时,此时元素数量再次发生了修改,所以modCount++即5,而size记录集合中元素的个数,增加了一个后,size=size-1即4:

浅谈ArrayList动态扩容

当执行完list.set(1, 100)时,元素的数量并没有发生改变,所以modCount和size都不变。

浅谈ArrayList动态扩容




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

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

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

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

(0)


相关推荐

  • dump文件 linux,Linux下快速分析DUMP文件「建议收藏」

    dump文件 linux,Linux下快速分析DUMP文件「建议收藏」dump文件传输到本地进行分析,常常需要大量的等待时间。使用IBM的eclipse的MAT工具可以直接在服务器上进行快速DUMP分析。运行环境要求linux操作系统JDK8以上下载MAT的linux版本Eclipse的MAT工具下载链接MAT支持各种操作系统,找到Linux版本下载下来#运行uname-m看一下linux是x86_64还是x86的帮助你选择下载那个版本。uname-…

  • Git ssh 配置及使用

    Git ssh 配置及使用前言:前几天在写博客手把手教你用Hexo+github搭建自己博客的时候,经常需要用到一些git操作,截了好多图,于是就想干脆整理成一系列的git教程,总结如下Git下载及配置环境变量Git命令行教程及实例教程Gitssh配置及使用gitssh配置多个账户Gitconfig使用说明Git配置别名——让命令变得更简单闲聊这篇教程是在电脑

  • Python 中return用法及意义「建议收藏」

    Python 中return用法及意义「建议收藏」return意义其实说白了,函数就是个你招来的工人。你给他一些材料,告诉他怎么用这些材料拼装,然后他负责把拼装好的成品交给你。材料就是函数的参数,成品是函数的输出,而怎么拼装就是你写的函数体代码了。比如这段代码defworker(a,b,c):x=a+by=x*c这个工人worker在你的指导下,用abc三个材料,装配出了x和y两个成品。但是程…

    2022年10月28日
  • 银行软件测试面试常见问题答案(平安银行软件测试面试)

    测试技术面试题1、什么是兼容性测试?兼容性测试侧重哪些方面?参考答案:兼容测试主要是检查软件在不同的硬件平台、软件平台上是否可以正常的运行,即是通常说的软件的可移植性。兼容的类型,如果细分的话,有平台的兼容,网络兼容,数据库兼容,以及数据格式的兼容。兼容测试的重点是,对兼容环境的分析。通常,是在运行软件的环境不是很确定的情况下,才需要做兼容。根据软件运行的需要,或者根据需求文档

  • MATLAB 2018b 安装与简介

    MATLAB 2018b 安装与简介matlab2018b安装教程该版本是mathworks官方开发的新版本的商业数学软件,可以帮助用户不仅仅将自己的创意停留在桌面,还可以对大型数据集运行分析,并扩展到群集和云。另外matlab代码可以与其他语言集成,使您能够在Web、企业和生产系统中部署算法和应用程序。与matlab2018a相比,matlab2018b拥有更多数据分析、机器学习和深度学习选项,并且速度比以往更快。其亮点…

  • rac 10g 10.2.0.1升级到10.2.0.5具体解释[通俗易懂]

    rac 10g 10.2.0.1升级到10.2.0.5具体解释

发表回复

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

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