ArrayList 源码分析

简介

在添加大量元素前，应用程序可以使用 ensureCapacity 操作来增加容量，可以减少递增式再分配的数量
ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
线程不安全，而 vector 线程安全(几乎所有方法都加上了 synchronized 修饰，因此速度相对慢)
可以添加 null 值(但不建议)

扩容机制

Java 的 ArrayList 是一个基于动态数组实现的列表，它允许我们动态地增加和减少元素。ArrayList 的核心特性之一是它的自动扩容机制，这允许它在添加元素时自动增长内部数组的大小。以下是 ArrayList 扩容机制的关键点：

初始容量：
- 当创建一个新的 ArrayList 实例时，如果没有指定初始容量，它将使用默认的初始容量（默认为 10）。如果指定了初始容量，ArrayList 将使用该值作为内部数组的大小。
容量增长策略：
- 当添加元素时，如果内部数组没有足够的空间来容纳更多的元素，ArrayList 将进行扩容操作。扩容操作涉及到创建一个新的更大的数组，并将旧数组中的所有元素复制到新数组中。
扩容计算：
- 在 ArrayList 中，扩容是通过 grow() 方法实现的。当需要扩容时，grow() 方法会被调用，它将当前数组的容量增加一半（oldCapacity + (oldCapacity >> 1)）。这意味着新容量是旧容量的 1.5 倍。
最大数组大小：
- ArrayList 有一个最大数组大小的限制，定义为 MAX_ARRAY_SIZE，它是 Integer.MAX_VALUE - 8。这是为了防止 int 类型溢出，以及避免在创建超大数组时出现 OutOfMemoryError。
特殊情况下的容量调整：
- 如果计算出的新容量超过了 MAX_ARRAY_SIZE，ArrayList 会调用 hugeCapacity() 方法来处理这种情况，它会返回 Integer.MAX_VALUE 或 MAX_ARRAY_SIZE，具体取决于请求的最小容量。
复制旧数组：
- 在新容量计算出来之后，ArrayList 使用 Arrays.copyOf() 方法来创建一个新的数组，并复制旧数组中的所有元素到新数组中。
性能考虑：
- 扩容操作是 ArrayList 中成本较高的操作，因为它涉及到数组的复制。因此，尽管每次添加操作的平均时间复杂度是 O(1)（即“摊还常数时间”），但在实际应用中，如果频繁地进行扩容，性能可能会受到影响。
预分配容量：
- 可以通过 ensureCapacity() 方法提前增加 ArrayList 的容量，以减少在添加大量元素时的扩容操作次数。

总结来说，ArrayList 的扩容机制通过在需要时自动增加内部数组的大小来保证列表可以动态地增长。这种机制使得 ArrayList 在大多数情况下都非常有用，但在元素数量频繁变化的情况下，可能需要考虑预分配容量或者使用其他数据结构以优化性能。

如是只是创建了一个无参构造对象，则初始化赋值的是一个空数组，当加入元素之后才会扩容到默认的 10.(在 JDK 1.6 则是无参构造就扩容到 10)

/**
 * ArrayList扩容的核心方法。
 */
private void grow(int minCapacity) {
	// overflow-conscious code
	int oldCapacity = elementData.length;
	int newCapacity = oldCapacity + (oldCapacity >> 1);
	//这个判断主要是对于刚开始加入元素的时候，方便直接到minCapacity(10)
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
	//若很大，快要溢出int了，则切换到hugeCapacity
	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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 对minCapacity和MAX_ARRAY_SIZE进行比较
    // 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    // 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

/**
* Arrays.copyOf()方法
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
	@SuppressWarnings("unchecked")
	T[] copy = ((Object)newType == (Object)Object[].class)
		? (T[]) new Object[newLength]
		: (T[]) Array.newInstance(newType.getComponentType(), newLength);
	// 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
	System.arraycopy(original, 0, copy, 0,
					 Math.min(original.length, newLength));
	return copy;
}


/**
*   System.arraycopy复制数组
* @param src 源数组
* @param srcPos 源数组中的起始位置
* @param dest 目标数组
* @param destPos 目标数组中的起始位置
* @param length 要复制的数组元素的数量
*/
//native 方法
public static native void arraycopy(Object src,  int  srcPos,
									Object dest, int destPos,
									int length);