【Java 集合】这次真的从0到1彻底吃透ArrayList底层实现源码！

2022-7-16

文章较长，希望你能耐心阅读！相信你能够受益匪浅

0、ArrayList简介

ArrayList是 Java 集合 List 的一个实现类，List 是一个接口，其实现类除 ArrayList 之外，还有 LinkedList，并继承了 Collection，ArrayList集合很常用，同时也是程序员面试时经常会被问到的知识点，下面是结构图：

实现了 Serializable 接口，表明它支持序列化。
实现了 Cloneable 接口，表明它支持克隆，可以调用超类的 clone()方法进行浅拷贝。
实现了RandomAccess 接口：这是个标记接口，表明该类可随机访问。
继承了 AbstractList 抽象类，在他们的抽象父类中，都提供了equals() 方法和 hashCode() 方法。它们自身并不实现这两个方法。
实现了 List 接口，表明该容器类可以存放相同的元素，并且能够保证元素的有序。

ArrayList的主要特点可以总结如下：

ArrayList是可以动态增长和缩减的索引序列，它是基于Object[] 数组实现的List类。
该类封装了一个动态再分配的Object[] 数组，每一个类对象都有一个capacity属性，表示它们所封装的Object[]数组的长度，当向ArrayList中添加元素时，该属性值会自动增加。如果想ArrayList中添加大量元素，可使用ensureCapacity方法一次性增加capacity，可以减少增加重分配的次数提高性能。
ArrayList的用法和Vector相类似，但是Vector是一个较老的集合，具有很多缺点，不建议使用。另外，ArrayList和Vector的区别是：ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的。
ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList 类。
ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

增删慢：每次删除元素，都需要更改数组的长度，拷贝以及移动元素的位置

查询快：由于数组在内存中是一块连续的空间，因此可以根据索引快速获取某个位置上的元素。

1、ArrayList底层数据结构

通过观察源代码可以看到ArrayList底层是基于一个Object[] 数组实现的。代码如下：

transient Object[] elementData; // non-private to simplify nested class access

一个对象只要实现了Serilizable接口，这个对象就可以被序列化，java的这种序列化模式为我们提供了很多便利，我们可以不必关心具体序列化的过程，只要这个类实现了Serilizable接口，这个类的所有属性和方法都会自动序列化。

但是我们常常会遇到这样的问题，这个类的有些属性需要序列化，而其他属性不需要被序列化，这时transient关键字为我们提供了便利，你只需要实现Serilizable接口，将不需要序列化的属性前添加关键字transient，序列化对象的时候，这个属性就不会序列化到指定的目的地中。

1）一旦变量被transient修饰，变量将不再是对象持久化的一部分，该变量内容在序列化后无法获得访问。

2）transient关键字只能修饰变量，而不能修饰方法和类。注意，本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量，则该类需要实现Serializable接口。

3）被transient关键字修饰的变量不再能被序列化，一个静态变量不管是否被transient修饰，均不能被序列化。

数据结构图

说明：底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。

优点

由于底层实现是基于数组，支持随机访问，查找效率为O(1)

1、可以根据下标遍历元素效率较高。

2、可以根据下标访问元素效率较高。

3、在数组的基础上封装了对元素操作的方法。

4、可以自动扩容。

缺点

插入和删除操作需要移动所有受影响的元素，效率相对较低

1、插入和删除的效率比较低。

2、根据内容查找元素的效率较低。

适用场景

根据ArrayList的底层数据结构特点，ArrayList一般适用于查询多，增删操作少的场景下。

2、底层源码分析

0.成员变量

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 版本号 序列化相关，Java序列化的机制是通过判断类的serialVersionUID来验证的版本一致的
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 实际存储元素数组
    transient Object[] elementData;
    // 实际元素大小，默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

1.构造方法

无参构造

// 用法
ArrayList<String> list = new ArrayList<>();

// 源码
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

当我们使用一个无参的 ArrayList构造方法创建的时候，内部使用了一个空的数组赋值给了用于保存数据的数组。

指定初始容量

// 用法
ArrayList<String> list = new ArrayList<>(6);

// 源码
public ArrayList(int initialCapacity) {
  // 如果指定初始容量大于 0，则将按照指定容量初始化elementData数组
  if(initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  }
  // 如果指定初始容量等于 0，则将按照默认容量初始化elementData数组
  else if(initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  }
  // 如果指定初始容量小于 0 抛出IllegalArgumentException异常
  else {
    throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  }
}

该构造函数可以传入一个 int 值，如果该值大于 0，则创建一个长度为该值的数组；如果该值等于 0，则使用一个空数组；如果该值小于 0，则抛出IllegalArgumentException异常。

指定一个集合

// 用法
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("YJS");
ArrayList<String> list = new ArrayList<>(arrayList);

// 源码
public ArrayList(Collection <? extends E > c) {
  // 将参数集合转换成数组并且赋值给elementData数组
  elementData = c.toArray();
  // 将elementData的长度赋值给成员变量size，如果参数集合元素不为空
  if((size = elementData.length) != 0) {
    // 数组的创建和拷贝
    if(elementData.getClass() != Object[].class) 
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  }
  // 如果传入的集合为空，则将使用默认空数组
  else {
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

该构造函数可以传入一个 Collection，将传入的集合转换为数组，然后将该数组赋值给成员变量elementData，将elementData的长度赋值给成员变量 size，判断是否不等于 0 ，如果传入的集合中有元素该判断是成立的，然后再判断elementData.getClass() != Object[].class，成立则将会进行数组的创建和拷贝。如果等于零则将EMPTY_ELEMENTDATA赋值给 elementData。

2.添加元素原理分析

示例源码

我这里使用的是无参构造器创建的ArrayList集合，也就是说初始容量为空。

public static void main(String[] args) {
    ArrayList arrayList = new ArrayList();
    arrayList.add(0);
    arrayList.add("java");
    arrayList.add("yjs");
    System.out.println("arrayList= " + arrayList);
}

初始化ArrayList

ArrayList arrayList = new ArrayList();执行后，会自动调用ArrayList的无参构造方法。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

调用add(E e) 方法

在每次添加数据时，如果数据是基本数据类型，会先将基本数据类型进行装箱操作，把基本数据类型转换成对应的包装类型（引用数据类型）,最终add(E e) 会向数组末尾添加一个元素。

/**
 * 将基本数据类转换为引用数据类型
 * @param  i 	传入的参数为一个基本型数据类型
 * @return 		返回的参数是一个基本数据类型的包装类（引用数据类型）
 */
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

如果是引用数据类型的话会直接去调用ArrayList的add(E e)方法，源码如下：

public boolean add(E e) {
    // 确保数组已使用长度（size）加1之后足够存下 下一个数据
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 数组的下一个位置存放传入元素,同时将size后移
    elementData[size++] = e;
    // 始终返回true
    return true;
}

调用ensureCapacityInternal(size + 1);方法，该方法的作用是确保数组的长度加1后内存是充足的，就是说保证能够数组还能存放一个元素。

ensureCapacityInternal()

ensureCapacityInternal(int minCapacity)方法保证存在剩余空间存放要添加的元素。

/**
	1、如果调用的是空参数构造函数：比较初始容量和所需最小容量的大小，并返回较大的
	2、如果调用的带参数构造函数：直接返回最小容量(size+1)
**/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    /**
    	如果ArrayList创建对象时调用的是空参数构造函数：
    	第一次调用add()方法添加元素时：会在这儿将数组的容量初始化为10
    	随后调用add()方法添加元素时：会比较添加该元素所需的最小容量minCapacity和10的大小，返回大的	 
    */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	/**
		如果ArrayList创建对象时调用的为带参构造函数：直接返回最小容量minCapacity = size+1
	*/
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果 minCapacity(即size+1当前需要的最小容量) > elementData.length(数组的容量),需要扩容
    // 使得存在剩余的数内存存放要添加的元素
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

调用calculateCapacity(elementData, minCapacity)计算添加一个元素所需的最小容量minCapacity；根据ArrayList创建对象时使用的构造方法分为两种情况：

如果使用空参数构造函数创建ArrayList对象，会在第一次调用add()方法添加元素时，将数组的容量初始化为10，随后每次调用add()方法添加元素时都会比较初始容量10与minCapacity的大小，并返回大的容量。

如果使用带参构造函数创建ArrayList对象，会直接但是minCapacity。

调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));该方法就是ensureCapacityInternal(size + 1)方法的底层，其作用是确保数组的长度加1后内存是充足的，就是说保证能够数组还能存放一个元素。

若添加一个元素所需的最小容量minCapacity大于数组的长度if (minCapacity - elementData.length > 0)那么就需要扩容，此时就会调用扩容方法：grow(int minCapacity)

grow()

这个方法完成了ArrayList()集合进行扩容的真正实现，源码如下：

private void grow(int minCapacity) {
    // 获取数组原有的容量
    int oldCapacity = elementData.length;
    
    // 扩容1.5倍（将数组的容量扩容1.5倍）
    // 进行右移一位，也就是除 2的 1 次方
    // 假如 oldCapacity 现在为 12 
    // newCapacity = 12 + (12/2) = 18
    // 也可以理解新容量为 为旧的容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果扩展为1.5倍后还不满足需求,则直接扩展为需求值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 检查扩容后的容量是否大于最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 申请一块更大内存容量的数组，将原来数组中的元素挪到这个新数组中，同时将elementData指向这个新数组
    // 原来的旧的数组由于没有引用变量指向他，就会被垃圾回收机制回收掉
    elementData = Arrays.copyOf(elementData, newCapacity);
}

调用 grow(int minCapacity)方法，该方法会对数组容量进行扩容。

在扩容时会申请一块更大内存容量的数组，将原来数组中的元素拷贝到这个新的数组中，同时让elementData指向该数组，而原来的数组由于没有新的指针指向它，就会被垃圾回收机制回收。

在扩容时，首先考虑扩容1.5倍（如果扩容的太大，可能会浪费更多的内存，如果扩容的太小，又会导致频繁扩容，申请数组拷贝元素等对添加元素的性能消耗较大，因此1.5倍刚好）。如果扩容1.5倍还是内存不足，就会直接扩容到添加元素所需的最小的容量。同时不能超过数组的最大容量Integer.MAX_VALUE - 8。

hugeCapacity()

// 用来赋最大值。
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。
    // Integer.MAX_VALUE:2147483647   MAX_ARRAY_SIZE：2147483639  也就是说最大也就能给到第一个数值。还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

总结

3、其他方法源码分析

1.add(int index, E element)

向数组的指定位置添加元素。

public void add(int index, E element) {
    // 首先判断索引是否越界
    rangeCheckForAdd(index);

    // 确保数组size+1之后能够存下 下一个数据
    ensureCapacityInternal(size + 1); 

    /**
    	源数组 elementData 从传入形参index处开始复制，复制size-index个元素
    	目标数组 elementData 从index+1处开始粘贴，粘贴从源数组赋值的元素
    **/
    System.arraycopy(elementData, index, elementData, index + 1,size - index);

    // 把index处的元素替换成新的元素。
    elementData[index] = element;

    // 将size后移
    size++;
}

// 判断索引是否越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 这是一个本地方法，由C语言实现。
public static native void arraycopy(Object src,  // 源数组
                                    int  srcPos, // 源数组要复制的起始位置
                                    Object dest, // 目标数组（将原数组复制到目标数组）
                                    int destPos, // 目标数组起始位置
                                    int length   // 复制源数组的长度
                                   );

2.set(int index, E element)

设置index位置处的元素。

public E set(int index, E element) {
    // 检查下标是否越界
    rangeCheck(index);
	
    //记录index位置处的旧值
    E oldValue = elementData(index);
    //将数组index索引处的元素设置为新值element
    elementData[index] = element;
    //返回旧值
    return oldValue;
}

//判断索引越界
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

3.get(int index)

获取指定索引位置处的元素。

public E get(int index) {
    //判断索引越界
    rangeCheck(index);
    //返回指定索引位置处的元素
    return elementData(index);
}

4.remove(int index)

删除指定索引位置的数组元素。

//删除该列表中指定位置的元素,将所有后续元素转移到前边（将其中一个元素从它们中减去指数)
public E remove(int index) {
    //判断索引越界
    rangeCheck(index);

    modCount++;
    //获取index位置处的旧值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        /**
            源数组 elementData 从传入形参index+1处开始复制，复制size-index-1个元素
            目标数组 elementData 从index处开始粘贴，粘贴从源数组赋值的元素
        */
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //将size减1指向最后一个元素位置，再将最后一个位置清空
    elementData[--size] = null; 

    return oldValue;
}

// 这是一个本地方法，由C语言实现。
public static native void arraycopy(Object src,  // 源数组
									int  srcPos, // 源数组要复制的起始位置
                                    Object dest, // 目标数组（将原数组复制到目标数组）
                                    int destPos, // 目标数组起始位置
                                    int length   // 复制源数组的长度
                                    );

4、常见面试题

1.说一说 ArrayList。

ArrayList是List接口的常用实现类，并且是容量可变的线程不安全列表，底层使用Object[]数组实现，支持对元素的快速随机访问，但插入与删除速度很慢。集合扩容时会创建更大的数组，把原有数组复制到新数组。ArrayList 实现了 RandomAccess 标记接口，如果一个类实现了该接口，那么表示使用索引遍历比迭代器更快。

通过查看源码可以发现实际上 RandomAccess 接口中什么都没有定义。所以， RandomAccess 接口不过是一个标识罢了。标识实现这个接口的类具有随机访问功能，也就是表示使用索引遍历比迭代器更快。

具体应用比如在 binarySearch() 方法中，它要判断传入的 list 是否 RamdomAccess 的实例，如果是，调用indexedBinarySearch()方法，如果不是，那么调用iteratorBinarySearch()方法。

elementData是 ArrayList 的数据域，被 transient 修饰，序列化时会调用 writeObject 写入流，反序列化时调用 readObject 重新赋值到新对象的 elementData。原因是 elementData 容量通常大于实际存储元素的数量，所以只需发送真正有实际值的数组元素。

size 是当前实际大小，elementData 大小大于等于 size。

modCount记录了 ArrayList 结构性变化的次数，继承自 AbstractList。所有涉及结构变化的方法都会增加该值。expectedModCount 是迭代器初始化时记录的 modCount 值，每次访问新元素时都会检查 modCount 和 expectedModCount 是否相等，不相等就会抛出异常。这种机制叫做 fail-fast，所有集合类都有这种机制。

2.ArrayList 和 LinkedList 的区别

底层数据结构

ArrayList 底层使用的是 Object[] 数组，存储空间是连续的；LinkedList 底层使用的是双向链表数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。）存储空间是不连续的。
插入和删除是否受元素位置的影响
- ArrayList 底层采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
- LinkedList 底层采用链表存储，所以，如果是在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst() 、 removeLast()），近似 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)）时间复杂度近似为 O(n) ，因为需要先移动到指定位置再插入。
  - 对于随机访问get 和 set ，ArrayList 优于 LinkedList，因为 LinkedList 要移动指针。
  - 对于新增和删除操作 add 和 remove ，LinedList 比较占优势，因为 ArrayList 要移动数据。
是否支持快速随机访问

LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
是否保证线程安全

ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
内存空间占用

ArrayList 的空间浪费主要体现在在List列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

同样的数据量 LinkedList 所占用空间可能会更小，因为 ArrayList 需要预留空间便于后续数据增加，而 LinkedList 增加数据只需要增加一个节点。

3.Arraylist 和 Vector 的区别

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

4.简单说一下ArrayList的扩容

扩容可分为两种情况：

第一种情况，当ArrayList的容量为0时，此时添加元素的话，需要扩容，三种构造方法创建的ArrayList在扩容时略有不同：

1.无参构造，创建ArrayList后容量为0，添加第一个元素后，容量变为10，此后若需要扩容，则正常扩容。

2.传容量构造，当参数为0时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。

3.传列表构造，当列表为空时，创建ArrayList后容量为0，添加第一个元素后，容量为1，此时ArrayList是满的，下次添加元素时需正常扩容。