𝙁𝙡𝙖𝙨𝙝

ArrayList

约 6045 字大约 20 分钟

2025-01-15

概述

  1. ArrayList 的底层是数组队列，相当于动态数组。

  2. 与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。

  3. ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。

    public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
}
    • List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
    • RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
    • Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
    • Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便

ArrayList 类图

ArrayLisy 和 Vector 的区别

  1. ArrayList 是 List 的主要实现类，底层使用 Object[]存储，适用于频繁的查找工作，线程不安全 。
  2. Vector 是 List 的古老实现类，底层使用Object[] 存储，线程安全。

底层源码

以 JDK1.8 为例，分析一下 ArrayList 的底层源码：

ArrayList 存储机制

构造函数

ArrayList 有三种方式来初始化，构造方法源码如下（JDK8）：

以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。 下面在我们分析 ArrayList 扩容时会讲到这一点内容！

补充：JDK6 new 无参构造的 ArrayList 对象时，直接创建了长度是 10 的 Object[] 数组 elementData 。

add()方法

  • add()源码：
/**
* 将指定的元素追加到此列表的末尾。
*/
public boolean add(E e) {
    // 加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
  • ensureCapacityInternal()源码：
// 根据给定的最小容量和当前数组元素来计算所需容量。
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果当前数组元素为空数组（初始情况），返回默认容量：10和最小容量中的较大值作为所需容量
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 否则直接返回最小容量
    return minCapacity;
}

// 确保内部容量达到指定的最小容量。
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

ensureCapacityInternal 方法非常简单，内部直接调用了 ensureExplicitCapacity 方法：

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {	//mminCapacity为最小所需容量
    modCount++;
    //判断当前数组容量是否足以存储minCapacity个元素			//数组位置不足
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容
        grow(minCapacity);
}

新增元素大体流程

  • 当我们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法 ，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
  • 当 add 第 2 个元素时，minCapacity 为 2，此时 elementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0 不成立，所以不会进入 （执行）grow(minCapacity) 方法。
  • 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。

直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容

ArrayList 扩容机制

grow()方法

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！ 奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

  • 例子：
    • 当 add 第 1 个元素时，oldCapacity 为 0，经比较后第一个 if 判断成立（扩容后的数组容量还是小于所需容量），newCapacity = minCapacity(为 10)。但是第二个 if 判断不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 hugeCapacity 方法。数组容量为 10，add 方法中 return true,size 增为 1。
    • 当 add 第 11 个元素进入 grow 方法时，newCapacity 为 15，比 minCapacity（为 11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 方法。数组容量扩为 15，add 方法中 return true,size 增为 11。
    • 以此类推······

hugeCapacity()方法

从上面 grow() 方法源码我们知道：如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 对minCapacity和MAX_ARRAY_SIZE进行比较
    // 若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    // 若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

区分 System.arraycopy()和 Arrays.copyOf()

阅读源码的话，我们就会发现 ArrayList 中大量调用了这两个方法。比如：我们上面讲的扩容操作以及add(int index, E element)、toArray() 等方法中都用到了该方法！

System.arraycopy()

  • 源码：
	// 我们发现 arraycopy 是一个 native 方法,接下来我们解释一下各个参数的具体意义
	/**
    *   复制数组
    * @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);
  • 场景：
  • 结果：
0 1 99 2 3 0 0 0 0 0

Arrays.copyOf()

  • 源码：
    public static int[] copyOf(int[] original, int newLength) {
      // 申请一个新的数组
        int[] copy = new int[newLength];
  // 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
  • 场景：
   /**
     以正确的顺序返回一个包含此列表中所有元素的数组（从第一个到最后一个元素）; 返回的数组的运行时类型是指定数组的运行时类型。
     */
    public Object[] toArray() {
    //elementData：要复制的数组；size：要复制的长度
        return Arrays.copyOf(elementData, size);
    }

使用 Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：

public class ArrayscopyOfTest {

  public static void main(String[] args) {
    int[] a = new int[3];
    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    int[] b = Arrays.copyOf(a, 10);
    System.out.println("b.length"+b.length);
  }
}
  • 结果：
10

两者联系和区别

  • 联系：Arrays.copyOf()内部实际调用了 System.arraycopy() 方法
  • 区别：
    • System.arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组
    • 而且可以选择拷贝的起点和长度以及放入新数组中的位置
    • Arrays.copyOf() 是系统自动在内部新建一个数组，并返回该数组。

ensureCapacity()

ArrayList 源码中有一个 ensureCapacity 方法，这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的，那么这个方法有什么作用呢？

理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数

  • 测试 1：
public class EnsureCapacityTest {
  public static void main(String[] args) {
    ArrayList<Object> list = new ArrayList<Object>();
    final int N = 10000000;
    long startTime = System.currentTimeMillis();
    for (int i = 0; i < N; i++) {
      list.add(i);
    }
    long endTime = System.currentTimeMillis();
    System.out.println("使用ensureCapacity方法前："+(endTime - startTime));

  }
}
  • 运行结果：
使用ensureCapacity方法前：2158
  • 测试 2：
public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}
  • 运行结果：
使用ensureCapacity方法后：1773

通过运行结果，我们可以看出向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过，这个性能差距几乎可以忽略不计。而且，实际项目根本也不可能往 ArrayList 里面添加这么多元素。

思考小结

  1. 存储的对象：存储不唯一、有序的对象，对象只能为引用类型，不能为基本数据类型
  2. 底层数据结构：动态数组，可自动扩容
  3. null 值问题：可以存储 null 值，但没意义
  4. 线程安全问题：不安全
  5. 快速访问问题：由于实现了 RandomAccess 接口，所以支持通过下标实现快速访问

ArrayList 的存储、扩容机制

  1. ArrayList 的默认初始化容量为 10，初始化 ArrayList 对象赋值的是一个空数组，当添加第一个元素时，才将数组扩容为 10
  2. ArrayList 扩容时，新数组的容量为旧数组的 1.5 倍（若扩容后的新数组容量仍小于 minCapacity，则直接使用 minCapacity 作为新数组容量）
  3. 新旧数组怎么完成元素转移：Arrays.copyOf(elementData, newCapacity)；elementData 为旧数组对象，newCapacity 为新数组容量；底层调用了 System.arraycopy()方法，该方法可以指定旧数组和新数组的起始位置、以及容量

版权所有

版权归属：haipeng-lin

许可证：署名 4.0 国际 (CC-BY-4.0)

贡献者: haipeng-lin

欢迎光临小破站！粤ICP备2025360098号-1

© Copyright 2024-2026 All Rights Reserved. 版权所有：𝙁𝙡𝙖𝙨𝙝