介绍

ArrayList是一个动态可调整大小的数组列表。内部是基于数组实现的，大小会自动增长，支持随机访问。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

类图如下：

数据结构

静态常量

可以看到数组的大小默认为10

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    /**
     * 分配的数组的最大大小。 尝试分配更大的数组可能会导致 OutOfMemoryError
     *
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

成员变量

elementData存储了实际的元素，transient修饰符保证他不被序列化，size是数组中元素的个数。

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;

构造方法

构造方法根据指定的大小初始化elementData数组，注意传0和不传是不一样的，
传0会初始化为EMPTY_ELEMENTDATA，不传初始化为DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

添加元素 & 扩容 add(E e)

添加元素时使用 ensureCapacityInternal() 方法来保证容量足够，如果不够时，需要使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1)，即 oldCapacity+oldCapacity/2。其中 oldCapacity >> 1 需要取整，所以新容量大约是旧容量的 1.5 倍左右。（oldCapacity 为偶数就是 1.5 倍，为奇数就是 1.5 倍 - 0.5 5 + 2.5
扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建 ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

public boolean add(E e) {
    // 保证容量大小必须大于等于size + 1
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 赋值
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    // 数组为空，minCapacity从DEFAULT_CAPACITY（10）和minCapacity取最大值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 保证容量大小至少有minCapacity个
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    // 最小容量 - 当前数组长度 > 0，说明当前数组大小不够，需要扩容，调用grow函数
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    // 旧数组的长度
    int oldCapacity = elementData.length;
    // 新数组长度为旧数组的长度 * 1.5
    // 如果旧数组是奇数，最低位会丢失，等同于oldCapacity + (oldCapacity-1) >> 1
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断newCapacity < minCapacity,说明扩容一次后容量达不到minCapacity
    if (newCapacity - minCapacity < 0)
        // newCapacity赋值为minCapacity
        newCapacity = minCapacity;
    // 超过最大分配数组大小
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 数组所有元素复制到新数组中，并赋值给elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果超过MAX_ARRAY_SIZE 赋值为Integer.MAX_VALUE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
Arrays.copyOf:
public static <T> T[] copyOf(T[] original, int newLength) {
    // 获取数组的类型，复制指定长度的元素
    return (T[]) copyOf(original, newLength, original.getClass());
}
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);
    // 从original数值的0下标开始复制到copy数组的0下标处进行复制，复制的个数是newLength
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

通过下标获取元素 get(int index)

public E get(int index) {
    // 下标范围检查
    rangeCheck(index);
    // 通过数组下标直接获取元素
    return elementData(index);
}
private void rangeCheck(int index) {
    // 下标超过size，会有自定义提示，Index: {index}, Size: {size}
    // 如果下标是负数，数组本身也会抛出IndexOutOfBoundsException
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
    return (E) elementData[index];
}

根据index移除元素 remove(int index)

// 根据下标移除元素    
public E remove(int index) {
        // 下标范围检查
        rangeCheck(index);
        modCount++;
        // 下标取值
        E oldValue = elementData(index);
        // 移动元素的数量，index后面的元素的个数
        // 因为index从0开始，所有index后面元素数量应该是size - (index + 1) = size -index -1
        int numMoved = size - index - 1;
        if (numMoved > 0)           
            // 下标从index之后的所有元素全部往前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 移除末尾下标位置元素
        elementData[--size] = null; // clear to let GC do its work
        // 返回目标的旧值
        return oldValue;
    }
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }
System.arraycopy：
/**
 *   src – 源数组。
 *   srcPos – 源数组中的起始位置。
 *   dest – 目标数组。
 *   destPos – 目标数据中的起始位置。
 *   length – 要复制的数组元素的数量。
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

根据object移除元素 remove(Object o)

    public boolean remove(Object o) {
        // 元素为null
        if (o == null) {
            for (int index = 0; index < size; index++)
                // 遍历移除第一个值为null的元素
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                // 遍历移除第一个equals相等的元素
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    private void fastRemove(int index) {
        modCount++;
        // remove后需要移动的元素个数
        int numMoved = size - index - 1;
        if (numMoved > 0)
            // index之后的所有元素向前移动一位
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        // 末尾下标元素赋值为null
        elementData[--size] = null; // clear to let GC do its work
    }

这里只有一个关键点，remove(Object o)方法只会按顺序移除第一个equals的元素，如果equals有匹配多个元素话，则只会移除第一个。

初梦 's 学习记录

ArrayList源码分析

介绍