最详细集合源码解析之ArrayList集合源码解析

从今天开始我会将集合源码分析陆陆续续整理，写成文章形成集合源码系列文章，方便大家学习

ArrayList集合源码其实相对比较简单，整个源码结构相对于HashMap等源码要好理解的多；先来看下ArrayList整体结构

ArrayList整体结构

01实现Cloneable接口

为什么要实现这个接口呢，ArrayList会调用clone()方法，这个方法是object的方法，调用该方法的对象必须要实现Cloneable接口，否则会抛出 CloneNoSupportException异常。

02实现 RandomAccess接口

这个接口就是一个标识接口，在JAVA官方定义中实现该接口的List就表示这个类可以实现快速随机访问,使用for循环获取数据的效率要优于迭代器获取数据得效率

03实现Serializable接口

这个接口也是个标识接口，代表可以被序列化。

04继承AbstractList并实现List接口

其实List接口定义了一些方法，实现该接口的类都必须实现这些方法，这些方法会在后续进行详细讲解，先放张图看看有哪些方法。

字段属性

/**
?????*?默认初始容量.
?????*/
????private?static?final?int?DEFAULT_CAPACITY?=?10;

????/**
?????*?空的数组实例
?????*/
????private?static?final?Object[]?EMPTY_ELEMENTDATA?=?{};

????/**
?????*?这也是空的数组实例，和EMPTY_ELEMENTDATA相比用于了解添加元素时数组膨胀多少
?????*/
????private?static?final?Object[]?DEFAULTCAPACITY_EMPTY_ELEMENTDATA?=?{};

????/**
?????*?存储ArrayList数据的数组
?????*/
????transient?Object[]?elementData;?//?non-private?to?simplify?nested?class?access

????/**
?????*?表示集合的长度
?????*
?????*?@serial
?????*/
????private?int?size;

构造函数解析01设置初始容量

????public?ArrayList(int?initialCapacity)?{
????????//判断传的初始容量是否大于0
????????if?(initialCapacity?>?0)?{
????????????//大于0就创建设置的容量大小的数组
????????????this.elementData?=?new?Object[initialCapacity];
????????}?else?if?(initialCapacity?==?0)?{
????????????//等于0就创建空数组
????????????this.elementData?=?EMPTY_ELEMENTDATA;
????????}?else?{
????????????//小于0抛出异常
????????????throw?new?IllegalArgumentException("Illegal?Capacity:?"?+
????????????????????initialCapacity);
????????}
????}

02 无参构造

??public?ArrayList()?{
????????this.elementData?=?DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
????}

03传入一个集合

????public?ArrayList(Collection<??extends?E>?c)?{
?????????//将传入的集合转为数组赋值给elementDate
????????elementData?=?c.toArray();
????????//将该数组的长度赋值给size并判断该集合是否为空
????????if?((size?=?elementData.length)?!=?0)?{
?????????????//判断数组元素对象是否为Object类
????????????if?(elementData.getClass()?!=?Object[].class)
????????????????//不是的话就重新复制
????????????????elementData?=?Arrays.copyOf(elementData,?size,?Object[].class);
????????}?else?{

????????????//传入的集合为空就创建一个空手数组
????????????this.elementData?=?EMPTY_ELEMENTDATA;
????????}
????}

这里面有两点需要注意一下，有的人看到这段代码可能会有疑惑，代码第一步就已经将集合转为数组传给elementData了，为什么下面还要进行一步判断然后进行数组复制呢？

这是因为toArray方法可能会存在返回的不是Object类型的数组，因此要多加一步判断进行校验；通过Arrays.copyOf方法进行重新赋值。

add方法

添加元素，添加元素算是ArrayList核心的方法，添加元素会涉及到数组的扩容操作。

???public?boolean?add(E?e)?{
????????ensureCapacityInternal(size?+?1);??//?Increments?modCount!!
????????elementData[size++]?=?e;
????????return?true;
????}

首先会调用ensureCapaciity方法，将集合长度加一的值传入

第一步就是判断是不是要创建初始容量的数组，从这里可以看到字段属性的初始容量到现在才闪亮登场，可能一开始大家都觉得会是在构造函数进行设置初始容量大小的数组，这里要注意了，是在添加方法调用的。

这里要注意一点就是这个modCount,这个属性会贯穿整个ArrayList,只要涉及到数据的改变就会出现它。

如果需要的容量大于当前数组的长度，那就真正进入扩容的方法grow

首先判断将容量扩大1.5倍能否满足所需容量大小，如果不满足

就判断是否比最大数组长度大，如果还比它大就进行进一步的比较

???private?static?int?hugeCapacity(int?minCapacity)?{
????????//如果小于0就抛出异常
????????if?(minCapacity?<?0)?//?overflow
????????????throw?new?OutOfMemoryError();
????????//如果大于数组最大容量就扩容IntegerD的最大长度，小于的话就扩容为最大数组长度
????????return?(minCapacity?>?MAX_ARRAY_SIZE)??
????????????????Integer.MAX_VALUE?:
????????????????MAX_ARRAY_SIZE;
????}

最后扩容的操作通过Arrays.copyof方法来执行

remove方法01 remove(int index)

????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;?//?clear?to?let?GC?do?its?work

????????return?oldValue;
????}

• 通过具体位置移除元素，首先就是先判断传入的位置是否越界；

• 然后同样的modCount++，标识在改变数据。

  
  

• 获取当前位置的元素值，用于返回

  
  

• 计算需要移动的数量

  
  

• 然后通过System.arraycopy完成数组的拷贝来移除元素，这个方法我在下面会单独介绍

  
  

• 将数组空出来的位置置空，方便垃圾回收器回收

  
  

02 remove(Object object)

??public?boolean?remove(Object?o)?{
????????if?(o?==?null)?{
????????????for?(int?index?=?0;?index?<?size;?index++)
????????????????if?(elementData[index]?==?null)?{
????????????????????fastRemove(index);
????????????????????return?true;
????????????????}
????????}?else?{
????????????for?(int?index?=?0;?index?<?size;?index++)
????????????????if?(o.equals(elementData[index]))?{
????????????????????fastRemove(index);
????????????????????return?true;
????????????????}
????????}
????????return?false;
????}

???private?void?fastRemove(int?index)?{
????????modCount++;
????????int?numMoved?=?size?-?index?-?1;
????????if?(numMoved?>?0)
????????????System.arraycopy(elementData,?index?+?1,?elementData,?index,
????????????????????numMoved);
????????elementData[--size]?=?null;?//?clear?to?let?GC?do?its?work
????}

传入具体值进行删除，大致分为两步，一步是for循环遍历找出与之匹配的元素索引位子，第二步就是根据索引位置进行删除。

• 从代码可知，先判断该元素是否为空，为空就遍历数组是否存在空的数据，找到后，调fastRemove方法传索引位置进行删除

• 如果不为空就for循环找到该元素，同样通过fastRemove方法进行删除

• fastRemove方法和上一个remove方法大致一样，唯一区别就是去掉了索引位置校验，因为是先for获取的索引的位置，索引不会越界，减少不必要的代码

  
  

System.arraycopy方法

??arraycopy(Object?src,??int??srcPos,
????????????????????????????????????????Object?dest,?int?destPos,
????????????????????????????????????????int?length);

这个方法在arrayList的增删改都有用到，Array.copyof底层也是用的这个方法，这个方法主要有四个参数

1. Object src：源数组

   
   

2. int srcPos:源数组开始截取的起始位置

   
   

3. Object dest:目标数组

   
   

4. destPos 目标数组起始位置

   
   

5. int length：需要复制的长度

   
   

这四个参数具体什么意思呢，举个例子就明白了，比如：

Object[]?arr={1,2,3,4,5,6};
???????????Object[]?newArr=new?Object[5];
???????????System.arraycopy(arr,1,newArr,0,4);

源数组arr,里面有6个元素，目标数组是个新数组，数组长度为5，

传参里的1就是从源数组第一个位置开始截取，放入目标数组，放入到目标数组第0个位置，截取长度为4，那么结果就是目标数组元素是2,3,4，5