LXX的网络日志
人因梦想而伟大
ArrayList源码剖析(二):核心方法的原理

基于Eclipse Adoptium jdk-11.0.13.8-hotspot,对ArrayList的源码进行分析

打开ArrayList的源码一看,有几属性:

  • DEFAULT_CAPACITY:默认容量是10
  • EMPTY_ELEMENTDATA:空数组
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA:默认用来判断扩容的空数组
  • elementData:用来存储元素的数组
  • 其他的不展示了,太多了

ArrayList部分源码截图.png

ArrayList默认构造函数

ArrayList默认的构造函数,会将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,就是一个空数组。

ArrayList默认构造函数.png

add(element)方法

先看看ArrayList.add(element)方法,这里面调用了另外一个add()方法,跟进去看看:

ArrayListaddobject.png

这个add(element)方法,首先会判断一下size是否与数组的长度一样,如果一样,就会调用grow()方法,进行扩容,把elementData扩容到10个,这个扩容的源码后面再分析了。

如果不一样,直接插入数组的里面,刚开始的话呢,s就是0,也就是插入数组的第一个位置,并且对size加1。

这个size+1呢,就是下个元素插进来的的时候,都是插入数组的尾部。

插入示例:

List<String> arr = new ArrayList<>();
arr.add("张三");
arr.add("李四");

// 第一次插入的时候差不多就是这样
// s = 0;
// elementData[s] = "张三";
// size = s + 1;
// elementData=["张三", null, null, null, null, null, null, null, null, null];

// 第二次插入
// s = 1;
// elementData[s] = "李四";
// size = s + 1;
// elementData=["张三","李四", null, null, null, null, null, null, null, null];


add的基本原理就是这样。

add(index, element)方法

再来看看add(index, element)这个方法,一开始检查是否越界。

然后这一行代码,如果数组是空的或者容量不够用了,就去执行grow()进行扩容。

if ((s = size) == (elementData = this.elementData).length)
    elementData = grow();

这下面的代码,简单的说,就是把这个位置的元素以及后面的元素全部往后面一个位置拷贝,然后再把新元素覆盖在指定的位置。

最后size再加一。

System.arraycopy(elementData, index,
                 elementData, index + 1,
                 s - index);
elementData[index] = element;
size = s + 1;

ArrayListaddindex,object.png

示例:

List<String> arr = new ArrayList<>();
arr.add("张三");
arr.add("李四");
// elementData=["张三", "李四", null, null, null, null, null, null, null, null];
arr.add(1,"王五");
// add(index, elementData) 之后
// 先把 "李四"这个元素,以及后面的元素,全部拷贝,然后再往后面一格粘贴
// elementData=["张三", "李四", "李四", null, null, null, null, null, null, null];
// 然后再把新的元素插入(覆盖)进来
// elementData=["张三", "王五", "李四", null, null, null, null, null, null, null];

把元素添加到指定的位置,这个原理就是这么简单,下面继续来看看set(index, element)方法。

set(index, element)方法

再来看看set(index, e)方法里面的源码,这个set()方法其实就是替换指定位置的元素:

Objects.checkIndex(index, size),这行代码没啥好说的,就是检查一下插入的位置,越界没有。

E oldValue = elementData(index),这行代码就是获取出来这个位置原来的元素。

elementData[index] = element,将新的元素设置到这个位置。

最后返回旧的元素。

ArrayListset.png

Set示例:

List<String> arr = new ArrayList<>();
arr.add("张三");
arr.add("李四");
// elementData=["张三","李四", null, null, null, null, null, null, null, null];
arr.set(1, "王五");
// set 之后,直接覆盖掉 "李四" 这个元素
// elementData=["张三","王五", null, null, null, null, null, null, null, null];

set(index, element)方法的原理,简单的说就是这样。

get(index)方法

get(index)方法,这个代码很简单,一开始检查是否越界。

然后调用elementData(index)方法。

ArrayListget.png

elementData(index)方法就更加简单了,直接通过下标找到元素。

ArrayList.elementData.png

remove(index)方法

remove(index)方法:

开始检查下标是否越界,然后把elementData赋值给es,然后通过下标从es[]数组中获取出来要删除的元素。

然后调用fastRemove(element, index)方法。

ArrayList.removeindex.png

fastRemove(element, index)方法:

这行代码,就是判断一下新的size是否大于删除的下标。

然后把后面的元素拷贝一份,往前一格粘贴。

if ((newSize = size - 1) > i)
    System.arraycopy(es, i + 1, es, i, newSize - i);

最后这一行代码:

就是把最后一位元素给设置为null,清掉。

es[size = newSize] = null;

ArrayListfastRemove.png

示例:

ArrayList<String> arr = new ArrayList<>();
arr.add("张三");
arr.add("李四");
// elementData=["张三","李四", null, null, null, null, null, null, null, null];
arr.remove(0);
// removes时,先把要删除元素的位置的后面的所有元素,拷贝一份,然后往前面一格粘贴,这个时候数组里是这样的:
// elementData=["李四","李四", null, null, null, null, null, null, null, null];
// 然后再把数组里面的最后一个元素给设置为null,清掉,此时数组里面是这样的:
// elementData=["李四",null, null, null, null, null, null, null, null, null];

remove(object)方法

remove(object)方法:

主要是看found这个label标签里面的循环,其实就是从数组里面找到这个元素,在找的过程中会计算这个下标,找到之后就去执行fastRemove(elementData,index)方法。

最后去删除这个元素等一大堆操作。

上面分析过了,就不再分析了。

ArrayList.removeobject.png

最后再说一下,像add(index, element)和remove(index、object)这种方法,每次随机的插入和删除都要去拷贝数组,性能是很差的。