四.ArrayList底层源码实现

前言

ArrayList我们总是常用，但是其底层具体怎么实现呢？我们今天就来看看

一.例子

我们以一段代码来展开分析

/**
 * @author RickYinPeng
 * @ClassName Test_03_ArrayList
 * @Description
 * @date 2019/1/22/11:42
 */
public class Test_03_ArrayList {
    public static void main(String[] args) {
        ArrayList<String> list01 = new ArrayList<>();
        
        list01.add("01_aa");
        
        list01.add("02_bb");
        
        list01.add("03_cc");
        
        list01.add("04_cc");
        
        list01.add("05_cc");
        
        list01.add("06_cc");
        
        list01.add("07_cc");
        
        list01.add("08_cc");
        
        list01.add("09_cc");
        
        list01.add("10_cc");
        
        list01.add("11_cc");
    }
}

在分析之前我们先来看看ArrayList的构造方法

二.构造方法分析

源码

/**
     * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    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);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

这里有两个构造，一个是有参构造一个是无参构造

2.1我们先来看看有参构造

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

分析有参构造：

当我们通过有参构造来new一个ArrayList时，传入参数initialCapacity，这就是一个初始化的参数，解毒代码我们发现，当我们传入的参数>0时，就执行这么一段代码

1	this.elementData = new Object[initialCapacity];

那这个elementData是个什么呢?我们来看看

1	transient Object[] elementData;

这就是那个elementData，它是一个Object类型的数组,也就是说，我们的 ArrayList 是将数据保存在了这个 Object数组中的，底层是使用这个Object数组来实现

也就是说我们传入的数值initialCapacity如果 >0 那么ArrayList底层就会帮我们初始化一个initialCapacity大小的Object数组。如果传入的数值为0，那么就会走下面的代码

1	this.elementData = EMPTY_ELEMENTDATA;

我们来看看这个 EMPTY_ELEMENTDATA 是啥？

1	private static final Object[] EMPTY_ELEMENTDATA = {};

这就是一个空的Object数组，也就说如果我们传入的参数值为0，那么ArrayList底层就会帮我们实现一个空的Object数组。

2.2无参构造

1
2
3

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

这个比较简单，我们来看看 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个就ok了.

1	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA跟我们前面分析的EMPTY_ELEMENTDATA这个是一样的，都是一个空的数组，至于为什么人家用两个我就不知道了，我们继续下面的分析。

三.add方法分析

我们在第一个add方法处加上断点，然后一步一步分析

开始debug

跟进add方法内部

跟进add方法

源码

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

我们发现其中还有一个 ensureCapacityInternal(size + 1); 方法，此时它有一个参数size+1,这个size是什么呢？我们来看看

1	private int size;

就是这样一个变量，这里告诉你，这个size就是当前 ArrayList 的size大小(注意：这个size跟我们之前看到的那个elementData数组的长度可不一样，这个size就是我们能在程序外部看到的ArrayList集合的大小)，，因为此时是我们第一次添加元素，所以size为0。

所以这时 ensureCapacityInternal(size + 1) 的参数 size+1 = 1

这里解释一下为什么是size+1，因为咱们添加一个元素，是不是ArrayList的大小要加1，所以是size+1

跟进ensureCapacityInternal(size + 1)方法内部

源码

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

分析：

此时，在这个函数中，它先判断 elementData跟DEFAULTCAPACITY_EMPTY_ELEMENTDATA是不是同一个引用(==是判断地址的在对象中和)，而之前在分析无参构造时有这么一句代码

1	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

所以显然，这个判断成立，执行如下代码

1	minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

此时这个代码就是选出 DEFAULT_CAPACITY 和 minCapacity的最大值，而这个 minCapacity 就是我们之前传的 size+1 = 1，所以这个minCapacity是1

这个minCapacity从英文角度去理解，就是当前容器(ArrayList)的最小容量，就是我这个容器不能比这个容量再小，再小就装不下了，所以在这里选最大值

我们来看看 DEFAULT_CAPACITY 这个是个啥？

1	private static final int DEFAULT_CAPACITY = 10;

DEFAULT_CAPACITY的默认值是10,这里告诉大家，这个DEFAULT_CAPACITY是我们的ArrayList底层给我们初始化的大小，这个大小是初始化的谁呢，就是我们之前分析的那个Object的数组大小。

在这里说一下，我们的ArrayList底层是使用那个Object数组来存放数据的，所以ArrayList给这个数组得初始化一个大小，之前在构造中只是给它引用地址并未初始化大小。

注意：这里这个Object数组的长度，并不是我们ArrayList的长度，我们的ArrayList的长度，是那个size字段并不是它，这一点千万别搞混

所以这里执行完后，minCapacity就会变为10，因为是找最大值啊，10比1（size+1）大,接下来执行下面这段代码

1	ensureExplicitCapacity(minCapacity);

### 跟进ensureExplicitCapacity(minCapacity)方法内部

源码

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

这里这个modCount++;就不用管了，这个就是用来计数的，当你每次add的时候，我们来看下面的代码

1
2
3

// overflow-conscious code
if (minCapacity - elementData.length > 0)
    grow(minCapacity);

如果 minCapacity 减去elementData.length（就是那个Object数组的长度）>0，那么执行grow(minCapacity);函数。此时minCapacity为10（经过前面的选最大值后变为了10）

所以此时会进入grow方法

跟进grow(minCapacity);方法内部

源码

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

此时代码中有 oldCapacity ，这个代表的是原有的Object数组的长度，现在这个长度为0

newCapacity 代表的是新的Object数组的长度，就是扩容后的长度，通过 oldCapacity + (oldCapacity >> 1); 这句代码给它扩容，其实就是旧的长度加上旧的长度除以2之后的长度作为新的长度

此时 elementData.length; 为0，所以 oldCapacity为0，所以算出的newCapacity也为0

所以会走下面这句代码

1 2	if (newCapacity - minCapacity < 0) newCapacity = minCapacity;

就是说扩容后的长度还没有我默认的长度10大呢，所以就将默认长度10赋值给新的长度newCapacity。

接下来走了

1	elementData = Arrays.copyOf(elementData, newCapacity);

这段代码，这段代码我就不进去看了，就是构造一个newCapacity大小的数组，然后将Object数组中原有的内容复制到新的数组中然后返回给elementData，此时elementData已经跟那个DEFAULTCAPACITY_EMPTY_ELEMENTDATA已经不一样了，已经不是指向同一个地址了，因为这个elementData指向了新的地址，因为Arrays.copyOf(elementData, newCapacity);给它返回了一个新的数组

最后分析

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

最终跳回了这里，不过ensureCapacityInternal(size + 1);这个方法我们已经分析完毕，就是去判断我们添加的元素有没有超过内置Object的数组长度，如果超过，我们就去给它扩容，然后将原有的Object数组复制到新的扩容后的数组中。

所以此时elementData已经指向了那个扩容后的数组的地址了，然后执行elementData[size++] = e;将传入的参数添加到数组中

四.之后分析

在我们之后的九次add中，既不会再去扩容了，也就是说不会再走grow(minCapacity);方法了