ArrayList扩容机制源码分析

1、先看一下ArrayList的构造方法

1-1：空参构造方法:

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

可以看到默认的空参构造方法是赋值了一个空数组

1-2：传入默认大小/容量，构造方法

 private static final Object[] EMPTY_ELEMENTDATA = {};

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

• 当你传入的容量大于等于0，就会给你new出相对应大小的数组。不然就会抛出非法参数的异常
• 因为扩容是需要浪费时间的性能的。所以如果你开始就知道容量大小，应当直接选择这种构造方法

1-2：传入一个Collection的集合，构造方法

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

把你传入的其它类型的集合，转成ArrayList集合

2、看一下ArrayList是如何进入扩容的

看一下add()方法

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

可以看到首先就是调用了这个 ensureCapacityInternal，因为你添加一个元素，可能会出现数组越界，那这个方法就是预防这个问题的。

我们再看一下这个 ensureCapacityInternal

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

这个里面先调用了calculateCapacity，后调用 ensureExplicitCapacity，我们依次来看

private static final int DEFAULT_CAPACITY = 10;

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

• 这个方法就是判断，目前这个集合/数组是否为空，因为我们看到使用空参构造出来的集合/数据是空的。如果是空的话。就取默认大小和当前大小的最大值。
• 可以看到默认容量大小是 10

上面看了calculateCapacity，我们再来看下 ensureExplicitCapacity

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0){
    	grow(minCapacity);
    }        
}

这个 minCapacity 就是我们现在需要的容量大小，如果它大于当前的数组大小。那么就触发了 grow() 方法，也就是扩容方法。

3、现在我们可以来具体看一下这个 grow() 扩容方法了

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

简单解释一下 >> 右位移，你也可以直接记住是扩大了50%
    这里直接把oldCapacity当作 999
    1、把 999 转化成二进制 1111100111
    2、从右边去掉一位变成 111110011 就是最后的结果，转成十进制是 499
    3、你可以理解成 >> 后面接几，就移除几位

• 通过上面的解释我们知道了新的容量大小是之前的1.5倍。
• 如果当前所需容量大小，还是大于新的容量大小。 就直接让当前容量大小作为扩容后的大小
• 如果新的容量要是大于默认最大值，就需要调用一下hugeCapacity方法，取Integer和当前容量的最大值

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

4、总结

• 当我们向集合里面添加一个元素的时候，就会去判断当前集合大小是否满足。
• 因为使用无参构造方法创建的ArrayList，默认是空数组。所以需要先判断数组是否为空，如果为空的话，就取当前长度和默认长度的最大值，默认长度是10。
• 然后判断当前所需空间是否大于数组的空间，如果不大于就不需要进行扩容了。如果大于则需要进去扩容。
• 新的长度大小，是在旧的基础上加上旧长度的0.5倍。使用向右位移一位计算出来的。
• 如果新计算的长度还是小于当前需要的长度，就直接让新的长度等于当前所需长度。
• 最后得出的新长度要和最大的数组长度对比。如果大于最大长度。就需要让新长度和最大长度比较，大于最大长度，就让新长度等于Integer的最大值，否则就让新长度等于数组最大长度。
• 最后一步，得出了新的长度，调用Arrays.copyOf，生成新的数组。