基于Eclipse Adoptium jdk-11.0.13.8-hotspot,对ArrayList的源码进行分析
打开ArrayList的源码一看,有几属性:
- DEFAULT_CAPACITY:默认容量是10
- EMPTY_ELEMENTDATA:空数组
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA:默认用来判断扩容的空数组
- elementData:用来存储元素的数组
- 其他的不展示了,太多了
ArrayList默认构造函数
ArrayList默认的构造函数,会将elementData初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA,就是一个空数组。
add(element)方法
先看看ArrayList.add(element)方法,这里面调用了另外一个add()方法,跟进去看看:
这个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;
示例:
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,将新的元素设置到这个位置。
最后返回旧的元素。
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)方法。
elementData(index)方法就更加简单了,直接通过下标找到元素。
remove(index)方法
remove(index)方法:
开始检查下标是否越界,然后把elementData赋值给es,然后通过下标从es[]数组中获取出来要删除的元素。
然后调用fastRemove(element, index)方法。
fastRemove(element, index)方法:
这行代码,就是判断一下新的size是否大于删除的下标。
然后把后面的元素拷贝一份,往前一格粘贴。
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
最后这一行代码:
就是把最后一位元素给设置为null,清掉。
es[size = newSize] = null;
示例:
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)方法。
最后去删除这个元素等一大堆操作。
上面分析过了,就不再分析了。
最后再说一下,像add(index, element)和remove(index、object)这种方法,每次随机的插入和删除都要去拷贝数组,性能是很差的。