ArrayList源码详解

1、家族情况

ArrayList

由上图可知ArrayList继承了AbstractList类并且实现了RandomAccessCloneableSerializable这几个接口。

这里主要讲下RandomAccess接口。打开源码后可以发现这是一个空接口,没有声明任何变量和方法。所以他只起一个“标记”,让别人可以通过instance of方法判断这list是支持下标随机访问的。如果实现了RandomAccess那么使用for循环遍历下标的方式是速度最快的。相应的LinkedList则使用迭代器Iterator的方式遍历集合的速度最快。也就是说这个接口决定了jdk内部使用何种方式遍历list。详细对于RandomAccess的介绍可以看这篇文章

2、成员变量

在正式探究源码之前让我们先把几个重要的成员变量理一下

  • DEFAULT_CAPACITY

    类型是int,初始化时默认的数组大小,这里的默认值是10。

  • elementData

    类型是Object数组,这个数组存放list中的的具体数据,如果不够了,会进行扩充。

  • EMPTY_ELEMENTDATA

    类型是Object数组,值是一个空数组。如果外部初始化ArrayList时指定数组大小为0,那么将会把这个值赋值给elementData变量。

  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    类型是Object数组,值也是一个空数组。不过需要区分的的是,如果初始化ArrayList的时候默认没传任何参数,那么将会把这个值赋值给elementData变量。当用户首次调用add方式时,再将elementData的值变成一个DEFAULT_CAPACITY大小的数组。

  • size

    当前ArrayList中真实存在的元素的数量。

3、初始化方式

ArrayList的内部是用数组来盛装具体的内容。ArrayList提供3中初始化方式:

  • 默认构造方法
1
List list1 = new ArrayList();
  • 指定初始长度
1
List list2 = new ArrayList(5);
  • 基于当前集合创造新的集合(浅拷贝)
1
2
3
4
String value=new String("1");
List ll = new LinkedList();
ll.add(value);
List list3 = new ArrayList(ll);

4、add方法

当调用ArrayList的add方法时,会在ArrayList的末尾加一个新元素。

arraylist-add方法

这里有一个重要的方法ensureCapacityInternal,该方法主要确保成员变量elementData数组中有足够的空位来放置新添加的元素。如果不够则需要将elementData数组进行扩充。再来看到底什么情况下才需要扩充数组。

arraylist-ensureCapacityInternal

minCapacity最小容量是size+1,也就是当前ArrayList中真实存在的元素的数量+1。如果使用的是空构造方法初始化ArrayList,那么最小容量(minCapacity)至少要是DEFAULT_CAPACITY(10)以上。得出最小容量之后,我们可以看到,如果当前elementData所能盛装的数量小于最小容量的话,那么说明当前elementData数组需要扩容(grow)。

arraylist扩容

最终要的代码是这一行,oldCapacity >> 1向右位移,相当于是除以2。也就是说newCapacity是原来elementData的1.5倍。

1
2
3
int newCapacity = oldCapacity + (oldCapacity >> 1);
//等效于
int newCapacity = oldCapacity + (oldCapacity / 2);

等计算出新的大小之后,再使用Arrays.copyOf方法创造一个新数组,该数组的长度是newCpacity。再将原先的数组内容的引用地址复制到新数组数组中。这样就做到了elementData数组的扩容。

5、remove方法

arraylist-remove

删除方法就比较简单,首先判断外部传入的index是否合法,再就是数组的切割。这也就是这块最关键的代码。

1
System.arraycopy(elementData, index+1, elementData, index, numMoved);

这几个参数分别的意思是:

  • 源数组
  • 在源数组的起始下标
  • 目标数组
  • 在目标数组的起始下标
  • 要复制的数组长度

下面举一个例子,我们要删除arr中第三个元素,也就是字母c

1
2
3
char [] arr = {'a','b','c','d'};
System.arraycopy(arr,3,arr,2,1);
//arr:[a、b、d、d]

可以发现最后一个元素重复了,所以需要将他置为null,好让垃圾回收。

1
elementData[--size] = null;

从上面的删除逻辑可以看出,删除一个元素并不会时elementData的大小收缩。但是可以额外的调用ArrayList的trimToSize方法,去掉多余的空值,让elementData的大小和实际存放元素的数量相等。

原文链接:https://www.jdkdownload.com/arraylist_detail.html