ArrayList源码解读

这篇文章带领大家走进ArrayList的源码世界。首先用最简短的大白话概括下文章的内容

  • 底层基于数组,查找元素时间o(1),增加删除元素涉及到元素移位,时间为o(n)
  • 无参构造器时,就只做了一个操作,Object[] elementData = {}
  • 无参构造器时,第一次添加新元素,会触发数组扩容方法,会用到数组默认容量10
  • 无参构造器时,数组容量满时再次增加元素,也会触发数组扩容方法,会进行1.5倍扩容,扩容使用到的是Arrays.copyOf()方法,本质就是创建一个新数组,将老数组的元素赋值到新数组中的位置上去
  • 元素插入,需要检查角标,然后判断数组是否需要扩容,都符合就进行System.arraycopy()进行数组的移位
  • 元素删除,需要检查角标,也需要进行System.arraycopy()数组的移位,插入删除时间为o(n)

ArrayList的CRUD

1
2
3
4
5
6
7
8
ArrayList arrayList = new ArrayList();
arrayList.add("哈哈");
arrayList.add(1,"嘻嘻");
arrayList.add("呵呵");
arrayList.remove("哈哈");
arrayList.remove(0);
arrayList.set(0,"嘻哈");
Object value = arrayList.get(0);

想必这些简单的增删改查方法大家熟的不能再熟了吧,那么现在就跟随着我赶紧去看看源码吧~

ArrayList的源码世界

核心数据结构

ArrayList底层是数组,那么肯定会有两个最基本的元素:一个数组结构用于存放元素,一个size结构用于记录数组中当前元素的个数

1
2
3
4
5
6
public class ArrayList {
transient Object[] elementData;// 数组
private int size;// 数组元素个数
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 默认空数组
private static final int DEFAULT_CAPACITY = 10;// 默认是10个元素
}

构造方法

1
2
3
4
5
6
7
8
9
10
11
12
13
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
}
}

我们日常中最常用的两种构造方法,想必就是这两种了吧

  1. 直接使用空参构造器,new ArrayList()这样
  2. 开发习惯好一点的,可能会初始化一下数组的容量,new ArrayList(int initialCapacity)这样

通过看构造方法的源码可知:

  • 对于无参构造方法来说,初始化就干了一件事,那就是 Object[] elementData = {},将核心数组给设置成了空数组。并且很关键的一点是,此时没有给这个elementData分配默认容量
  • 对于有参构造方法来说,参数中传递了initialCapacity数组容量大小,如果initialCapacity > 0,那么初始化方法为Object[] elementData = new Object[initialCapacity]; 构造了一个容量为initialCapacity的数组;如果initialCapacity == 0,就是将数组给设置为空数组了,Object[] elementData = {};如果initialCapacity < 0,直接抛出异常

现在我们用无参构造方法创建出来一个ArrayList对象,来看看它的CRUD都是怎么玩的吧~

增加操作的源码

对于ArrayList来说,增加元素的方法API就是调用的 add(E e) 方法,用一个步骤来说明就是:

  1. 增加元素之前,首先判断是否需要扩容,此时数组中的容量应该为size+1,需判断当前容量是否能容纳得下
  2. 将元素赋值给 size 指向的数组位置,此时相当于数组中这个角标中已经有这个新元素了
  3. size++,表示数组中的容量大小加1,毕竟增加了一个新元素啦
1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

第2,3步骤都没有什么可说的,着重就是看第一步骤,判断数组是否需要扩容可能会发现奇迹哦!

1
2
3
4
5
6
7
8
9
10
11
12
13
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

// 这里为了方便看源码,我们将这些方法中的代码给展开到
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

这个 ensureCapacityInternal() 方法就是判断数组是否需要扩容,从这块代码可以看到,需要分两种情况来分析:

  1. 第一种情况:第一次给ArrayList增加元素的时候,此时elementData = {},minCapacity的值为DEFAULT_CAPACITY=10,此时 minCapacity - elementData.length = 10 - 0 = 10 > 0,可知第一次增加元素的时候,就会走 grow(10) 扩容的方法,新大陆了,原来无参构造器中,第一次增加元素的过程,会触发数组扩容的操作,至于怎么扩容的,下面分析
  2. 第二种情况:假设此时数组中已经有一个元素的情况下,再次增加元素,这里判断是否需要扩容的代码逻辑就成为,minCapacity = size + 1 = 2,得判断如果这个元素进入数组了,数组容量能否撑得住?发现 2 - 10 是小于0的,所以此时不会进入grow()扩容方法……当数组中已经有10个元素了,新增加第11个元素时,此时的minCapacity = size + 1 = 11,发现比数组容量10大了,进入 grow() 扩容方法,至于怎么扩容的,下面分析

看到现在就能明白了,数组中采用无参构造器创建ArrayList对象,会有两种情况会触发数组扩容

  1. 第一种情况是第一次创建元素会进行数组扩容;
  2. 第二种情况是当数组容量满了的时候,还在往数组中新增元素时,也会触发数组的扩容。接着,就开始进入数组扩容的分析吧~~
1
2
3
4
5
6
7
8
9
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;// 【标记A】
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}

还是按照两种情况进行分析,新大陆就出现了哦

  1. 第一种情况,无参构造器,第一次增加元素的时候:此时minCapacity = 10,oldCapacity = 0,newCapacity = newCapacity * 1.5 = 0,正是由于0 - 10 = -10 < 0,就进入代码【标记A】中,将 newCapacity 设置为 10,这一个就可以看做是用默认长度10进行数组容量的初始化了。 elementData = Arrays.copyOf(elementData, 10); 进行数组的拷贝了
  2. 第二种情况,数组此时有10个元素了,再次新增加元素时:此时minCapacity = 11,oldCapacity = 10,newCapacity = newCapacity * 1.5 = 15,扩容后数组新容量为15,就不会进入那两个if 条件判断了,直接是采用方法 elementData = Arrays.copyOf(elementData, 15); 进行数组的拷贝了

分析这行代码 elementData = Arrays.copyOf(elementData, newCapacity); 数组拷贝,本质就是创建一个新的容量为newCapacity的数组,将老数组elementData中的元素拷贝到新数组中去,证明如下:

1
2
3
4
5
6
7
8
9
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType){
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
// Arrays.copy()的方法,创建了一个新数组,底层还是调用了 System.arraycopy(),进行数组元素移位,拷贝

好了,分析到这里,主要就将增加元素的源码给弄明白啦,接下来继续看插入操作的源码吧~

插入操作的源码

对于ArrayList来说,插入元素的方法API就是调用的 add(int index, E element) 方法,用一个步骤来说明就是:

  1. 首先判断插入位置的角标是否合法
  2. 插入操作,也得首先进行数组是否需要扩容的判断,若需要,就先扩容
  3. 然后用System.arraycopy()进行数组元素的移位,相当于从插入元素的位置起,后面的元素,从最后一个元素依次向后移动一位,给要插入的元素挪动一个位置出来
  4. 将挪动出来的位置给插入元素
  5. 数组元素大小size++
1
2
3
4
5
6
7
8
9
10
11
public void add(int index, E element) {
// 插入的角标不符合,直接抛出异常
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 判断数组是否需要扩容
ensureCapacityInternal(size + 1);
// 数组元素的移位,不会新创建数组,就是在老数组中进行的
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}

插入操作的源码,主要就是这个数组元素移位的操作很关键。这里是用的java api 直接操作的,如果是让我们手写一个数组元素的移位,也是很简单的,就是从最后一个元素开始循环,直到插入元素的角标位置,循环里面的元素依次往后移动移位就行了。正是由于这里出现了数组的移位操作,就导致增加的时间复杂度为o(n)

修改操作的源码

对于ArrayList来说,修改元素的方法API就是调用的 set(int index, E element) 方法,用一个步骤来说明就是:

  1. 校验修改的元素角标是否合法
  2. 获取当前角标中的老元素
  3. 将新元素赋值到这个插入位置上
  4. 返回老元素
1
2
3
4
5
6
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}

修改操作的源码也是很简单的,就是根据角标拿到当前角标中的元素,然后将新元素给设置到了这个角标中

1
2
3
E elementData(int index) {
return (E) elementData[index]; // elementData()方法就是根据角标取元素,时间o(1)的操作
}

查询操作的源码

对于ArrayList来说,查询元素的方法API就是调用的 get(int index) 方法,用一个步骤来说明就是:

  1. 校验查询的角标是否合法,index < 0 或者 index >= size 就是非法的
  2. 然后通过角标获取数组中的元素,时间为o(1)的方法
1
2
3
4
public E get(int index) {
rangeCheck(index);
return elementData(index);
}

删除操作的源码

对于ArrayList来说,删除元素的方法API就是调用的 remove(Object o) 或者 remove(int index) 方法,可以指定角标删除,也可以指定要删除的某一个具体的元素,这里就分析根据角标删除的源码吧,用一个步骤来说明就是:

  1. 校验删除角标是否合法
  2. 将当前删除位置的角标对应的元素取出来
  3. 采用System.arraycopy()进行数组元素移位,核心就是从删除元素的后一个位置开始,直到数组的最后一个元素,对于循环中的元素依次往前挪动一位,表示将要删除的位置给覆盖掉,完成删除操作
  4. 由于此时元素少了一位,就将size肯定要-1,同时将最后一个元素设置为null
  5. 最后返回这个角标下的老元素
1
2
3
4
5
6
7
8
9
10
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null;
return oldValue;
}

删除操作也涉及到移位了,用的api直接操作的,如果让咱们手写这块算法,我相信也是难不倒大家的,核心就是依次往前挪动一位,把要删除的位置元素给覆盖掉,相当于挤掉了。用数字分析这个过程就是:数组中有元素 1,2,3,4,5。此时要删除index=2的元素

  1. 从index+1=3的位置开始,将后面的元素依次往前移动,此时就成为了 1,2,4,5,5
  2. 此时由于少了一个元素size就会-1,变为4,然后将index=4的元素设置为null,1,2,4,5,null。

小节

到目前位置,已经将ArrayList的核心数据结构,常见操作的源码都分析了一遍,大家是不是对这块知识的理解更深入了呢~~~

主要就是记住数组的优点就是查询快,增删慢,然后会有扩容的操作。我们建议最好是在ArrayList构造的时候,给一个比较靠谱的初始化的数组的大小,避免数组容量太小,往里面塞入数据的时候,导致不断的在内存开辟新的数组进行数组扩容操作。