深入浅出 JAVA 之集合 - ArrayList

1transient Object[] elementData;

 1/**
 2 * 默认初始容量
 3 */
 4private static final int DEFAULT_CAPACITY = 10;
 5
 6/**
 7 * 创建空 ArrayList 实例所使用的空数组
 8 */
 9private static final Object[] EMPTY_ELEMENTDATA = {};
10
11/**
12 * 创建空 ArrayList 实例，且设置容量为默认大小 10 的时候所使用的空数组
13 */
14private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
15
16/**
17 * 存储集合中元素的数组 (使用transient关键字修饰的，因此在进行序列化时该属性不会被序列化)
18 */
19transient Object[] elementData;
20
21/**
22 * 集合的大小 (即集合中的元素数量)
23 */
24private int size;

1/**
2 * 无参构造方法，创建一个空数组
3 */
4public ArrayList() {
5    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
6}

 1/**
 2 * 支持配置初始容量的构造方法，创建一个指定容量的空数组
 3 *
 4 * @param  initialCapacity  初始容量
 5 * @throws IllegalArgumentException 如果设置的初始容量为负数，则抛出非法参数异常
 6 */
 7public ArrayList(int initialCapacity) {
 8    // 如果设置的初始容量大于 0，则创建一个 initialCapacity 长度的 Object 数组赋值给 ArrayList 对象的 elementData 属性
 9    if (initialCapacity > 0) {
10        this.elementData = new Object[initialCapacity];
11    }
12    // 如果设置的初始容量等于 0，则将预定义的空数组 EMPTY_ELEMENTDATA 数组赋给 ArrayList 对象的 elementData 属性
13    else if (initialCapacity == 0) {
14        this.elementData = EMPTY_ELEMENTDATA;
15    } 
16    // 如果设置的初始容量小于 0，则抛出非法参数异常
17    else {
18        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
19    }
20}

 1/**
 2 * 支持根据已有数组创建新集合的构造方法
 3 *
 4 * @param c 已有的 Collection 集合
 5 * @throws NullPointerException 如果传入的集合为空，则抛出空指针异常
 6 */
 7public ArrayList(Collection<? extends E> c) {
 8    // 将输入的 Collection 集合 c 转换为一个数组赋给 elementDat 变量
 9    elementData = c.toArray();
10    // 将 elementData 数组长度作为集合大小，然后判断大小是否不为 0
11    if ((size = elementData.length) != 0) {
12        // 检查 elementData 的类型是否为 Object[] 数组
13        if (elementData.getClass() != Object[].class) {
14            // 如果是则将使用 Arrays.copyOf() 方法创建一个新数组，并将其类型设置为 Object[]
15            elementData = Arrays.copyOf(elementData, size, Object[].class);
16        }
17    } else {
18        // 将 EMPTY_ELEMENTDATA 空数组作为集合的 elementData 数组，这里 EMPTY_ELEMENTDATA 是静态的提前
19        // 创建好的数组，这样避免重新创建数组，省去了内存分配和数组复制的操作，从而提高程序性能。
20        this.elementData = EMPTY_ELEMENTDATA;
21    }
22}

 1/**
 2 * 在集合末尾插入一个元素
 3 *
 4 * @param e 插入的元素
 5 * @return 插入成功则返回 true
 6 */
 7public boolean add(E e) {
 8    // 确保 ArrayList 中有足够的容量来存储新元素，如果没有足够的容量，就会通过扩容机制增加 ArrayList 的容量
 9    ensureCapacityInternal(size + 1);
10    // 将元素插入到集合数组的末尾位置，然后使集合大小 size+1，以便下次调用 add 方法时可以在正确的位置添加新元素
11    elementData[size++] = e;
12    // 默认返回 true
13    return true;
14}

 1/**
 2 * 指定位置插入元素方法
 3 *
 4 * @param index 插入的索引位置
 5 * @param element 要插入的元素
 6 * @throws IndexOutOfBoundsException 数组越界异常
 7 */
 8public void add(int index, E element) {
 9    // 检查指定的索引位置是否超出了当前集合可以存储的范围
10    rangeCheckForAdd(index);
11    // 调用 ensureCapacityInternal() 方法确保集合内部数组具有足够的容量来存储新添加的元素
12    ensureCapacityInternal(size + 1);
13    // 将指定索引及其后面的元素向右移动一个位置，以为新元素腾出空间
14    System.arraycopy(elementData, index, elementData, index + 1, size - index);
15    // 将新元素添加到指定的索引位置上
16    elementData[index] = element;
17    // 集合大小+1
18    size++;
19}

 1/**
 2 * 确保 ArrayList 中有足够的容量来存储新元素
 3 * 
 4 * @param minCapacity 集合存储元素所需要的最小容量
 5 */
 6private void ensureCapacityInternal(int minCapacity) {
 7    // 调用 calculateCapacity 方法计算 ArrayList 集合内部数组的最小容量
 8    // 调用 ensureExplicitCapacity() 方法，将 calculateCapacity 方法计算的最小容量作为参数
 9    // 如果 ArrayList 内部数组的容量小于指定的最小容量，则会通过扩容机制增加 ArrayList 的容量，以确保容量足够存储元素
10    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
11}

 1/**
 2 * 计算 ArrayList 集合内部数组的最小容量
 3 *
 4 * @param elementData 集合中存储元素的数组
 5 * @param minCapacity 集合存储元素所需要的最小容量
 6 * @return 计算后的集合所需的最小容量
 7 */
 8private static int calculateCapacity(Object[] elementData, int minCapacity) {
 9    // 检查 elementData 是否为静态 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 数组
10    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
11        // 如果是则说 elementData 是空数组，则将最小容量和默认容量 DEFAULT_CAPACITY 进行比较，
12        // 将其中较大的值返回作为计算后的最小容量。
13        return Math.max(DEFAULT_CAPACITY, minCapacity);
14    }
15    // 如果不是则说明 elementData 不是空数组，则直接返回指定的最小容量
16    return minCapacity;
17}

 1/**
 2 * 确保 ArrayList 内部数组具有指定的最小容量
 3 *
 4 * @param minCapacity 集合存储元素所需要的最小容量
 5 */
 6private void ensureExplicitCapacity(int minCapacity) {
 7    // 记录该 ArrayList 对象的结构修改次数，以便在遍历该对象时检查它是否被其他代码修改过。
 8    modCount++;
 9
10    // 判断集合存储元素所需要的最小容量是否大于集合 elementData 数组当前的容量，如果是则进行库容操作
11    if (minCapacity - elementData.length > 0) {
12        // 进行扩容操作
13        grow(minCapacity);
14    }
15}

 1/**
 2 * 集合扩容，增加 ArrayList 内部数组的容量以便存储更多的元素。
 3 *
 4 * @param minCapacity 所需的最小容量
 5 */
 6private void grow(int minCapacity) {
 7    // 记录集合旧容量到 oldCapacity 变量
 8    int oldCapacity = elementData.length;
 9    // 计算集合新容量到 newCapacity 变量，新容量大小为旧容量的 1.5 倍
10    int newCapacity = oldCapacity + (oldCapacity >> 1);
11    // 检查计算后的新容量是否大于等于所需的最小容量，如果是则直接使用新容量,否则将最小容量作为新容量
12    if (newCapacity - minCapacity < 0) {
13        newCapacity = minCapacity;
14    }
15    // 如果计算后的新容量大于 MAX_ARRAY_SIZE，会调用 hugeCapacity() 方法计算新的容量。
16    // 这是为了避免数组大小无限制地增长，因为数组大小不能超过 MAX_ARRAY_SIZE，否则会抛出 OutOfMemoryError 错误。
17    if (newCapacity - MAX_ARRAY_SIZE > 0) {
18        newCapacity = hugeCapacity(minCapacity);
19    }
20    // 将当前 ArrayList 内部数组 elementData 复制到一个新的数组中，其大小为计算后的新容量 newCapacity
21    elementData = Arrays.copyOf(elementData, newCapacity);
22}

 1/**
 2 * 删除指定位置元素
 3 *
 4 * @param index 要删除元素位置的索引
 5 * @return 删除的元素
 6 * @throws IndexOutOfBoundsException 索引越界异常
 7 */
 8public E remove(int index) {
 9    // 检查索引是否越界
10    rangeCheck(index);
11    // 记录修改次数
12    modCount++;
13    // 获取待删除元素的值
14    E oldValue = elementData(index);
15    // 计算待移动的元素个数
16    int numMoved = size - index - 1;
17    // 如果判断 numMoved 是否大于 0，如果是则说明有元素需要移动，则将数组元素向左移动
18    if (numMoved > 0) {
19        // 数组元素向左移动
20        System.arraycopy(elementData, index+1, elementData, index, numMoved);
21    }
22    // 将数组最后一个元素置空
23    elementData[--size] = null;
24
25    // 返回已经删除的元素
26    return oldValue;
27}

 1/**
 2 * 删除指定元素值的元素
 3 *
 4 * @param o 要删除元素
 5 * @return 如果待删除的指定元素存在则返回 true，否则返回 false
 6 */
 7public boolean remove(Object o) {
 8    // 如果待删除元素为 null，则遍历集合，查找集合中为 null 的元素进行删除
 9    if (o == null) {
10        for (int index = 0; index < size; index++) {
11            // 找到第一个为 null 的元素，然后进行快速删除，最后返回结果 true
12            if (elementData[index] == null) {
13                fastRemove(index);
14                return true;
15            }
16        }
17    }
18    // 如果待删除元素不为 null，则遍历集合，查找集合中和待删除元素相同的元素进行删除
19    else {
20        for (int index = 0; index < size; index++) {
21            // 找到第一个与待删除元素相同的元素，然后进行快速删除，最后返回结果 true
22            if (o.equals(elementData[index])) {
23                fastRemove(index);
24                return true;
25            }
26        }
27    }
28    // 如果没有找到和待删除元素相同的元素，则返回 false
29    return false;
30}

 1/** 
 2 * 获取指定索引位置元素值
 3 *
 4 * @param  index 要查找元素在集合中的位置索引
 5 * @return 集合中指定位置的元素
 6 * @throws IndexOutOfBoundsException 索引越界异常
 7 */
 8public E get(int index) {
 9    // 检查索引是否越界
10    rangeCheck(index);
11    // 返回集合指定位置中的元素
12    return elementData(index);
13}

1/**
2 * 获取集合指定位置中的元素
3 *
4 * @param index 要查找元素在集合中的位置索引
5 * @return 集合中指定位置的元素
6 */
7E elementData(int index) {
8    return (E) elementData[index];
9}

 1/** 
 2 * 设置指定索引位置元素值
 3 *
 4 * @param index 需要替换的元素索引
 5 * @param element 要存储在指定位置的元素
 6 * @return 先前位于指定位置中的旧元素
 7 * @throws IndexOutOfBoundsException 索引越界异常
 8 */
 9public E set(int index, E element) {
10    // 检查索引是否越界
11    rangeCheck(index);
12    // 获取集合指定位置中的旧元素，赋给变量 oldValue
13    E oldValue = elementData(index);
14    // 将传入的新元素插入到集合中的指定索引位置
15    elementData[index] = element;
16    // 返回集合中指定索引位置中原先的旧元素
17    return oldValue;
18}

 1/**
 2 * 查找集合中指定元素最后一次出现的位置
 3 * 
 4 * @param o 待查找的元素
 5 * @return 查找到的元素位置的索引，如果未找到则返回 -1
 6 */
 7public int lastIndexOf(Object o) {
 8    // 如果待查找元素为 null，从后向前遍历，找到第一个为 null 的元素，然后返回该元素的下标
 9    if (o == null) {
10        for (int i = size-1; i >= 0; i--) {
11            if (elementData[i]==null) {
12                return i;
13            }
14        }
15    }
16    // 如果待查找元素不为 null，从后向前遍历，找到第一个与待查找元素相等的元素，然后返回该元素的下标
17    else {
18        for (int i = size-1; i >= 0; i--) {
19            if (o.equals(elementData[i])) {
20                return i;
21            }
22        }
23    }
24    // 如果列表中不存在待查找元素，则返回 -1
25    return -1;
26}