转载

ArrayList动态扩容机制

我们通过一个具体的例子看一下ArrayList的扩容效果

先看一下ArrayList的初始容量

ArrayList<Integer> array = new ArrayList<>();
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：0
大小：0

getCapacity（）方法是用来获取集合容量的，ArrayList通过一个elementData对象数组储存数据，也就是说ArrayList的容量就是该数组的长度。所以我们只要得到了elementData数组就可以知道ArrayList的实际容量。

由于elementData是私有的无法直接得到，但是我们可以通过反射的方式获取。

代码如下：

public static Integer getCapacity(ArrayList list) {
    Integer length = null;
    Class c = ((Object)list).getClass();
    Field f;
    try {
        f = c.getDeclaredField("elementData");
        f.setAccessible(true);
        
        Object[] o = (Object[]) f.get(list);
        length = o.length;
    } catch (NoSuchFieldException ex) {
        Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
    } catch (SecurityException ex) {
        Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
    } catch (IllegalArgumentException ex) {
        Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
    } catch (IllegalAccessException ex) {
        Logger.getLogger(CollectionDemo.class.getName()).log(Level.SEVERE, null, ex);
    }
    return length;
}

接下来，我们向ArrayList中添加一个元素

ArrayList<Integer> array = new ArrayList<>();
array.add(1);
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：10
大小：1

向ArrayList中添加11个元素

ArrayList<Integer> array = new ArrayList<>();
for (int i = 0; i < 11; i ++) {
    array.add(i);
}
Integer capacity = getCapacity(array);
int size = array.size();
System.out.println("容量："+capacity);
System.out.println("大小："+size);
容量：15
大小：11

我们发现，当向array中添加11个元素之后，array的容量扩大到原来的1.5倍。

Why does it expansion 1.5 times?

具体为什么，下面我们看一下源码：

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

add方法是通过在array的尾部追加元素的方法，添加数据的。其中，调用ensureCapacityInternal方法用来判断是否需要扩容.

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++; 
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

参数传的是当前需要的最小容量，方法首先确认当前ArrayList实例是否为空，如果为空则比较所需容量和默认容量，取其较大值作为所需最小容量值。然后执行ensureExplicitCapacity进一步确定容量，以及是否需要扩容。当所需最小容量大于当前elementData数组长度时，要进行扩容操作。

modCount是fail fast机制，不了解也不影响，如果想了解可以看这里 ,如果minCapacity的值大于添加数据之前的大小，就调用 grow 方法，进行扩容，否则什么也不做。

发生扩容的条件

根据传入的最小需要容量minCapacity来和数组的容量长度对比，若minCapactity大于或等于数组容量，则需要进行扩容。(如果实际存储数组是空数组，则最小需要容量就是默认容量)

以上只是真实容量和所需容量的比较，其目的是计算出array的最终容量。真正实现扩容的方法是grow方法。下面具体来了解扩容机制的增长规则

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

这里传过来的minCapacity的值是array的size+1 添加一个元素，首先计算当前的array所需最小的容量大小，判断是否需要扩容等。当需要扩容时：