List之ArrayList源码实现-蒲公英云

一、引言

1.导语

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

2.要点

要点	说明
是否可以为空	无
是否有序	无
是否可以重复	无
是否线程安全	无

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

二、分析

1. 继承关系图

这里写图片描述

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后面的元素往后移一个位置的图形说明，更容易理解（网上随便找了一个，侵删）。

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的优缺点

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

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

2.ArrayList和Vector的不同

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

List 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();
    }
}