ArrayList源码解析之add方法

ArrayList是基于数组实现的，是一个动态数组，容量能自动增长。其扩容机制是在调用add()或者addAll()方法时发生的。

一、add(E e) 方法

public boolean add(E e) {
	// 判断是否需要扩容
	ensureCapacityInternal(size + 1);
	// 将新元素追加到相应的数组中
	elementData[size++] = e;
	return true;
}

ensureCapacityInternal(int minCapacity)方法判断是否需要扩容

// minCapacity = size + 1
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;
}

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

	// 增加元素所需空间不足，则需扩容
	if (minCapacity - elementData.length > 0)
		// 真正的扩容方法
		grow(minCapacity);
}

在grow()方法中，可以看出每次扩容后的长度是当前数组长度的1.5倍，其实质是将原有数组内容复制到一个长度为newCapacity的新数组中。

// 数组默认的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
	// 旧数组的长度
	int oldCapacity = elementData.length;
	// 扩容为原来的1.5倍
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	// 判断新的数组容量是否达到需求
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	// 判断新容量是否溢出
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
	// 调用Arrays.copyOf()方法，将elementData数组复制到一个新数组
	elementData = Arrays.copyOf(elementData, newCapacity);
}

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

二、add(int index, E element)方法

// 将元素添加到指定位置，扩容机制与add(E e)方法一致
public void add(int index, E element) {
	// 判断index是否越界
       rangeCheckForAdd(index);

       // 是否扩容
       ensureCapacityInternal(size + 1);  // Increments modCount!!
      	/*
      	* System.arraycopy()是比较重要的一个步骤，
      	* 其实质是将elementData数组中index位置（包含index）以后的数据全部向后移动一个位置，
      	* 从而用 elementData[index] = element ，将index位置元素替换为待添加元素。
      	*/
       System.arraycopy(elementData, index, elementData, index + 1,
                        size - index);
       elementData[index] = element;
       size++;
}

看看rangeCheckForAdd(index)方法，如果index越界，抛出IndexOutOfBoundsException异常。

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

看看System.arraycopy()的源码：

/**
 * 
 * @param src       源数组
 * @param srcPos	源数组开始位置
 * @param dest 		目标数组
 * @param destPos	目标数据开始位置
 * @param length	复制数据的长度
 */
public static native void arraycopy(Object src,  int  srcPos,
                                       Object dest, int destPos,
                                       int length);

三、addAll()方法

addAll()有两个重载方法，扩容机制与add()方法一致。

// 将指定集合中的元素添加到集合中
public boolean addAll(Collection<? extends E> c) {
    // 转数组
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 将c中所有元素追加到集合尾部
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
	
// 将指定集合中的元素添加到集合中的指定位置
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    // 需要移动元素的个数
    int numMoved = size - index;
    // 先将待添加数据所需空间空出，然后将指定集合数据从指定位置开始添加
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}