《ArrayList的底层原理》

一、简介

ArrayList 是 Java 集合框架中最常用的 动态数组实现类，实现了 List 接口，允许存储 有序、可重复 的元素。

支持随机访问，访问时间复杂度为 O(1)
插入/删除非尾部元素需移动数据，时间复杂度为 O(n)
非线程安全，需手动处理并发问题

二、底层结构

核心成员变量：

/**
    * 默认初始容量大小
    */
   private static final int DEFAULT_CAPACITY = 10;

   /**
    * 空数组（用于空实例）。
    */
   private static final Object[] EMPTY_ELEMENTDATA = {};

   //用于默认大小空实例的共享空数组实例。
   //我们把它从EMPTY_ELEMENTDATA数组中区分出来，以知道在添加第一个元素时容量需要增加多少。
   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   /**
    * 保存ArrayList数据的数组
    */
   transient Object[] elementData; // non-private to simplify nested class access

   /**
    * ArrayList 所包含的元素个数
    */
   private int size;

元素存储在 Object[] 中
所有元素按顺序排列，支持下标访问

三、初始化与扩容机制

1. 初始化容量

使用无参构造时，并不会立刻分配内存
懒加载机制：第一次添加元素时初始化容量为 10

2. `ensureCapacityInternal`：确保容量

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

3. `ensureExplicitCapacity`：触发扩容判断

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
	modCount++;
    
   	// overflow-conscious code
    if (minCapacity - elementData.length > 0)
        
	//调用grow方法进行扩容，调用此方法代表已经开始扩容了
	grow(minCapacity);
}

modCount : 快速失败机制

4. `grow`：核心扩容逻辑

/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
    
	// oldCapacity为旧容量，newCapacity为新容量
	int oldCapacity = elementData.length;
    
	//将oldCapacity 右移一位，相当于oldCapacity / 2，
	//位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
	int newCapacity = oldCapacity + (oldCapacity >> 1);
    
	//然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
	if (newCapacity - minCapacity < 0)
		newCapacity = minCapacity;
    
	//再检查新容量是否超出了ArrayList所定义的最大容量，
	//若超出了，则调用hugeCapacity()来比较minCapacity和 MAX_ARRAY_SIZE，
	//如果minCapacity大于MAX_ARRAY_SIZE，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。
	if (newCapacity - MAX_ARRAY_SIZE > 0)
		newCapacity = hugeCapacity(minCapacity);
    
	// minCapacity 通常接近 size，所以这样做是有利的
	elementData = Arrays.copyOf(elementData, newCapacity);
}

5. `hugeCapacity`：极限处理

//要分配的最大数组大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

四、常用方法源码解析

1. `add(int index, E e)`：添加元素

/**
 * 在此列表中的指定位置插入指定的元素。
 * 先调用 rangeCheckForAdd 对index进行界限检查；然后调用 ensureCapacityInternal
 * 方法保证capacity足够大；
 * 再将从index开始之后的所有成员后移一个位置；将element插入index位置；最后size加1。
 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1); // 修改 modCount 的值
    
    // arraycopy()这个实现数组之间复制的方法一定要看一下，下面就用到了arraycopy()方法实现数组自己复制自己
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);
    elementData[index] = element;
    size++;
}

2. `get(int index)`：获取元素

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];
}

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3. `remove(int index)`：删除元素

/**
 * 删除该列表中指定位置的元素。 将任何后续元素移动到左侧（从其索引中减去一个元素）。
 */
public E remove(int index) {
    rangeCheck(index);
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;

    if (numMoved > 0) {
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }

    elementData[--size] = null; // 防止内存泄漏
    return oldValue;
}

五、总结

特性	说明
存储结构	动态数组 `Object[]`
初始容量	默认 10（懒加载）
扩容机制	原容量 * 1.5
插入/删除效率	尾部快，中间慢
线程安全	非线程安全，需自行加锁或使用并发集合