ArrayList源码解读

r囧r小猫 2022-10-14 13:53 184阅读 0赞

## 1、概述 ##

ArrayList是Java集合中使用比较多的，继承AbstractList，实现List接口。内部维护一个**Object类型的数组****elementData.允许null的存在**。其中实现了 **List**<E>、**RandomAccess**、\`**Cloneable\`**、java.io.**Serializable**.

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70][]

需要深入了解它，便要从**成员变量**、**构造方法**、**主要方法**深入。

## 2、成员变量 ##

> private static final long serialVersionUID = 8683452581122892189L;
> 
> **// 无参构造后第一次添加数据时，初始化数组elementData的容量 10 **  
> **private static final int DEFAULT\_CAPACITY = 10**;** **
> 
> // **无参构造时，初始化数组elementData为空数组**  
> **private static final Object\[\] EMPTY\_ELEMENTDATA = \{\}**;    
> private static final Object\[\] DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA = \{\};
> 
> // **ArrayList内部维护的数组，用来存储数据**  
> **transient Object\[\] elementData**; 
> 
> // **实际元素个数**  
> **private int size**;    
> private static final int MAX\_ARRAY\_SIZE = Integer.MAX\_VALUE - 8;

上面标红是比较主要的属性，**size**是elementData中**实际有的元素个数**，这里需要区别**elementData**的length是集合容量，表示最多可以容纳多少个元素。

//初始化elementData的容量为10
    ArrayList list = new ArrayList(10);  
    //输出 0
    System.out.println(list.size());

其中还有一个属性也是比较重要的，不过不是它的，而是它的父类的属性。

protected transient int modCount = 0;

**modCount** 是ArrayList 继承自 AbstractList 的属性，它是用来**记录集合的尺寸被修改次数**的，**add**、**remove** **方法会导致 modCount +1** ，而set 方法不会，因为set 方法没有改变集合的尺寸。它的作用会在（fail-fast）快速-失败中体现。

## 3、构造方法 ##

初始化时提供了三个方法

>     public ArrayList()
>     public ArrayList(int initialCapacity)
>     public ArrayList(Collection<? extends E> c)

### 无参构造方法 ###

>     /**
>     * Constructs an empty list with an initial capacity of ten.
>      */
>     //DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个{}空数组
>      public ArrayList() {
>           this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
>     }

创建对象使用无参构造时，**初始elementData容量为0**，（**在jdk7是10**）如果**第一次添加数据**时，需要扩容，则**扩容elementData为10**，如果再次需要扩容（**添加元素超过10后**）则**扩容elementData为1.5倍**。

### 有参构造方法 ###

>     /**
>      * Constructs an empty list with the specified initial capacity.
>      */
>     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);
>         }
>     }

初始化容量大小为initialCapacity，如果**initialCapacity > 0**直接创建一个Object类型大小为initialCapacity的数组，**initialCapacity=0**时把EMPTY\_ELEMENTDATA赋值elementData，**initialCapacity < 0**时就抛出异常。

### 指定Collection的参数有参构造 ###

>     /**
>      * Constructs a list containing the elements of the specified
>      * collection, in the order they are returned by the collection's
>      * iterator.
>      */
>     public ArrayList(Collection<? extends E> c) {
>         elementData = c.toArray();
>         if ((size = elementData.length) != 0) {
>             // defend against c.toArray (incorrectly) not returning Object[]
>             // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
>             if (elementData.getClass() != Object[].class)
>                 elementData = Arrays.copyOf(elementData, size, Object[].class);
>         } else {
>             // replace with empty array.
>             this.elementData = EMPTY_ELEMENTDATA;
>         }
>     }

将**Collection转为数组并赋值给elementData，把elementData中元素个数赋值给size**。当 **size != 0** 时则在**判断elementData的class类型是否是Object\[\]**，不是就做转换。size = 0时，把EMPTY\_ELEMENTDATA赋值给elementData，就相当于new ArrayList()；

## 4、ArrayList扩容机制（重点） ##

使用**无参构造方法创建对象**后，在第一次添加的分析，以代码deburg演示扩容的过程：代码如下

>     ArrayList list  = new ArrayList();
>     // 第一次扩容
>     for (int i = 0; i < 10; i++) {
>        list.add(i);
>     }

由于使用deburg不好演示过程，再次就使用**processon画图**来演示过程。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1][]

注意：当扩容为**原来的1.5倍**，newCapacity - minCapacity <=0 并且 elementData不为空数组，minCapacity > 0 就直接返回minCapacity的值（**这个值是size+1的容量**）

## 5、主要方法 ##

*  ### add（）方法 ###

>     /**
>      * Appends the specified element to the end of this list.
>      */
>     public boolean add(E e) {
>         modCount++;
>         add(e, elementData, size);
>         return true;
>     }
> 
>     private void add(E e, Object[] elementData, int s) {
>         if (s == elementData.length)
>             elementData = grow();
>         elementData[s] = e;
>         size = s + 1;
>     }

在add()方法中清楚地看到**判断是否size（数组真实元素个数）和数组容量大小是否相等**，相等的话就扩容。**不相等**就直接添加到数组中，size++；在这个方法中可以看到**modCount这个变量是记录该数组修改的次数**。

说到grow扩容方法就看看它内部到底长什么样的.

*  ### grow（）方法 ###

>     private Object[] grow() {
>         return grow(size + 1);
>     }
> 
>     private Object[] grow(int minCapacity) {
>         return elementData = Arrays.copyOf(elementData,
>                                            newCapacity(minCapacity));
>     }

该方法首先把size+1作为参数传入grow的重载方法中，**这个是添加一个元素时的最小容量值**（**size+1**），在后面的newCapacity方法中很有可能就扩容值为size+1.单说也不算，不如再看看newCapacity方法内部到底是什么机密。

**Arrays.copyof(elementData,newCapacity(minCapacity)) 扩容并保存之前数组的数据**，不可以扩容了就不保存之前的数据对吧。

*  ### newCapacity（）方法 ###

>     private int newCapacity(int minCapacity) {
>         // overflow-conscious code
>         int oldCapacity = elementData.length;
>         int newCapacity = oldCapacity + (oldCapacity >> 1);
>         if (newCapacity - minCapacity <= 0) {
>             if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
>                 return Math.max(DEFAULT_CAPACITY, minCapacity);
>             if (minCapacity < 0) // overflow
>                 throw new OutOfMemoryError();
>             return minCapacity;
>         }
>         return (newCapacity - MAX_ARRAY_SIZE <= 0)
>             ? newCapacity
>             : hugeCapacity(minCapacity);
>     }

oldCapacity保存数组之前的容量，**minCapacity是size+1的值**，对**oldCapacity扩容为1.5倍**，和minCapacity比较大小，如果**newCapacity - minCapacity <=0**,在判断是否**为默认的空数组**，如果是就返回**扩容为10的值**，**如果也不为空数组和minCapacity > 0 就直接返回minCapacity的值**（**size+1**）如果**扩容后的newCapacity**值**小于**ArrayList的最大容量**MAX\_ARRAY\_SIZE**，就返回扩容为1.5倍的值。否则**大于****MAX\_ARRAY\_SIZE**就调用hugeCapacity(minCapacity)方法，该方法是咋样处理呢？看下面方法分析过程。

*  ### hugeCapacity（）方法 ###

>     private static int hugeCapacity(int minCapacity) {
>         if (minCapacity < 0) // overflow
>             throw new OutOfMemoryError();
>         return (minCapacity > MAX_ARRAY_SIZE)
>             ? Integer.MAX_VALUE
>             : MAX_ARRAY_SIZE;
>     }

注意到传入的参数是minCapacity（**size+1**）的值，**不是扩容为1.5倍的值**，就比如**minCapacity大于MAX\_ARRAY\_SIZE** 在newCapacity（）方法中**newCapity**就**更加大于****MAX\_ARRAY\_SIZE**，就调用hugeCapacity（）方法，再看hugeCapacity()方法，**返回Integer.MAX\_VALUE**的值.

## 6、ArrayList源码结论（重点） ##

*  ArrayList中维护了一个**Object类型的数组**elementData.  **transient Object\[\] elementData**，**transient** 表示瞬间、短暂的，**表示该属性不会被序列化**。
 *  当创建对象时，如果使用**无参构造方法**，则初始化elementData容量为0.（jdk7是10）
 *  当**添加元素**时，**先判断是否要扩容**（s == elementData.length），需要则调用grow（）等方法，否则直接添加元素
 *  如果使用无参构造方法创建对象，如果**第一次添加元素**，需要**扩容则扩容elementData为10**，需要**再次扩容就是原先的1.5倍**.
 *  如果使用**有参构造方法**，**初始化容量为Capacity**，容量为Capacity值大小.
 *  如果使用有参构造指定容量Capacity，如果**添加元素后需要在扩容**，则**直接扩容elementData为1.5倍**.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70]: /images/20221014/e4929682a58a4cbd83649c6089552139.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcyNTUxNw_size_16_color_FFFFFF_t_70 1]: /images/20221014/6e36c702ac0143c4a848b65ab61cd327.png