硬核ArrayList源码分析,答应我每天看一遍好么

一 前言

知识追寻者目前的系列都是基于jdk1.8进行学习分析;本篇源码分析会进行每步分析,当所有方法分析完最后还会做个大总结;如果不爱看源码分析步骤,只要面试最终结论的读者可以看看文末的总结就行了;

知识追寻者(Inheriting the spirit of open source, Spreading technology knowledge;)

二 ArrayList源码分析
2.2 空参构造方法源码分析

调试代码

public static void main(String[] args) {
// 初始化长度为0
ArrayList list = new ArrayList();//断点
}

首先刚刚开始调到断点时,会默认显示ArrayList初始化长度为0;

其次进入构造方法

public ArrayList() {
// elementData 是 Object[] ---> 故 Arraylist底层由对象数组实现
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

可以看出就是一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData ;

先看看什么是DEFAULTCAPACITY_EMPTY_ELEMENTDATA,源码如下,可以看出是final修饰的Object[]数组;

// 共享的空数组实例,当第一个元素添加时从EMPTY_ELEMENTDATA辨别出扩张大小
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

再看看elementData是什么,源码如下

// 动态数组缓冲区,ArrayList存储元素的地方,elementData长度就是ArrayList长度
// 当第一个元素添加时 DEFAULT_CAPACITY 被被扩张
transient Object[] elementData; // non-private to simplify nested class access

后面再进入调试会进入父类,给张类图看看ArrayList的都继承了哪些父类

真正的步入顺序如下

AbstractList –> AbstractCollection–> Object

有趣的是知识追寻者在分析过程中还发行执行了如下一行代码,也就是记录list大小改变的次数,如果发生了无法预料的改变就会抛出ConcurrentModificationException异常;这就解释了为什么在迭代器中不能进行使用List的remove等操作(这边就不对迭代器Iterator进行扩展,后面会出相关源码分析);这是由fail-fast机制提供的方案;

科普fail-fast 机制

fail-fast 机制 就是快速失败机制,也就是在集合发送结构改变的时候会抛出ConcurrentModificationException异常,用于快速的对bug进行检测做出失败判定;

// 记录list被修改的次数,也就是大小改变的次数
// 如果在迭代器中使用迭代,做出了不是期待的改变就会抛出ConcurrentModificationException
protected transient int modCount = 0;

Tip1 : 以后面试答List集合在迭代过程中调用了remove方法后会发生什么情况?答:我看过知识追寻者ArrayList源码系列文章,是由于 fail-fast机制检测到List发生结构变化抛出了 ConcurrentModificationException 异常;瞬间高大尚有木有,难道我答是由于集合在迭代过程中发生了remove,add, set , next, previous操作?太细节了吧,太low了吧,有实力的面试官就知道你水平了,小伙子背的不错额!

Tip: ArrayList底层基于动态Object数组实现

2.2 初始化容量源码分析

ArrayList的初始化容量大体就给定初始化值,则创建对应大小的Object数组;没有给定初值值,则使用成员共享遍历空Object数组;否则其它情况抛出非法参数异常;

测试代码

public static void main(String[] args) {
// 初始化为0
ArrayList list = new ArrayList(5);
}

源码

public ArrayList(int initialCapacity) {
// 初始化容量大于0,创建指定大小的object数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 初始化容量等于0,空 object数组
} else if (initialCapacity == 0) {
// 其中 private static final Object[] EMPTY_ELEMENTDATA = {};
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 否则抛出非法参数异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

Tip 给定指定大小的容量进行初始化ArrayList会返回指定大小的ArrayList

2.3 add方法源码分析

测试代码

public static void main(String[] args) {
// 初始化为0
ArrayList list = new ArrayList();
list.add("a");
System.out.println(list);
}

首先:先看看add源码

public boolean add(E e) {
// 确保容量
// size就是list的大小,也就是集包含合的元素个数
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

可以看见有个ensureCapacityInternal(size + 1) 方法进行了确保容量,直接从这个表达式上可以得出结论在原来的数组长度上加1;进入看看

private void ensureCapacityInternal(int minCapacity) {
// 期望大小 添加1个a 所以是1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 判定是否是空数组
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
// 在1 和 10(DEFAULT_CAPACITY)中取最大值
}

ensureExplicitCapacity(minCapacity);//此时就是10
}

调试源码上可以直接得出结论如果,由于加入的的元素是1,所以期望容量为1,当经过与默认的初始容量比较后取最大值,此时就是10;所以添加一个元素后ArrayList的期望扩容大小扩大到了10

我们看下确保具体的扩容,集合修改次数 加1 ,如果期望扩容大于大于了ArrayList长度,会进行再次扩容;

private void ensureExplicitCapacity(int minCapacity) {
modCount++;//list改变次数加1

// overflow-conscious code
//如果期望扩容小于元素ArrayList长度,会进行再次扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);//扩容
}

看下扩容grow(minCapacity); 其内部实现思路也很简单,每次扩容都是在原来List长度上加 50%;如果期望容量超过了数组最大长度 (int整数最大值 – 8) 就使用int整数最大值 作为数组长度;最后会进行数组拷贝和重新指定数组大小;这边值的一说是 数会保留8个位置作为数组头的预留位置,如果分配长度超过数组最大长度MAX_ARRAY_SIZE就会抛出OutOfMemoryError异常,;VM 通常都会限制这个大小,实际中可能没到 MAX_ARRAY_SIZE 就抛出最大异常了,更不用说 int 的最大值;

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;//oldCapacity=0 当前元素a未插入时的长度
int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity=0 原始长度 + 原始长度左移一位,也就是 除以2; 如果长度10,经过扩容后就是15
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;//(0-10) 0)
newCapacity = hugeCapacity(minCapacity);///如果期望容量大于数组容量最大值就使用Int最大值;否则使用数组最大值
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);//数组拷贝,容量为10
}

hugeCapacity(minCapacity); 源码如下

private static int hugeCapacity(int minCapacity) {
if (minCapacity MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}

Tip : ArrayList 初始化容量为0,添加一个元素后扩容到10;超过10后每次在原有的数组长度上 加50%长度进行扩容;ArrayList 的 最大长度为 Integer.MAX_VALUE – 8; 最后会调用 Arrays.copyOf 方法重新赋值 Object数组

2.4 set 源码分析

测试代码

public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("a");
list.set(0,"b");
System.out.println(list);
}

首先进入set方法

public E set(int index, E element) {
rangeCheck(index);// index =0 ; element = b ;检测ArrayList是否越界

E oldValue = elementData(index);//获取原来数组索引对象
elementData[index] = element;//根据对应重新赋值
return oldValue;//返回对象
}

第一行就是检测ArrayList是否越界

private void rangeCheck(int index) {
if (index >= size) // 给定索引大于等于数组长度抛出异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

第二行是获取原来Object数组位置上的对象;

@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];// index =0 ; elementData 是个 object[] }

第三行根据索引重新赋值,最后返回;那么 这边 oldValue 就是 elementData[index];

Tip : set方法就是重新赋值数组位置上的值;相当于更新操作;如果给定位置上没有元素,会抛异常;

2.5 get 源码分析

测试代码

public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("a");
list.get(0);
System.out.println(list);
}

进入get方法

public E get(int index) {
rangeCheck(index);//检测数组是否越界

return elementData(index);//获取数组对应位置上的对象
}

与set方法后面一致,还是调用elementData获取数组对应位置上的对象;get 方法没什么奇特点;

2.6 remove源码分析

测试代码

public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add("a");
list.add("b");
list.remove(0);
System.out.println(list);
}

源码如下,整体

public E remove(int index) {
rangeCheck(index);// 检测数组是否越界

modCount++;//修改次数 +1
E oldValue = elementData(index);//获取数组index位置上的值 oldValue=a

int numMoved = size - index - 1;// numMoved = 2-0-1 = 1;表示移动的数量
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//数组拷贝
elementData[--size] = null; // clear to let GC do its work.数组长度 -1 位置置为null.

return oldValue;//返回移除的值
}

这边可以对arraycopy方法进行一个简要说明

public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);

参数

src 要被复制的数组
srcPos 开始复制的下标
dest 目标数组
destPos 开始存放数据的位置
length 放置个数

说完不懂的人肯定还是一头雾水,我们举个栗子看看

public static void main(String[] args) {
int[] src = new int[]{1,2,3,4,5};
int[] desc = new int[]{6,7,8,9,10};
System.arraycopy(src,2,desc,1,2);
Arrays.stream(desc).boxed().forEach(des ->{
System.out.println(des); // 6 ,3, 4, 9, 10
});
}

src 从 位置index = 2 开始取值,取几个呢取length = 2 个 (也就是3和4);将其放入 desc 的index = 1 的位置开始,此时就会完成覆盖也就是(3,4会覆盖7,8)

原理懂咧,那么刚刚那个源码里面是 src 和 desc 都是一同一个数组,假定要删除index =0 (即元素1);该复制几位?movNum = size – index -1 = 5 – 0- 1 = 4 ; 需要复制4位;src 的 2,3,4,5 就会覆盖 1,2,3,4;最终得到 2 ,3,4,5,5; 最后将 最后一个元素置为 null 就完成了删除操作!! 哦哦哦 你学会了么,知识追寻者学会了,瞬间高大尚,以后写数据结构又有的玩了;

public static void main(String[] args) {
int[] src = new int[]{1,2,3,4,5};
int[] desc = new int[]{1,2,3,4,5};
System.arraycopy(src,1,desc,0,4);
Arrays.stream(desc).boxed().forEach(des ->{
System.out.println(des); // 2,3,4,5,5
});

}

Tip remove 操作 底层调用的是System.arraycopy 方法,将 要删除元素后面所有元素进行拷贝至删除元素索引位置,再将数组尾节点置为null

三 总结

集合在迭代过程中发生了remove,add, set , next, previous操作,会触发fast-fail机制,抛出做出了不是期待的改变就会抛出ConcurrentModificationException;
ArrayList底层基于动态Object数组实现, 所有数组的优缺点和ArrayList差不多,查找快把,增删慢;
ArrayList 初始化容量为0,添加一个元素后扩容到10;超过10后每次在原有的数组长度上 加50%长度进行扩容;ArrayList 的 最大长度为 Integer.MAX_VALUE – 8;给定指定大小的容量进行初始化ArrayList会返回指定大小的ArrayList;
set方法就是重新赋值数组位置上的值;相当于更新操作;如果给定位置上没有元素,会抛异常;
remove 操作 底层调用的是System.arraycopy 方法,将 要删除元素后面所有元素进行拷贝至删除元素索引位置,再将数组尾节点置为null;

半天就过去了;知识追寻者有空再补ArrayList其它方法的源码吧;

作者:知识追寻者

相关推荐

Vue 中 template 有且只能一个 root的原因解析(源码分析)

VisualStudio2019中为.NET Core WinForm App启用窗体设计器

VisualStudio2019中为.NET Core WinForm App启用窗体设计器

visual studio 2019使用net core3.0创建winform无法使用窗体设计器

antd-mobile ListView长列表的数据更新遇到的坑