Java ArrayList使用总结
提起ArrayList,相信很多小伙伴都用过,而且还不少用。但在几年之前,我在一场面试中,面试官要求说出ArrayList的扩容机制。很显然,那个时候的我并没有关注这些,从而错过了一次机会。不过好在我还算比较喜欢搞事情的,所以今天这篇文章也算是填坑吧。
看完这边文章你将了解到:
- ArrayList底层实现
- ArrayList为什么允许null值
- ArrayList为什么可重复
- ArrayList查询效率和插入效率对比
类图
下图是ArrayList的类图结构
ArrayList继承于 AbstractList,实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
这里逐个分析一下这里接口的意义:
- RandomAccess是一个标志接口,表明实现这个这个接口的 List集合是支持快速随机访问的。有兴趣可以看看Collections类中哪个方法用到了这个标志性接口。
- 实现 Cloneable接口并覆盖了方法clone(),能被克隆。
- 实现了java.io.Serializable 接口,这意味着ArrayList支持序列化,能通过序列化去传输(请注意,ArrayList的序列化是有点小特殊的,后面会讲解)。
源码解析
成员变量
在正式进入源码分析之前,我们有必要先看看它的成员变量都有哪些,这里列举比较重要的成员变量:
private int size; // 实际元素个数 transient Object[] elementData; //真正保存元素的数组 private static final int DEFAULT_CAPACITY = 10;//默认的初始容量大小
构造方法
我们有三种初始化办法:无参数直接初始化、指定大小初始化、指定初始数据初始化,源码如下:
//1、无参数直接初始化,数组大小为空 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } //2、指定初始数据初始化 public ArrayList(Collection<? extends E> c){ //elementData是保存数组的容器,默认为null elementData=c.toArray(); //如果给定的集合(c)数据有值 if((size=elementData.length)!=0){ //c.toArray might(incorrectly)not return Object[](see 6260652) //如果集合元素类型不是Object类型,我们会转成Object if(elementData.getClass()!=Object[].class){ elementData=Arrays.copyOf(elementData,size,Object].class); } }else{ //给定集合(c)无值,则默认空数组 this.elementData=EMPTY_ELEMENTDATA } } //3、指定初始容量 public ArrayList(int initialCapacity) { //指定的初始容量大于0,将elementData初始化为指定大小的数组 if (initialCapacity > 0) { this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { //否则初始化成一个空数组 this.elementData = EMPTY_ELEMENTDATA; } }
除过源码中注释外,补充几点:
- ArrayList无参构造器初始化时,默认大小是空数组,并不是大家常说的10,10是在第一次add的时候扩容的数组值。
- 使用方式二进行创建对象时,如果入参容器保存的对象不是Object,则转换为Object。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA又是什么鬼?它其实是定义在成员变量的两个空数组,
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; private static final Object[] EMPTY_ELEMENTDATA = {};
很明显问题来了,既然都是空数组,为什么要声明两个?一个不行吗?读者请先思考一下,带着疑问往下看。
新增和扩容实现
通过构造方法可以很清楚的看到,ArrayList的确是基于数组的,但动态又从何说起?
新增时就是给数组中添加元素,主要分为两步走:
- 判断是否需要扩容,如果需要扩容执行扩容操作;
- 直接赋值。
对应源码如下:
public boolean add(E e) { //确保数组大小是否足够,不够执行扩容,size为当前数组元素个数,判断size+1是因为后面还要size++ ensureCapacityInternal(size + 1); //1 elementData[size++] = e;//2 return true; }
我们先来看一下扩容部分的源码:
private void ensureCapacityInternal(int minCapacity) { //先调用calculateCapacity计算容量 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } private static int calculateCapacity(Object[] elementData, int minCapacity) { //如果当前数组还是个空数组,也就是他用过无参构造去初始化的 //那么直接返回DEFAULT_CAPACITY,即10 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 如果当前容量已经大于当前数组的长度了,说明需要去扩容了 if (minCapacity - elementData.length > 0) //扩容 grow(minCapacity); } private void grow(int minCapacity){ int oldCapacity = elementData.length; //oldCapacity>>1是把oldCapacity除以2的意思 int newCapacity=oldCapacity+(oldCapacity>>1); //如果扩容后的值<我们的期望值,扩容后的值就等于我们的期望值 if(newCapacity-minCapacity<0) newCapacity = minCapacity; //如果扩容后的值>jvm所能分配的数组的最大值,那么就用Integer的最大值 if(newCapacity-MAX_ARRAY_SIZE>0) elementData=Arrays.copyOf(elementData,newCapacity); }
注释相对来说已经比较详细了,这里需要注意以下几点:
- 上面有个问题是为什么需要声明两个空数组。我们在看到上面源码的时候有一个方法为calculateCapacity,这个方法内部逻辑只有在通过无参构造初始化ArrayList的时候才会改变将要返回的minCapacity。而返回的这个值将会决定下面的数组是否需要扩容。如果我们通过指定大小的方式初始化ArrayList并指定大小为0,这说明我们需要的就是一个空的ArrayList,不需要去扩容,你细品;
- 新增时,没有对值进行校验,所以新增值可以为null,且没有做重复值判断,所以元素可以重复;
- ArrayList中的数组的最大值是Integer.MAX_VALUE,超过这个值,JVM就不会给数组分配内存空间了;
- 扩容是原来容量大小+容量大小的一半,简单说就是扩容后的大小是原来容量的1.5倍。
扩容完成之后,就是简单的赋值了,赋值时并没有加锁,所以是线程不安全的。
扩容的本质
在grow方法的最后,扩容是通过Arrays.copyOf(elementData,newCapacity);这行代码实现的。这个方法实际上调用的方法是我们经常使用的System.arraycopy:
/** *@param src 被拷贝的数组 *@param srcPos 从数组那里开始 *@param dest 目标数组 *@param destPos从目标数组那个索引位置开始拷贝 *@param length 拷贝的长度 *此方法是没有返回值的,通过dest的引用进行传值 */ public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);
这个方法是一个native方法,虽然不能看到方法内部的具体实现,但通过参数也可以管中窥豹。这个方法会移动元素。所以说数组如果要扩容,需要重新分配一块更大的空间,再把数据全部复制过去,时间复杂度 O(N);而且你如果想在数组中间进行插入和删除,每次必须搬移后面的所有数据以保持连续,时间复杂度 O(N)。由于数组又是一块连续的内存空间,能够根据索引快速访问元素。
上面也就解释了一开始那个问题:ArrayList为什么插入慢,查询快。
删除
ArrayList有多种删除方法,这里以根据值删除的方式进行说明(其他原理类似):
public boolean remove(Object o) { //如果要删除的值是null,删除第一个是null的值 if(o==null){ for(int index=0;index<size;index++) if(elementData[index]==null){ fastRemove(index) return true; } }else{ //如果要删除的值不为null,找到第一个和要删除的值相等的删除 for(int index=0;index<size;index++) //这里是根据 equals来判断值相等的,相等后再根据索引位置进行删除 //所以根据对象删除时,一般来说,如果你确定要删除的是某一类的业务对象,则需要重写equals if(o.equals(elementData[index]){ fastRemove(index) return true; } } return false }
核心其实是fastRemove方法:
private void fastRemove(int index){ //记录数组的结构要发生变动了 nodCount++; //numMoved表示删除index位置的元素后,需要从index后移动多少个元素到前面去 //减1的原因,是因为size从1开始算起,index从0开始算起 int numMoved=size-index-1; if(numMoved>0) //从index+1位置开始被拷贝,拷贝的起始位置是index,长度是numMoved System.arraycopy(elementData, index+1, elementData, index, numMoved); //数组最后一个位置赋值null,帮助GC(没有引用则自动回收了) elementData[--size] = null; }
从源码中,我们可以看出,某一个元素被删除后,为了维护数组结构,我们都会把数组后面的元素往前移动,同时释放最后一个引用,便于回收。
总结
本文主要从ArrayList的源码入手,分别从初始化、新增、扩容、删除四个方面展开学习。我们发现ArrayList内部其实就是围绕了一个数组,在数组容量不足时将数组扩容至更大,所以也就自然被称作基于动态数组。
微信搜索Java成神之路或扫描下方二维码,发现更多Java有趣知识,让我们一起成长!
以上就是Java ArrayList使用总结的详细内容,更多关于Java ArrayList使用的资料请关注猪先飞其它相关文章!
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06- 下面小编就为大家带来一篇java中String类型变量的赋值问题介绍。小编觉得挺不错的。现在分享给大家,给大家一个参考。...2016-03-28
- 这篇文章主要介绍了Java线程池中的各个参数如何合理设置操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-06-19
- 在Java中,我们可以利用多线程来最大化地压榨CPU多核计算的能力,下面这篇文章主要给大家介绍了关于java中多线程与线程池基本使用的相关资料,需要的朋友可以参考下...2021-09-13