ArrayList里面的空间自动扩充

November 7, 2014

我们知道在使用ArrayList时，我们无需关心他的大小，只需要往里放置对象即可，那么它是如何做的空间自动扩充的呢？首先，我们在构造函数中可以传入一个int值，这个值表示的就是初始的容量，如果没有传这个值，那么默认的容量是0。

/**
 * The elements in this list, followed by nulls.
 */
transient Object[] array;
/**
 * Constructs a new instance of {@code ArrayList} with the specified
 * initial capacity.
 *
 * @param capacity
 *            the initial capacity of this {@code ArrayList}.
 */
public ArrayList(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity < 0: " + capacity);
    }
    array = (capacity == 0 ? EmptyArray.OBJECT : new Object[capacity]);
}

/**
 * Constructs a new {@code ArrayList} instance with zero initial capacity.
 */
public ArrayList() {
    array = EmptyArray.OBJECT;
}

通过上面的代码我们看到如果capacity是0的话，和不传int参数的作用是一样的，如果int值是大于0的那么,我们保存对象用的数组就是这个确切的值。

那么如果说我们往里存入对象时，空间不够用了，会发生什么呢？

/**
 * Adds the specified object at the end of this {@code ArrayList}.
 *
 * @param object
 *            the object to add.
 * @return always true
 */
@Override public boolean add(E object) {
    Object[] a = array;
    int s = size;
    if (s == a.length) {
        Object[] newArray = new Object[s +
                (s < (MIN_CAPACITY_INCREMENT / 2) ?
                 MIN_CAPACITY_INCREMENT : s >> 1)];
        System.arraycopy(a, 0, newArray, 0, s);
        array = a = newArray;
    }
    a[s] = object;
    size = s + 1;
    modCount++;
    return true;
}

这里我们看到了如果说size 和数组的长度一样了，也就是说数组满了，那么会重新new出一个数组，这个数组大小是s + (s < (MIN_CAPACITY_INCREMENT / 2) ? MIN_CAPACITY_INCREMENT : s >> 1)，而这个MIN_CAPACITY_INCREMENT常量的大小是12:

/**
 * The minimum amount by which the capacity of an ArrayList will increase.
 * This tuning parameter controls a time-space tradeoff（时间-空间权衡的方法）. This value (12)
 * gives empirically good results（这个12是经验上得出来比较好的初始值） and is arguably consistent with the
 * RI's specified default initial capacity of 10: instead of 10, we start
 * with 0 (sans allocation) and jump to 12.
 */
private static final int MIN_CAPACITY_INCREMENT = 12;

因此如果是刚开始size小于6的话，那么这个新的数组长度就会变成12，如果size已经比大于货等于12了，那么这个新的数组就是原来的两倍大小。

在addAll方法中还有另一种逻辑，但是和这个逻辑基本是一致的，有兴趣的可以去看看java源码。