List之ArrayList源码实现

雨点打透心脏的1/2处 2022-05-14 01:05 169阅读 0赞

## 一、引言 ##

### 1.导语 ###

*  集合是Java重要且非常基础的东西，因为任何数据必不可少的就是该数据是如何存储的，集合的作用就是以一定的方式组织、存储数据。所以说研究其底层源代码是一个程序员的必修课。

### 2.要点 ###

<table> 
 <thead> 
  <tr> 
   <th align="center">要点</th> 
   <th align="center">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">是否可以为空</td> 
   <td align="center">无</td> 
  </tr> 
  <tr> 
   <td align="center">是否有序</td> 
   <td align="center">无</td> 
  </tr> 
  <tr> 
   <td align="center">是否可以重复</td> 
   <td align="center">无</td> 
  </tr> 
  <tr> 
   <td align="center">是否线程安全</td> 
   <td align="center">无</td> 
  </tr> 
 </tbody> 
</table>

只要在学习集合源码的时候的时刻牢记这四点，就会时刻思路比较清晰，更便于我们去理解其设计思想和实现。

## 二、分析 ##

### 1. 继承关系图 ###

![这里写图片描述][70]

### 2. 字段 ###

```
        /**
         * Default initial capacity.  初始化容量大小为10
         */
        private static final int DEFAULT_CAPACITY = 10;
    
        /**
         * Shared empty array instance used for empty instances.
         * 空的数组
         */
        private static final Object[] EMPTY_ELEMENTDATA = {};
    
        /**
         * Shared empty array instance used for default sized empty instances. We
         * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
         * first element is added.
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
        // 当前数据对象存放地方，当前对象不参与序列化
        transient Object[] elementData; // non-private to simplify nested class access
    
        /**
         * The size of the ArrayList (the number of elements it contains).
         *  数组中的元素个数
         */
        private int size;
    ```

### 3. 构造函数 ###

#### 3.1 空参构造函数 ####

```
     public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
    ```
    >注意：此时ArrayList的size为空，但是elementData的length为1。第一次添加时，容量变成初始容量大小10.

#### 3.2 int参数构造函数 ####

```
    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);
        }
    }
    ```
    > 注意：此时ArrayList的size为空，但是elementData的length为1。第一次添加时，容量变成初始容量大小10.

#### 3.3 collection参数构造函数 ####

public ArrayList(Collection<? extends E> c) {
            // 指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排
            // 这里主要做了两步：1.把集合的元素copy到elementData中。2.更新size值。
            elementData = c.toArray();
            if ((size = elementData.length) != 0) {
                // c.toArray might (incorrectly) not return Object[] (see 6260652)
                if (elementData.getClass() != Object[].class)
                    elementData = Arrays.copyOf(elementData, size, Object[].class);
            } else {
                // replace with empty array.
                this.elementData = EMPTY_ELEMENTDATA;
            }
        }

### 4. add方法 ###

/** * Appends the specified element to the end of this list. * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */
        public boolean add(E e) {
            // 扩容操作，稍后讲解
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            // 将元素添加到数组尾部
            elementData[size++] = e;
            return true;
        }

### 5.ensureCapacityInternal方法 ###

/** * Increases the capacity of this <tt>ArrayList</tt> instance, if 增加arrayList的容量 * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. 确保他能装下最新插入的元素 * * @param minCapacity the desired minimum capacity */
        public void ensureCapacity(int minCapacity) {
            // 如果elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则扩容容量为默认值（10），否则就为0
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
    
            if (minCapacity > minExpand) {
                ensureExplicitCapacity(minCapacity);
            }
        }
    
        // 数组容量检测，不够时则进行扩容操作
        private void ensureCapacityInternal(int minCapacity) {
            // 如果elementData为默认的空数组，则容量扩容为默认容量和参数容量的较大值
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            // 进行扩容操作
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) {
            modCount++;
    
            // overflow-conscious code
            // 如果当前指定的最小容量比缓冲区的长度大，则进行扩容，并且扩容的长度为指定的minCapacityd；
            // 否则不进行扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        /** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit * 具体最大为什么是Integer.MAX_VALUE - 8，这上面的英文说的很清楚。 * 大概的意思：jvm中有一些头元素会存在数组中，所以预留了8个空的，防止oom. */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组的最大值：Integer的最大值-8
    
        /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */
        private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            // 新容量 = 原来容量 + （原来容量）/2
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 如果新容量比指定的容量小，则把新容量赋值为新容量。
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            // 如果新容量比最大的数组大，则进行大容量扩容
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            // 创建新容量长度的数组，并把原来的元素赋值到新数组中，实现扩容 + 复制 元素的效果
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
        // 大容量分配
        private static int hugeCapacity(int minCapacity) {
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

> 思考：  
> 1.判断是否需要扩容，如果需要，计算需要扩容的最小容量  
> 2.如果确定扩容，就执行grow(int minCapacity)，minCapacity为最少需要的容量  
> 3.第一次扩容是的容量大小是原来的1.5倍  
> 4如果第一次 扩容后容量还是小于minCapacity,那就扩容为minCapacity  
> 5.最后，如果minCapacity大于最大容量，则就扩容为最大容量

### 6.get(int)方法 ###

public E get(int index) {
            // 先进行越界检查
            rangeCheck(index);
            // 通过检查则返回结果数据，否则就抛出异常。
            return elementData(index);
        }
    
        // 越界检查的代码很简单，就是判断想要的索引有没有超过当前数组的最大容量
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

### 7.add(int, E)方法 ###

public void add(int index, E element) {
            // 插入数组位置检查
            rangeCheckForAdd(index);
    
            // 确保容量，如果需要扩容的话则自动扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index); // 将index后面的元素往后移一个位置
            elementData[index] = element; // 在想要插入的位置插入元素
            size++; // 元素大小加1
        }
    
      // 针对插入数组的位置，进行越界检查，不通过抛出异常
      // 必须在0-最后一个元素中间的位置插入，，否则就报错
      // 因为数组是连续的空间，不存在断开的情况
      private void rangeCheckForAdd(int index) {
            if (index > size || index < 0)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

*  对将index后面的元素往后移一个位置的图形说明，更容易理解（网上随便找了一个，侵删）。  
    ![这里写图片描述][70 1]

### 8.remove(int index) ###

public E remove(int index) {
           // 索引越界检查
            rangeCheck(index);
    
            modCount++;
            // 得到删除位置元素值
            E oldValue = elementData(index);
    
            // 计算删除元素后，元素右边需要向左移动的元素个数
            int numMoved = size - index - 1;
            if (numMoved > 0)
                // 进行移动操作，图形过程大致类似于上面的add(int, E)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            // 元素大小减1，并且将最后一个置为null.
            // 置为null的原因，就是让gc起作用，所以需要显示置为null
            elementData[--size] = null; // clear to let GC do its work
    
            // 返回删除的元素值
            return oldValue;
        }

### 9.remove(Object o) ###

public boolean remove(Object o) {
            // 如果删除元素为null,则循环找到第一个null,并进行删除
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        // 根据下标删除
                        fastRemove(index);
                        return true;
                    }
            } else {
            // 否则就找到数组中和o相等的元素，返回下标进行删除
                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);
            // 元素大小减1，并且将最后一个置为null. 原因同上。
            elementData[--size] = null; // clear to let GC do its work
        }

### 10.set(int index, E element) ###

// 这个很简单，看下代码基本上都能理解
      // 作用：替换指定索引的元素
      public E set(int index, E element) {
            // 索引越界检查
            rangeCheck(index);
    
            E oldValue = elementData(index);
            elementData[index] = element;
            return oldValue;
        }

## 三、结尾 ##

### 1.ArrayList的优缺点 ###

<table> 
 <thead> 
  <tr> 
   <th align="center">要点</th> 
   <th align="center">说明</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">优点1</td> 
   <td align="center">ArrayList底层以数组实现，是一种随机访问模式，再加上它实现了RandomAccess接口，因此查找也就是get的时候非常快</td> 
  </tr> 
  <tr> 
   <td align="center">优点2</td> 
   <td align="center">ArrayList在顺序添加一个元素的时候非常方便，只是往数组里面添加了一个元素而已</td> 
  </tr> 
  <tr> 
   <td align="center">缺点1</td> 
   <td align="center">删除元素时，涉及到元素复制，如果要复制的元素很多，那么就会比较耗费性能</td> 
  </tr> 
  <tr> 
   <td align="center">缺点2</td> 
   <td align="center">插入元素时，涉及到元素复制，如果要复制的元素很多，那么就会比较耗费性能</td> 
  </tr> 
 </tbody> 
</table>

**ArrayList比较适合顺序添加、随机访问的场景**

### 2.ArrayList和Vector的不同 ###

*  ArrayList是线程非安全的，Vector则是线程安全的。Vector中90%的方法和ArrayList的是一样的。
 *  Vector可以指定增长因子，而ArrayList不行，而且两者默认扩容的大小也是不一样的，一个1.5倍；一个是2倍而且还可以指定。
 *  针对第一点中的缺点，jdk也给出了解决方法：

List<String> synchronizedList = Collections.synchronizedList(list);
    // 此时list则是一个线程安全的集合

### 3.为什么ArrayList的elementData是用transient修饰的 ###

*  说明：ArrayList实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化
 *  理解：序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此ArrayList中重写了writeObject方法。

private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException{
            // Write out element count, and any hidden stuff
            int expectedModCount = modCount;
            s.defaultWriteObject();
    
            // Write out size as capacity for behavioural compatibility with clone()
            s.writeInt(size);
    
            // Write out all elements in the proper order.
            for (int i=0; i<size; i++) {
                s.writeObject(elementData[i]);
            }
    
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }

*  优点：这样做既提高了序列化的效率，减少了无意义的序列化；而且还减少了序列化后文件大小。

### 4.版本说明 ###

*  这里的源码是JDK8版本，不同版本可能会有所差异，但是基本原理都是一样的。

### 5.回顾和思考 ###

*  再次思考学习集合源码的四个目标和上面的具体的内容，是不是有一种恍然大悟的感觉！！！

[70]: /images/20220514/c23f25c84ea14947be8c673a05809eb3.png
[70 1]: /images/20220514/ad9ee2bda4b843399c8b7c065353fb11.png