ArrayList和Vector扩容机制源码（JDK8）探索

ArrayList和Vector都是实现了List接口的集合类，元素有序可重复，支持索引；
其中ArrayList是线程不安全的，Vector是线程安全的。两者都通过Object类型的数组elementData存放元素；其扩容机制如下：
先说结论：

ArrayList
- 无参构造时，初始elementData为空，第一次添加元素时扩容为10，以后按1.5倍扩容
- 有参构造时，初始为传入参数大小，以后按1.5倍扩容
Vector
- 无参构造时，初始为10，按2倍扩容
- 有参构造时，初始为传入参数大小，按2倍扩容

下面从JDK8的源码分析一下：

ArrayList扩容机制

首先是ArrayList无参构造时，debug用的代码如下：

  ArrayList arrayList = new ArrayList();
        for (int i = 0; i < 20; i++) {
            arrayList.add(i);
        }

无参new一个ArrayList对象时，会调用无参构造器：

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

而在ArrayList里DEFAULTCAPACITY_EMPTY_ELEMENTDATA的定义为

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

所以初始化后，elementData是空的：

接下来开始往里面添加元素：

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

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
//这里判断我们这个对象的数组是否是初始化的那个数组，如果是，则返回DEFAULT_CAPACITY和minCapacity中的最大值，因为这是第一次添加元素，所以就是初始化的那个数组，所以返回两者的最大值，这里DEFAULT_CAPACITY=10（定义的final常量），minCapacity=1（传入的数值），所以返回10.
private static final int DEFAULT_CAPACITY = 10;

private void ensureExplicitCapacity(int minCapacity) {//传入10
        modCount++;

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

private void grow(int minCapacity) {//传入10
        // overflow-conscious code
        int oldCapacity = elementData.length;//=0
        int newCapacity = oldCapacity + (oldCapacity >> 1);//位运算，相当于/2,所以是1.5倍的oldCapacity，这里仍旧等于0
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;//=10
        if (newCapacity - MAX_ARRAY_SIZE > 0)//MAX_ARRAY_SIZE是一个很大的数，先不用管
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);//扩容为10
    }

然后就是添加数据，可以看到，elementData已经扩容为10：

当添加到第十一个元素时，流程基本一致，grow函数那里流程有点不同：

private void grow(int minCapacity) {//传入11
        // overflow-conscious code
        int oldCapacity = elementData.length;//=10
        int newCapacity = oldCapacity + (oldCapacity >> 1);//=15
        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);//扩容为15
    }

可以看到，elementData已经扩容为15：

ArrayList有参构造时，debug用的代码如下：

ArrayList arrayList = new ArrayList(8);
        for (int i = 0; i < 20; i++) {
            arrayList.add(i);
        }

调用有参构造器：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];//new一个Object类型的数组，大小为参数大小
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

初始化的容量为8：

然后后续添加过程的按1.5倍扩容，过程和上面的一致

Vector扩容机制

首先是Vector无参构造时，debug用的代码如下：

Vector vector = new Vector();
        for (int i = 0; i < 20; i++) {
            vector.add(i);
        }

调用无参构造器：（可以看到，无参构造器直接调用了有参构造器，并传入了一个10）
```
public Vector() {
        this(10);
   }
```

调用有参构造器：（这里又调用了两个参数的有参构造器，另一个参数是0）

public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }

public Vector(int initialCapacity, int capacityIncrement) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];//new一个第一个参数大小的Object类型的数组，这里是10
        this.capacityIncrement = capacityIncrement;//=0
    }

可以看到，elementData容量已经初始化为10：

接下来往里面添加第一个元素：

public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

private void ensureCapacityHelper(int minCapacity) {//传入1，代表需要一个空间
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);//如果需要的空间大于数组的大小，则需要扩容，这里暂时不需要
    }

所以不需要扩容，直接就往里面添加第一个元素了：

当添加到第11个元素时，需要扩容了，进入grow()函数：

private void grow(int minCapacity) {//传入11
        // overflow-conscious code
        int oldCapacity = elementData.length;//=10
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
    //capacityIncrement在构造器那里已经初始化为0，所以这个返回的时oldCapacity+oldCapacity，即2倍的elementData.length
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);//数组扩容为2倍大小
    }