GM的博客

ArrayList详解

# ArrayList详解

基于JDK8

# 1、ArrayList的底层数据结构和继承体系

ArrayList中的元素实际上是存储在Object数组中的 transient Object[] elementData;。

ArrayList的继承体系：

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

  
        复制成功！
mixureSecure

# 2、ArrayList的构造函数

# ①、我们最常用的空参构造函数

 // 存储实际元素的数组
 transient Object[] elementData
 // 默认的空Object数组
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
 public ArrayList() {
 		// 当我们使用ArrayList的空参构造函数时 会初始化ArrayList的elementData 为空Object数组
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

  
        复制成功！

# ②、带容量参数的构造函数

private static final Object[] EMPTY_ELEMENTDATA = {};
// 参数是 开发人员传入的初始容量大小
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        	// 如果传的初始容量大于0 则  elementData  初始化为 对应容量大小的Object数组 Object[initialCapacity]
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
        	// 如果传的初始容量等于0  则 elementData   初始化为空 Object数组  {}
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        	// 如果传的初始容量小于0  则抛异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

  
        复制成功！

# ③、带集合参数的构造函数

这个构造函数会接受一个 Collection接口实现类的实例，即可以拿其他的单值集合来初始化为ArrayList。
这里涉及到一个比较重要的方法 Arrays.copyOf方法，下面会讲到。

private static final Object[] EMPTY_ELEMENTDATA = {};
// 参数是 开发人员传入的其他集合
public ArrayList(Collection<? extends E> c) {
		// 把开发人员传入的其他集合 转成数组 并把elementData 的引用指向 该数组
        elementData = c.toArray();  // toArray方法调用的就是 Arrays.copyOf
        // 如果初始化后的 elementData 的长度不为0 
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            // 这个注释指向的是 JDK的bug  下面这个if就是为了解决这个bug
            if (elementData.getClass() != Object[].class)
            	// 如果 c.toArray()返回的数组类型不是Object数组类型
            	// 就使用 Arrays.copyOf方法 复制成  Object数组类型
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 如果初始化后的 elementData 的长度为0  就初始化为一个空  Object数组类型
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

// toArray方法调用的就是 Arrays.copyOf
public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
}

  
        复制成功！

# 小插曲：JDK 漏洞 6260652

可以看到这个代码注释： // c.toArray might (incorrectly) not return Object[] (see 6260652)

	// c.toArray might (incorrectly) not return Object[] (see 6260652)
	// c.toArray()返回的数组类型可能不是Object数组类型
  if (elementData.getClass() != Object[].class)
            	// 如果 c.toArray()返回的数组类型不是Object数组类型
            	// 就使用 Arrays.copyOf方法 复制成  Object数组类型
                elementData = Arrays.copyOf(elementData, size, Object[].class);

  
        复制成功！

这段代码解决的是什么漏洞？什么情况下会出现这个漏洞呢？ 这个漏洞可能会引发哪些问题？ 漏洞在官网上的描述：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 (opens new window)

mixureSecure

问题提出时间：2005-04-25 解决时间: 2015-07-09 ， 受到影响的版本JDK5.0 和 6

在JDK9中修复了该问题。

mixureSecure

这里的问题描述说的是：

JDK1.5.0_02版本中、 Collection接口的 <T> T[] toArray(T[] a);方法上有这么一段注释

Note that toArray(new Object[0])  is identical in function to toArray()   
意思是   toArray(new Object[0]) 方法和  toArray() 方法在功能上是相同的  

  
        复制成功！

我们看下这两个方法在Collection接口中的定义：


Object[] toArray();

<T> T[] toArray(T[] a);

  
        复制成功！

我们知道接口是属于比较高层次的抽象，任何实现了某个接口的类都必须遵循这个接口中方法的声明。 也就是说 Collection接口的子类 都必须遵循上面 toArray(new Object[0]) 方法和 toArray() 方法在功能上是相同的这个声明。

但是，但是来了就是问题要来了。县长来了，鹅城就太平了。 Arrays类来了JDK的坑就有了。。。

之前其实已经提过Arrays.asList方法返回的List 实际上是 Arrays类的一个静态内部类 private static class ArrayList<E> 并非 java.util.ArrayList ，所以之前在 **Java API使用避坑合集 (opens new window)**这篇文章中介绍过，private static class ArrayList 不支持添加或者修改操作。否则会报java.lang.UnsupportedOperationException。

那么我们现在说的这个漏洞又是Arrays搞得鬼，这真验证了那句话，约80%的程序错误可能源于20%的代码模块(2/8定律，又称为帕累托原则（Pareto Principle）)。

我们回到 JDK 漏洞 6260652的讨论，上面说了 private static class ArrayList 坑， 那么 JDK 漏洞 6260652 是具体怎么体现的呢？

实际上就是 private static class ArrayList 这个静态内部类， 没有遵循Collection 接口声明的 这句话Note that toArray(new Object[0]) is identical in function to toArray() 我们看下private static class ArrayList中 toArray的具体实现

// 无参的toArray 实际上调用的 是clone方法  返回的是Object数组 (但是返回的数组实际的类型 并一定是Object)
@Override
public Object[] toArray() {
   return a.clone();
}

// 有参的toArray 实际上调用的是 Arrays.copyOf  返回的数组类型是根据具体的运行时类型而确定的
// 所以如果该方法返回了 Object[]   上面的toArray()返回了 String[]  那么两个toArray方法返回的数组类型就不一致了  
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    int size = size();
    if (a.length < size)
        return Arrays.copyOf(this.a, size,
                             (Class<? extends T[]>) a.getClass());
    System.arraycopy(this.a, 0, a, 0, size);
    if (a.length > size)
        a[size] = null;
    return a;
}

  
        复制成功！

这两个方法在某些情况下 返回的结果并不一致。也就不遵循Collection 接口对这两个方法的声明。

看下面的代码：

public class TestA {
    public static void main(String[] args) {
        
       List l = Arrays.asList(args);
        
        Object[] objects1 = l.toArray();
        Object[] objects2 = l.toArray(new Object[0]);
        
        System.out.println(objects1.getClass());
        System.out.println(objects2.getClass());

    }
}

  
        复制成功！

运行结果：

class [Ljava.lang.String;
class [Ljava.lang.Object;

  
        复制成功！

很明显同一个 private static class ArrayList 对象调用toArray()和toArray(new Object[0])两个方法，虽然明面上返回的数组类型都是Object， 但是实际上打印出来的运行时结果却不一致。这和 Collection 接口声明的 这句话Note that toArray(new Object[0]) is identical in function to toArray() 相悖了。这就是这个漏洞的具体表现。

这个漏洞可能会造成的问题如下：

public static void main(String[] args) {

        List<String> list = Arrays.asList("a","b");
        System.out.println(list.getClass());
        Object[] o = list.toArray();
        System.out.println(o.getClass());
        o[0] = "c";
        System.out.println(Arrays.toString(o));
        
        // ArrayStoreException
        o[1] = new Object();

    }

  
        复制成功！

运行结果：

class java.util.Arrays$ArrayList
class [Ljava.lang.String;
[c, b]
Exception in thread "main" java.lang.ArrayStoreException: java.lang.Object

  
        复制成功！

o[1] = new Object();报错了 ArrayStoreException 因为 java.util.Arrays$ArrayList 也就是 Arrays的静态内部类 private static class ArrayList 的toArray()方法返回了 Object数组，但是这个数组实际上的类型是String。 如果这个时候我们给 toArray()方法返回的数组中的元素赋值一个Object类型的变量，显然在编译时期可以正常编译，但是在运行时期就会出现Object对象 向String数组中存储的情况，此时JVM会抛出 ArrayStoreException。

我们再回头看真正的 java.util.ArrayList 集合中 的这段代码的时候就清楚了：

mixureSecure

所以这个判断是为了保证真正存储集合元素的数组类型是 Object类型。

如果没有这段代码if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class);

我们通过反射做点小手脚，运行下面这段代码：

public static void main(String[] args) throws Exception {

        // 创建一个普通的 ArrayList
        ArrayList<Object> list = new ArrayList<>(Arrays.asList("1", "2", "3"));

        // 使用反射获取 ArrayList 类中的 elementData 字段
        Field elementDataField = ArrayList.class.getDeclaredField("elementData");
        elementDataField.setAccessible(true);

        // 将 list对象的elementData 字段设置为一个新的数组  相当于 在ArrayList有参构造中执行了elementData = c.toArray();
        // 未执行  if (elementData.getClass() != Object[].class)    elementData = Arrays.copyOf(elementData, size, Object[].class);
        Object[] objects = Arrays.asList("1", "2", "3").toArray();
        elementDataField.set(list, objects);

        System.out.println(list);  // 输出: [1, 2, 3]

        System.out.println(objects.getClass());  // 输出 class [Ljava.lang.String;

        // 下面这行代码会抛出 ArrayStoreException
        list.add(new Object());
    }

  
        复制成功！

可以看到在 list.add(new Object());时抛了 java.lang.ArrayStoreException 因为在运行时 ArrayList尝试把Object类型的对象添加进 String类型的数组中 这是不被允许的。

那么再回过头来看：

 // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);

  
        复制成功！

目的就很明确了， 由于运行时 c.toArray返回的可能不是 Object类型的数组 ，为了保证集合运行时的类型安全 通过elementData = Arrays.copyOf(elementData, size, Object[].class); 来保证 elementData 获取的是Object数组类型。

在JDK9版本，对 private static class ArrayList 的toArray()方法也进行了改进： JDK9之前的版本是这样的：

 @Override
public Object[] toArray() {
 	   // clone返回的是 运行时的具体类型
      return a.clone();
  }

  
        复制成功！

JDK9及之后的版本是这样的：

 @Override
 public Object[] toArray() {
			// 利用Arrays.copyOf 复制一个新的 Object类型数组
            return Arrays.copyOf(this.a, this.a.length, Object[].class);
      }

  
        复制成功！

# 3、ArrayList的Arrays.copyOf方法

先看下这个方法的实现： 可以看到这个方法有许多重载

mixureSecure

我们主要来看下ArrayList集合带参构造中用的这个copyOf方法elementData = Arrays.copyOf(elementData, size, Object[].class);

/**
     * 创建一个指定类型和长度的新数组，并将原数组中的元素复制到新数组中。
     * 
     * @param <T> 新数组中元素的类型。
     * @param <U> 原数组中元素的类型。
     * @param original 原数组，从中复制元素。
     * @param newLength 新数组的长度。
     * @param newType 新数组的类类型。
     * @return 指定类型的新数组，其中包含从原数组复制的元素。
     */
    public static <T, U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        // 创建新数组的引用
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            // 如果新数组类型是 Object[]，则直接创建一个新的 Object 数组
            ? (T[]) new Object[newLength]
            // 否则，使用反射根据指定类型创建新数组
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        
        // 将原数组的元素复制到新数组中，复制长度为原数组和新数组长度中的较小值
        System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
        
        // 返回新数组
        return copy;
    }

  
        复制成功！

再看下System.arraycopy方法
这个本地方法通过 Java Native Interface (JNI) 与底层操作系统进行交互，从而实现高效的数组复制操作。

/**
 * 将一个数组中的元素复制到另一个数组中。
 * 
 * @param src    源数组，从中复制数据。
 * @param srcPos 源数组中的起始位置，从该位置开始复制。
 * @param dest   目标数组，将数据复制到此数组中。
 * @param destPos目标数组中的起始位置，从该位置开始放置复制的数据。
 * @param length 需要复制的元素数量。
 */
public static native void arraycopy(Object src, int srcPos,
                                    Object dest, int destPos,
                                    int length);

  
        复制成功！

实际上copyOf 不仅仅在带参构造中被使用了，在ArrayList的扩容过程也有用到，下面会讲到。

# 4、ArrayList的add()方法和扩容过程

我们执行下面的代码 先利用空参构造函数创建一个ArrayList对象， 然后往ArrayList中添加第一个元素 ArrayList<String> arrayList = new ArrayList<>(); arrayList.add("秀逗");

从add(E e)方法开始看：

//  ArrayList用于保存元素的数组大小 没有赋值 默认是0
private int size;   

// 默认空数组
private static final Object[] EMPTY_ELEMENTDATA = {};

// 默认的 ArrayList 容量大小是 10
private static final int DEFAULT_CAPACITY = 10;
 
public boolean add(E e) {
		// ensureCapacityInternal 方法确保内部容量足够容纳新的元素
        ensureCapacityInternal(size + 1); 
        // 将元素添加到数组中，并更新 size
        elementData[size++] = e;
        return true;
    }

  
        复制成功！

ensureCapacityInternal方法：


private void ensureCapacityInternal(int minCapacity) {
		//  minCapacity 表示该方法所需要确保的最小容量
		// 如果 elementData 是默认空数组 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 计算所需的最小容量：取默认容量和指定最小容量中的较大值  
            // 我们用空的ArrayList 添加第一个元素 这里的指定最小容量就是1  minCapacity 取的是 DEFAULT_CAPACITY = 10 
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
		// 明确ArrayList 的容量 
        ensureExplicitCapacity(minCapacity);
    }

  
        复制成功！

ensureExplicitCapacity方法：

// 确保 ArrayList 的内部数组（elementData）有足够的容量来容纳 minCapacity 个元素。
// 如果当前的容量不足以容纳这些元素，该方法会调用grow方法来扩展数组的容量。
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;     // modCount++  用于支持 fail-fast机制 后面会说
        
        // 如果当前数组容量不足，则进行扩容  
        if (minCapacity - elementData.length > 0)
            // minCapacity（需要确保的最小容量）  比elementData.length(数组的真实容量) 大
            // 调用扩容方法
            grow(minCapacity);
    }

  
        复制成功！

grow方法：

private void grow(int minCapacity) {
        // overflow-conscious code  提醒开发者，这部分代码是专门设计用来防止和处理整数溢出问题的
        int oldCapacity = elementData.length;  // 旧容量
        int newCapacity = oldCapacity + (oldCapacity >> 1);  // 新容量 = 旧容量 + 旧容量/2(向下取整)
        if (newCapacity - minCapacity < 0) // 如果新容量仍然不足以满足最小容量，则使用最小容量
        	// 当我们使用 addAll方法时 可能会走到这
            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);
    }

  
        复制成功！

hugeCapacity方法：

// 在 Java 中，数组的最大长度受到虚拟机实现的限制 
// 通过 Integer.MAX_VALUE - 8 ，MAX_ARRAY_SIZE 考虑了 JVM 内部的实现细节和可能的额外开销，确保数组分配在绝大多数情况下都是安全的
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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;
}

  
        复制成功！

copyOf方法：

/**
     * 创建一个新的数组，包含原数组的所有元素，并将其长度扩展到指定的新长度。
     * 
     * @param <T> 元素的类型
     * @param original 原数组
     * @param newLength 新数组的长度
     * @return 包含原数组所有元素并扩展到新长度的数组
     */
    public static <T> T[] copyOf(T[] original, int newLength) {
        // 调用另一个重载的 copyOf 方法，传递原数组的类型
        return (T[]) copyOf(original, newLength, original.getClass());
    }    

  
        复制成功！

copyOf方法：

/**
     * 创建一个新的数组，包含原数组的所有元素，并将其长度扩展到指定的新长度。
     * 新数组的类型由 newType 参数指定。
     * 
     * @param <T> 新数组的元素类型
     * @param <U> 原数组的元素类型
     * @param original 原数组
     * @param newLength 新数组的长度
     * @param newType 新数组的类型
     * @return 包含原数组所有元素并扩展到新长度的数组
     */
    public static <T, U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        // 使用 @SuppressWarnings("unchecked") 来抑制类型转换警告
        @SuppressWarnings("unchecked")
        // 创建一个新的数组，数组类型由 newType 指定
        T[] copy = ((Object)newType == (Object)Object[].class)
            // 如果新数组类型是 Object[]，则直接创建一个新的 Object 数组
            ? (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;
    }

  
        复制成功！

上面就是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。

    1. 调用 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
}

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

# 8. ArrayList的addAll(Collection<? extends E> 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倍 容量还是不够，就会扩容到实际元素大小的容量。

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

下面一睹真容。

秀逗：
mixureSecure

四眼：
mixureSecure

大黄：
mixureSecure

三、LinkedList详解