ArrayList详解

上面就是add(E e)方法的整个过程：

5、ArrayList添加元素和扩容过程梳理

• 初始化和添加第一个元素

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("秀逗");

• 1.开始调用无参构造创建 ArrayList 对象：

// 这里 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

因此，elementData 初始化为空数组。

• 2.调用 add(E e) 方法：

 public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e; // 将元素添加到数组中
    return true;
}

• 3.调用 ensureCapacityInternal(int minCapacity) 方法：

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

minCapacity 是 size + 1，此时 size 为 0，所以 minCapacity 为 1。
因为 elementData 是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以 minCapacity 被设置为DEFAULT_CAPACITY，即 10。

• 4.调用 ensureExplicitCapacity(int minCapacity) 方法：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

modCount++ 用于支持快速失败机制。
当前 elementData.length 为 0，因为 elementData 是一个空数组。
因为 minCapacity 为 10，而 elementData.length 为 0，满足 minCapacity - elementData.length > 0，所以调用grow(minCapacity)。

• 5.调用 grow(int minCapacity) 方法：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

oldCapacity 是 0。
newCapacity 计算为 0 + (0 >> 1) = 0。
因为 newCapacity 小于 minCapacity（10），所以 newCapacity 被设置为 minCapacity，即 10。
newCapacity 不超过 MAX_ARRAY_SIZE，所以不调用 hugeCapacity(minCapacity)。
使用 Arrays.copyOf 扩展数组到新容量 10。

• 6.调用 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);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

创建一个新数组，类型和 original 相同，长度为 newLength（10）。
将 original 的内容复制到新数组中（original 为空数组，复制长度为 0）。
返回新数组，并将 elementData 指向新数组。

• 7.返回 add(E e)：
  将元素 e 添加到 elementData 中第一个位置（elementData[0] = “秀逗”）。
  增加 size 到 1。
  返回 true。

到此为止，添加第一个元素的过程完成。

假设我们已经向 ArrayList 添加了10个元素，当我们添加第11个元素时需要扩容。

arrayList.add("第11个元素");

• 1.调用 add(E e) 方法：

public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 确保容量足够
    elementData[size++] = e; // 将元素添加到数组中
    return true;
}

size 为 10，minCapacity 为 11。

• 2.调用 ensureCapacityInternal(int minCapacity) 方法：

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

elementData 不再是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，所以 minCapacity 仍为 11。

• 3. 调用 ensureExplicitCapacity(int minCapacity) 方法：

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

当前 elementData.length 为 10。
因为 minCapacity 为 11，满足 minCapacity - elementData.length > 0，所以调用 grow(minCapacity)。

• 4.调用 grow(int minCapacity) 方法：

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

oldCapacity 是 10。
newCapacity 计算为 10 + (10 >> 1) = 10 + 5 = 15。
因为 newCapacity 大于 minCapacity（11），所以 newCapacity 保持为 15。
newCapacity 不超过 MAX_ARRAY_SIZE，所以不调用 hugeCapacity(minCapacity)。
使用 Arrays.copyOf 扩展数组到新容量 15。

• 5.调用 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);
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

创建一个新数组，类型和 original 相同，长度为 newLength（15）。
将 original 的内容复制到新数组中（original 长度为 10，复制长度为 10）。
返回新数组，并将 elementData 指向新数组。

• 6.返回 add(E e)：
  将元素 e 添加到 elementData 中第11个位置（elementData[10] = “第11个元素”）。
  增加 size 到 11。
  返回 true。

6、整数溢出问题

上面看源码的过程中有JDK的注释 // overflow-conscious code

// overflow-conscious code 通常表示该代码部分是特别设计来防止和处理整数溢出问题的。

整数溢出是指在计算过程中，结果超出了类型所能表示的最大或最小值，导致结果回绕到最小值或最大值，从而产生错误的结果。

代码示例：

public static void main(String[] args) {
        int i = Integer.MAX_VALUE + 1;
        System.out.println(i);
    }

结果： -2147483648

这个结果就变成了 Integer 的最小值 ，发生了结果回绕现象。这个错误结果如果不处理可能会导致程序运行错误或其他异常行为。

在ArrayList中

private void grow(int minCapacity) {
    // overflow-conscious code 提醒开发者，这部分代码是专门设计用来防止和处理整数溢出问题的
    int oldCapacity = elementData.length;  // 旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新容量 = 旧容量 + 旧容量/2(向下取整)
    if (newCapacity - minCapacity < 0) // 如果新容量仍然不足以满足最小容量，则使用最小容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) // 如果新容量超过了数组的最大允许容量，则使用最大容量
        newCapacity = hugeCapacity(minCapacity);

    // minCapacity is usually close to size, so this is a win:  (minCapacity 通常情况下非常接近size )
    elementData = Arrays.copyOf(elementData, newCapacity);
}

int newCapacity = oldCapacity + (oldCapacity >> 1); 这里使用了 oldCapacity + (oldCapacity >> 1) 来计算新容量。
oldCapacity >> 1 是将 oldCapacity 右移一位，相当于 oldCapacity 除以2，向下取整。
这使得新容量约为旧容量的1.5倍（即约50%的增长）。

if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);

检查计算得到的新容量是否小于需要的最小容量 minCapacity，如果是，则将新容量设置为 minCapacity。
检查新容量是否超过了允许的最大容量 MAX_ARRAY_SIZE，如果是，则调用 hugeCapacity(minCapacity) 方法处理。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow  如果minCapacity 小于0 直接抛内存溢出错误
        throw new OutOfMemoryError();
 				
    // 如果 minCapacity 大于 MAX_ARRAY_SIZE   minCapacity  =  Integer.MAX_VALUE 	
    return (minCapacity > MAX_ARRAY_SIZE) ? 
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

如果 minCapacity 超过 MAX_ARRAY_SIZE，则返回 Integer.MAX_VALUE 作为新容量。
否则，返回 MAX_ARRAY_SIZE。
通过这些检查和处理，代码确保了在扩容过程中不会出现整数溢出的问题。例如，如果 oldCapacity 非常大，oldCapacity + (oldCapacity >> 1) 可能会导致整数溢出。通过检查新容量是否超出 minCapacity 和 MAX_ARRAY_SIZE，代码能够安全地处理扩容操作，防止整数溢出引发的错误。

7、fail-fast机制

     fail-fast机制是指在遍历集合（如ArrayList、HashMap等）时，如果集合结构被修改（如添加、删除或更新元素），
则迭代器会立即抛出ConcurrentModificationException，以快速响应程序的错误状态。 这个机制有助于开发者及时发现并修复并发修改集合的问题，防止程序后续再运行出现错误的结果。

触发fail-fast机制代码示例：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class TestA {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>(Arrays.asList("秀逗", "大黄", "四眼"));
        for (String s : list) {
            if("四眼".equals(s)){
                list.remove(s);
            }
        }
    }
}

结果：

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
	at java.util.ArrayList$Itr.next(ArrayList.java:851)
	at TestA.main(TestA.java:8)

可以看到 程序抛出 ConcurrentModificationException 。
在遍历过程中，当遇到元素"四眼"时，从集合中移除该元素。这会触发fail-fast机制。

迭代器和 fail-fast 机制工作原理：

在Java集合框架中，每个集合对象都有一个modCount字段，用于记录集合的结构修改次数。每次修改集合（如添加或删除元素）时，modCount都会递增。

上面的例子在增强型 for 循环中，实际上是通过隐式使用 Iterator 来实现的。因此，迭代过程如下：

• 1.获取迭代器：
  在增强型 for 循环开始时，list 会调用 iterator() 方法来获取一个 Iterator 对象。

Iterator<String> iterator = list.iterator();

• 2.记录 expectedModCount：
  迭代器在创建时会记录当前 modCount 值到 expectedModCount 中。

int expectedModCount = modCount;

• 3.遍历集合并检查 modCount：
  每次调用 iterator.next() 方法时，迭代器都会检查 expectedModCount 是否等于集合的 modCount。

if (modCount != expectedModCount)
    throw new ConcurrentModificationException();

如果modCount != expectedModCount 就抛出 ConcurrentModificationException

分析下上面代码中，执行步骤和 ConcurrentModificationException 抛出的过程：

• 1. 初始化 ArrayList 和 Iterator：

List<String> list = new ArrayList<>(Arrays.asList("秀逗", "大黄", "四眼"));
Iterator<String> iterator = list.iterator();
// expectedModCount = modCount = 0

• 2.第一次迭代：
  iterator.next() 返回 “秀逗”。
  检查 modCount 是否等于 expectedModCount。相等，继续。

• 3.第二次迭代：
  iterator.next() 返回 “大黄”。
  检查 modCount 是否等于 expectedModCount。相等，继续。

• 4.第三次迭代：
  iterator.next() 返回 “四眼”。
  检查 modCount 是否等于 expectedModCount。相等，继续。
  list.remove(s) 移除 “四眼”。此时，modCount 递增，modCount 变为 1。

String s = iterator.next(); // "四眼"
if ("四眼".equals(s)) {
    list.remove(s); // 这行代码会导致 modCount 增加到 1
}

• 5. 下一次迭代：
     在下一次调用 iterator.next() 之前，检查 modCount 是否等于 expectedModCount。
     由于 modCount 已经变为 1，而 expectedModCount 仍然是 0，不相等，抛出 ConcurrentModificationException。

8. ArrayList的addAll(Collection c)方法

这个方法用的也挺多，并且有个 扩容的细节需要注意下

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray(); // 将传入的集合转换为数组
    int numNew = a.length; // 获取新元素的数量
    ensureCapacityInternal(size + numNew); // 确保内部数组有足够的容量容纳新元素
    System.arraycopy(a, 0, elementData, size, numNew); // 将新元素复制到内部数组
    size += numNew; // 更新 ArrayList 的大小
    return numNew != 0; // 如果添加了元素，返回 true，否则返回 false
}

这里就不一步一步再分析了 和上面add方法 实际上基本一致，需要注意到点就是
当代码走到grow方法的时候 minCapacity = size + numNew 即旧数组的实际元素个数+新添加的集合内元素个数
如果扩容后的大小 newCapacity - minCapacity < 0
此时的新数组容量就变成了 旧数组的实际元素个数+新添加的集合内元素个数

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

举个例子就好理解了：

 public static void main(String[] args) throws Exception {
        // 原集合添加5个元素  实际数组长度是 10
        List<String> list = new ArrayList<>();
        list.add("1");
        list.add("2");
        list.add("3");
        list.add("4");
        list.add("5");

        Field elementDataField = ArrayList.class.getDeclaredField("elementData");
        elementDataField.setAccessible(true);
        Object[] elementData = (Object[]) elementDataField.get(list);
        System.out.println("list集合内实际数组长度是"+elementData.length);


        List<String> list2 = new ArrayList<>(Arrays.asList("1", "2", "3","4", "5", "6","7","8","9","10","11"));
        list.addAll(list2);

        // list调用 addAll方法 扩容后 newCapacity = 15 , minCapacity = 5+11 = 16
        // grow 方法中   if (newCapacity - minCapacity < 0)   newCapacity = minCapacity;
        // 所以新的数组长度就是 newCapacity = minCapacity = 16
        Object[] elementData1 = (Object[]) elementDataField.get(list);
        System.out.println("list集合addAll后实际数组长度是"+elementData1.length);

        // 再添加一个  原容量16 已经有16个元素了  这次也会扩容 容量变成 16 + 16/2 = 24
        list.add("13");
        Object[] elementData2 = (Object[]) elementDataField.get(list);

        System.out.println("list集合addAll后再add一个元素实际数组长度是"+elementData2.length);
    }

打印结果：

list集合内实际数组长度是10
list集合addAll后实际数组长度是16
list集合addAll后再add一个元素实际数组长度是24

所以需要注意的点就是，ArrayList的扩容 并非每次都增加原容量的 约1.5倍。
比如上面的例子就是例外，如果增加约到1.5倍 容量还是不够，就会扩容到实际元素大小的容量。

秀逗、四眼、大黄是文章中的常客

下面一睹真容。

秀逗：

四眼：

大黄：