ArrayList源码解析
大家好,我是连边。
前言
开始写Java集合
图解源码系列的文章,本篇是开篇,主角是ArrayList
。
这个系列按照这个步骤来讲解:
图解分析原理,实战面试题检测,阅读JDK源码进一步巩固理解。
阅读本系列文章,不需要数据结构的基础,带上认真的态度完全可以吃透。
Java集合的整体认识
java集合框架提供了一套性能优良,使用方便的接口和类,它们位于java.util
包中。
今天这篇文章的主角是ArrayList
,从上图可以看出,ArrayList
实现List接口,和它同根同级的还有LinkedList
,ArrayList
同时还实现了RandomAccess, Cloneable, java.io.Serializable,我们利用类图来直观说明。
图解基本原理
数组与动态数组(ArrayList)
数组的索引从0开始;
Java语言中提供的数组是用来储存固定大小的同类型元素;
Java中可以使用两种方式来声明数组:
1 |
|
Java中数组的创建方式同样有两种:
1 |
|
ArrayList是一种以数组实现的List
,与数组相比,具有动态扩展的能力,因此也可称之为动态数组
。
增删改查和扩容
添加元素
末尾添加元素
场景: 存在长度为6的数组,存在A、B、C三个值,把D值(索引为3)添加到数组末尾;
步骤: 直接进行压入操作就可以完成操作,然后再挪动size;
中间添加元素
场景: 存在长度为6的数组,存在A、B、C三个值,把D值(索引为2)添加到AB之间;
步骤: 首先需要把添加位置之后的元素往后挪,挪动完成之后,把指定的元素插入到挪出来的空位,然后挪动size;
删除元素
删除末尾元素
场景: 存在长度为6的数组,存在A、B、C三个值,把C值(索引为2)从数组中删除;
步骤: 直接进行删除,然后挪动size;
删除中间元素
场景: 存在长度为6的数组,存在A、B、C三个值,把B值(索引为1)从数组中删除;
步骤: 找到指定索引的值,进行删除,把删除元素后边的元素依次往前挪,把最后一个元素设置为null,让他释放垃圾,然后移动size;
修改元素
场景: 存在长度为6的数组,存在A、B、C三个值,把B值(索引为2)修改成D值;
步骤: 找到指定索引,把原来的值进行赋值,把新元素直接覆盖,返回oldValue;
查询元素
场景: 存在长度为6的数组,存在A、B、C三个值,把B值(索引为2);
步骤: 找到指定索引,返回;
动态扩容
数组ArrayList
是一种以数组实现的List
,与数组相比,增删改查元素都一样,也需要连续的内存空间,但是它具有动态扩展的能力,因此也可称之为动态数组
。
这里着重用动图表示动态数组的扩容机制,因为增删改查元素和数组是一样的,可以参照数组的动态图。
场景: 存在长度为4的数组,存在A、B、C、D四个值,现在需要在最后添加元素,原来的长度不够,触发扩容机制;
步骤: 按照原来数组长度的1.5倍创建一个新数组,即创建size=6的数组,把原来的old数组平移到新数组,size也进行同步平移,进行添加元素,然后修改数组的引用(由原来的old数组引用改成new数组引用);
数组特性与总结
- 需要连续的内存空间来储存;
- 添加元素的性能,与添加元素位置有直接关系,末尾添加效率很高,越往前走效率越低(因为要移动元素),所以在不确定的添加位置场景下,不适合用数组,而储存固定大小的同类型的元素,可以选择用数组;
- 查找效率高,根据索引能直接找出对应元素返回,找不到抛出对应异常;
- 扩容是按照原来数组容量(capacity)的一半扩容;
- 扩容是创建一个新数组,然后平移复制原来数组的方式,而不是直接在原来的数组后边直接扩容,这点是由于数组需要连续的内存空间决定的;
通过上边的原理分析与总结,我们来实战面试题,来测试理论的掌握程度。
实战面试题
- ArrayList的size和capacity怎么理解?
- ArrayList内部是怎么存放数据的?
- ArrayList的大小是如何自动扩容的?
- 在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?
- ArrayList中的remove是如何操作的?
- ArrayList的add操作优化?
这是数组常见的面试题,你能手到擒来吗?
在文章的末尾会给出标准的答案,有不懂的题目也不着急看答案,我们继续阅读源码来巩固与思考。
源码分析类结构
源码基于jdk1.8
,首先来一段ArrayList.java
类的介绍:
- 代码总行数
1469
行; - 实现了
AbstractList<E>
抽象类; - 继承
List<E>, RandomAccess, Cloneable, java.io.Serializable
;
源码方法分类讲解
先看下这张图:
有没有一下就懵了?不着急,我把这个类的方法分类一下:
这篇文章从继承、实现、属性、构造方法、常用方法(其他方法类不讲解)来分类讲解。
这里重复贴一下ArrayList类图。
继承
通过上边类图,你会发现ArrayList继承了AbstractList
抽象类,AbstractList实现了List接口,而AbstractList抽象类有且只有一个抽象方法:
1 |
|
这里看源码的同学绝对有个疑问,为什么AbstractList实现了List接口,而我们的ArrayList也再次来实现了List,为什么会这样子设计呢?
1 |
|
猜测有三:
- 增加可读性,不要套娃一样的去看源码,可以清晰看到类的主要实现接口;
- 兼容问题;
- 面向接口编程;
实现
ArrayList实现了List, RandomAccess, Cloneable, java.io.Serializable
接口;
ArrayList实现了List,提供了基础的添加、删除、遍历等操作;
ArrayList实现了RandomAccess,提供了随机访问的能力;
ArrayList实现了Cloneable,可以被克隆;
ArrayList实现了Serializable,可以被序列化;
属性
1 |
|
serialVersionUID 是用来验证版本一致性的字段。我们将一个类的二进制字节序列转为java对象,也就是反序列化时,JVM会把传进来的二进制字节流中的serialVersionUID和本地相应的实体或对象的serialVersionUID进行比较,如果相同,则认为两个类是一致的,可以进行反序列化,否则就会出现版本不一致的反序列化异常。
DEFAULT_CAPACITY 默认容量为10,也就是通过new ArrayList()创建时的默认容量。
EMPTY_ELEMENTDATA 空的数组,这种是通过new ArrayList(0)创建时用的是这个空数组(下边构造方法代码中可以看到)。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 也是空数组,这种是通过new ArrayList()创建时用的是这个空数组,与EMPTY_ELEMENTDATA的区别是在添加第一个元素时使用这个空数组的会初始化为DEFAULT_CAPACITY(10)个元素。
elementData 真正存放元素的地方,使用transient是为了不序列化这个字段,至于没有使用private修饰,后面注释是写的“为了简化嵌套类的访问”,但是楼主实测加了private嵌套类一样可以访问,private表示是类私有的属性,只要是在这个类内部都可以访问,嵌套类或者内部类也是在类的内部,所以也可以访问类的私有成员。
size 真正存储元素的个数,而不是elementData数组的长度(capacity)。
构造方法
ArrayList(int initialCapacity)构造方法
传入初始容量,如果大于0就初始化elementData为对应大小,如果等于0就使用EMPTY_ELEMENTDATA空数组,如果小于0抛出异常。
1 |
|
ArrayList()构造方法
不传初始容量,初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组,会在添加第一个元素的时候扩容为默认的大小,即10。
1 |
|
ArrayList(Collection<? extends E> c)构造方法
传入集合并初始化elementData,这里会使用拷贝把传入集合的元素拷贝到elementData数组中,如果元素个数为0,则初始化为EMPTY_ELEMENTDATA空数组。
1 |
|
为什么c.toArray();
返回的有可能不是Object[]类型呢?主要还是因为jdk自身的bug导致的。
源码注释:c.toArray might (incorrectly) not return Object[] (see 6260652)
https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
请看下面的代码:
1 |
|
常用方法(增删改查)
add(E e)方法
添加元素到末尾,平均时间复杂度为O(1)。
1 |
|
步骤:
- 检查是否需要扩容;
- 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA则初始化容量大小为DEFAULT_CAPACITY;
- 新容量是老容量的1.5倍(oldCapacity + (oldCapacity >> 1)),如果加了这么多容量发现比需要的容量还小,则以需要的容量为准;
- 创建新容量的数组并把老数组拷贝到新数组;
add(int index, E element)方法
添加元素到指定位置,平均时间复杂度为O(n)。
1 |
|
步骤:
- 检查索引是否越界;
- 检查是否需要扩容;
- 把插入索引位置后的元素都往后挪一位;
- 在插入索引位置放置插入的元素;
- 大小加1;
remove(int index)方法
删除指定索引位置的元素,时间复杂度为O(n)。
1 |
|
步骤:
- 检查索引是否越界;
- 获取指定索引位置的元素;
- 如果删除的不是最后一位,则其它元素往前移一位;
- 将最后一位置为null,方便GC回收;
- 返回删除的元素。
可以看到,ArrayList删除元素的时候并没有缩容。
remove(Object o)方法
删除指定元素值的元素,时间复杂度为O(n)。
1 |
|
步骤:
循环调用fastRemove(int index)
fastRemove(int index)
1 |
|
步骤:
- 找到第一个等于指定元素值的元素;
- 快速删除;
fastRemove(int index)相对于remove(int index)少了检查索引越界的操作,可见jdk将性能优化到极致。
set(int index, E element)方法
修改指定元素值的元素,时间复杂度为O(1)。
1 |
|
步骤:
- 检查索引是否越界,这里只检查是否越上界,如果越上界抛出IndexOutOfBoundsException异常,如果越下界抛出的是ArrayIndexOutOfBoundsException异常。
- 获取指定索引的位置的元素,赋值给oldValue,用于返回
- 设置指定索引位置的元素
- 返回oldValue
get(int index)方法
获取指定索引位置的元素,时间复杂度为O(1)。
1 |
|
步骤:
- 检查索引是否越界,这里只检查是否越上界,如果越上界抛出IndexOutOfBoundsException异常,如果越下界抛出的是ArrayIndexOutOfBoundsException异常。
- 返回索引位置处的元素;
源码总结
- ArrayList内部使用数组存储元素,当数组长度不够时进行扩容,每次加一半的空间,ArrayList不会进行缩容;
- ArrayList支持随机访问,通过索引访问元素极快,时间复杂度为O(1);
- ArrayList添加元素到尾部极快,平均时间复杂度为O(1);
- ArrayList添加元素到中间比较慢,因为要搬移元素,平均时间复杂度为O(n);
- ArrayList从尾部删除元素极快,时间复杂度为O(1);
- ArrayList从中间删除元素比较慢,因为要搬移元素,平均时间复杂度为O(n);
面试题答案
ArrayList的size和capacity怎么理解?
如果把 ArrayList 看作一个杯子的话,capacity 就是杯子的容积,也就是代表杯子能装多少东西,而 size 就是杯子装的东西的体积。杯子可能装满了,也可能没装满,所以 capacity >= size 。capacity 过大和过小都不好,过大会造成浪费,过小又存放不下多个元素的值,capacity == size,则 ArrayList 空间利用率最大,但是不利于添加新的元素。当 ArrayList 实例内的元素个数不再改变了,可以使用 trimToSize() 方法最小化 ArrayList 实例来节省空间,也即是使 capacity == size。
ArrayList内部是怎么存放数据的?
ArrayList 可以看做是数组的封装,使用 elementData 数组来存储数据,使用 size 来代表 elementData 的非 null 元素个数。elementData 前没有访问修饰符,所以只有同类和同包下的类可以直接方法,外界想要知道 ArrayList 实例内元素的个数就要通过 size 属性。elementData 数组类型是 Object 类型,可以存放任意的引用类型,不能存放基本的数据类型。
ArrayList的大小是如何自动扩容的?
扩容是发生在添加操作前的,要保证要添加元素在 elementData 数组中有位置,也即是 size 加上要添加的元素个数要小于 capacity(size + num <= capacity 就说明容量是充足的),所以在添加方法中,先调用 ensureCapacityInternal(int) 方法来确保 elementData 容量充足,然后再进行具体的添加操作。如果 ensureCapacityInternal 方法(ensureCapacityInternal 方法中有调用了其他方法)发现数组容量不够了,就会扩容。扩容实际的方法是 grow(int) 方法,使用位运算符来使数组的容量扩容 1.5 倍。但是需要注意的是,没有指定初始化值的 ArrayList 实例,第一次扩容并不是以 1.5 倍扩容的,而是使用的默认容量 10,所以网上很多直接说 ArrayList 扩容是 1.5 倍也有不当之处,这点从 JDK 源码中可以很明确的看出来。
如果在构造 ArrayList 实例时,指定初始化值(初始化容量或者集合),那么就会创建指定大小的 Object 数组,并把该数组对象的引用赋值给 elementData;如果不指定初始化值,在第一次添加元素值时会使用默认的容量大小 10 作为 elementData 数组的初始容量,使用 Arrays.conpyOf() 方法创建一个 Object[10] 数组。
在索引中ArrayList的增加或者删除某个对象的运行过程?效率很低吗?解释一下为什么?
其实通过上边的源码可以知道,我们要分情况来讨论,详情见源码总结3、4、5、6点。
ArrayList中的remove是如何操作的?
见源码remove解析。
ArrayList的add操作优化?
核心就是避免 ArrayList 内部进行扩容。
1、对于普通少量的 add 操作,如果插入元素的个数已知,最好使用带初始化参数的构造方法,避免 ArrayList 内部再进行扩容,提高性能。
2、对于大量的 add 操作,最好先使用 ensureCapacity 方法来确保 elementData 数组中有充足的容量来存放我们后面 add 操作的元素,避免 ArrayList 实例内部进行扩容。上面提到的 ensureCapacityInternal 方法是一个私有方法,不能直接调用,而 ensureCapacity 方法是一个共有方法,专门提供给开发者使用的,提高大量 add 操作的性能。
我是连边,专注于Java和架构领域,坚持撰写有原理,有实战,有体系的技术文章。
可以关注订阅号@连边
不错过精彩文章