ArrayList源码分析

本文基于JDK1.8源码剖析来剖析，ArrayList顾名思义，数组的结构来表明一个List，先上一张图抛砖引玉：

这张图表明的便是恳求了容量capacity为10的array buffer，但是有用容量size为1的情况。 开始剖析源码：

1. 特点及结构办法

先来看他的几个特点和结构办法：

    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size;
    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);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList(Collection<? extends E> c) {
        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;
        }
    }

相信咱们看完这个代码的第一个疑问肯定是为什么要搞两个空Object数组出来。

1. EMPTY_ELEMENTDATA
2. DEFAULTCAPACITY_EMPTY_ELEMENTDATA

这两个都是空数组，其实要搞清楚这个问题看一下他们别离在什么地方运用就好了。

1. 首先是EMPTY_ELEMENTDATA，他一切被运用的地方都是在初始化的时分size为0的时分被赋值给elementData，所以它的效果便是在size为0的时分不用去创建一个空数组了，而是提前创建好了放在那儿，便利被运用。
2. 再看DEFAULTCAPACITY_EMPTY_ELEMENTDATA，他被运用的场景是在默许结构办法的时分被赋值给elementData，然后在add扩容的时分，被用来做判别。也便是说它的含义是告诉后边的代码当前是空的，需求被扩容成默许巨细DEFAULT_CAPACITY = 10。

其实深一点说它的效果是做一个时刻上的拖延处理，咱们每次new ArrayList()的时分其实这个时分并没有给咱们恳求内存，只要在add的时分才会恳求10个内存空间，它的含义在这儿。

那咱们来看结构办法，三个结构办法，其实没什么好说的，看完上面咱们的一个解说其实咱们应该好了解了。

这儿要留意的是假如咱们调用了一个new ArrayList(20)，是直接恳求了一个20的数组，而不是从0开始扩容，即使是new了一个ArrayList(Integer.MAX_VALUE)也是这样，并没有触发扩容，后边add的时分才会扩容。

好的，那既然是调集类，那咱们别离来看它的增修改查办法~

2. add

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

四个add办法，分为两种用法：

1. add单个
2. addAll

咱们发现这些办法都调用到了一个叫做ensureCapacityInternal的办法，下面看它的代码：

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
//初始化成DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时分容量赋值成DEFAULT_CAPACITY
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0) //①
            grow(minCapacity);
    }
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
     private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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;
    }

首先先回忆一下上面咱们说的add的时分关于赋值成DEFAULTCAPACITY_EMPTY_ELEMENTDATA用来做拖延恳求内存的常识，在calculateCapacity办法里边.

2.1. 扩容

下面就到了ArrayList的核心办法grow扩容。
咱们先从最不鸿沟的情况看起，先了解一个最简略的扩容机制，capacity容量和size都为10的时分再add一个是怎样触发grow的，grow办法里边真实起效果的便是下面两句了。

// 15 = 10 + (10 >> 1) = 10 + 5
int newCapacity = oldCapacity + (oldCapacity >> 1);
//复制数据
elementData = Arrays.copyOf(elementData, newCapacity);

看起来也不难，那其实写东西理清了思路逻辑就那么一点，其实真实难处理的和容易出问题的都在鸿沟上。咱们看到在grow办法里边有一些if来处理鸿沟条件，我在上面的if后边标了①②③④的注释，咱们别离看一下能触发这些if的条件。
①. 由于每次都会调用查看是否需求扩容，那判别只要大于elementData.length的时分才需求扩容。
②. 这句是说oldCapacity扩容1.5倍之后假如比需求的minCapacity还要小，那就直接用minCapacity作为newCapacity来做扩容。这个其实很好了解，在addAll的时分假如需求add的调集很大的时分就会呈现这种情况。
比方：

List src = new ArrayList(10);
List tar = new ArrayList(10);
src.addAll(tar);

那很明显oldCapacity = 10; 扩容1.5后newCapacity = 15，而minCapacity = 20。 ③④，这俩其实是一同的。假如扩容后的newCapacity大于MAX_ARRAY_SIZE，也便是大于Integer.MAX_VALUE - 8或者爽性大于Integer.MAX_VALUE最大值，这个时分就直接赋值为Integer.MAX_VALUE。
这个时分其实咱们还留意到hugeCapacity这儿有这么一个判别：

if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();

那什么时分会小于零呢？咱们知道java里边int是没有所谓的unsigned的概念的，也便是无符号的概念。这儿可以看一下我写过的一篇文章一次与或非操作实战，也便是说超过了Integer.MAX_VALUE就变成负数了。所以假如恳求的超过最大值就直接抛OOM了。

那其实看完扩容，add就很简略了，不解说了，直接上图。

2.2. add(E e)

add单个元素：

2.3. add(int index, E element)

2.4. Collection<? extends E> c

这儿需求留意的是addAll的时分，不管被add的List的size是多大的，只会扩一次容。一次性到需求的capacity。

3. get set

那其实getset就简略的很了，没几句代码，由于是ArrayList，优势便是在可以以O(1)的时刻复杂度找到需求的方位，很简略就不解说了。

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
     public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

4. remove

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;
    }
    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
    }

那看代码来说，remove(int index)跟remove(Object o)肯定是功率不一样的，一个O(1)一个是O(n)。这是remove单个的时分，便是找到需求移除的index的办法不一样，那找到之后的工作量都是由System.arraycopy来完成的，附图：

那removeAll的代码如下

     public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }
     public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);
    }
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

我也是在看的时分才发现有retainAll这么个办法，跟removeAll的区别只要一个标志位。那含义便是彻底相反的，咱们知道removeAll是把方针调集全部移除去，retainAll刚好相反，是只保存方针调集里的元素. 就比方说有listA: [0, 1, 2, 3, 4]，同时有listB: [1, 2, 3]。

1. listA.removeAll(listB) => listA: [0, 4]
2. listA.retainAll(listB) => listA: [1, 2, 3]

那咱们来看removeAll，complement为false，关键办法batchRemove ，这儿面有两个变量r和w，咱们还是拿listA.removeAll(listB)来举比如：

r会循环0 ... 4:

1. 第一遍循环，r= 0且w = 0 ，这时listB包括elementData[0]=0不建立，所以把elementData[0]赋值给elementData[w=0]，然后w++之后w = 1
2. 第二遍循环，r= 1且w = 1，这时listB包括elementData[1] = 1建立，不做赋值
3. 第三遍循环，r= 2且w = 1，这时listB包括elementData[2] = 2建立，不做赋值
4. 第四遍循环，r= 3且w = 1，这时listB包括elementData[3] = 3建立，不做赋值
5. 第五遍循环，r= 4且w = 1，这时listB包括elementData[4] = 4不建立，elementData[4]赋值给elementData[w=1]，然后w++之后w = 2

循环完毕。这时分removeAll操作就完成了。retainAll的操作便是刚好相反，下面附一张图，更直观：