ArrayList源码分析（JDK17）

写在前面:

第一次写源码分析，感觉写起来，不知道从何下手，不过慢慢的也就写完了，也不知道条理怎么样，内容应该还是都说了。希望能对ArrayList的理解有所帮助.
本文通过ArrayList对动态数组的实现/生命周期来进行源码的解析。会列举源码并注释代码的作用。但不会讲述动态数组的实现过程，实现过程在数组–java–动态数组已经写过了

明天在继续写

本文内容包括：

• 源码分析
• 扩容机制
• 迭代器
• 面试题

• 简介

  此类是 Java 集合框架的成员。 ArrayList 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。使用量很大，所以作为第一个进行源码分析的类。

  类层次结构

  继承于AbstractList抽象类
  
  实现了：

  1. List
     有序集合（也称为 序列）的接口
  2. RandomAccess
     标记性接口，使得随机访问比迭代器快
  3. Cloneable
     标记性接口，克隆
     所以重写clone方法完成浅克隆
  4. java.io.Serializable
     标记性接口，序列化

  构造

  ArrayList的构造方法一共有3个
  

  无参构造

  
  elementData代表着的就是存储元素的数组了。
  transient关键字代表着其不能被序列化
  

  注释上写着构造一共初始容量为10的空列表。但是我们打开DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个类查看。很明显，这就是一个空数组，所以最开始的数组大小就是0。
  这个也算是慢初始，因为可能构造了不用，所以设置为空就会减少空间的浪费。
  
  但为什么要这么写呢？
  我们可以看到这样一个属性，我们在扩容的时候用到这个，会导致无参构造扩容后就会是10.而在调用add后动态的初始化。

  

  有参构造

  根据你传入的参数来构建大小，如果为0则会赋值一个空数组(但是这个和无参的不一样)
  

  这个构造先判断传入集合的大小，如果为空则设置为空数组。
  如果不为空则判断是否的ArrayList类，是则直接赋值了，不是则进行拷贝。
  

  添加元素

  add：添加/插入一个元素

  这里和jdk8会不一样
  modCount继承于AbstractList，记录着集合的修改次数
  然后调用了add(E e, Object[] elementData, int s)方法(jdk8直接实现出来了，而不是抽取方法)
  返回一个true代表添加成功
  
  这段代码是很平常的添加代码，有意思的是这个注释。
  查阅资料发现，当方法字节码大小小于35的时候，会进行方法内联
  而这个操作由c1编译器进行。c1编译器(适用于执行时间较短或对启动性能有要求的程序)会比c2要快，所以可以让这个add成为热点，而被优化。
  这个部分应该属于JIT优化。
  

  public void add(int index, E element)

  /**
  在此列表中的指定位置插入指定的元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将一个元素添加到其索引中）。
  形参:
  index – 要插入指定元素的索引 element – 要插入的元素
  抛出:
  IndexOutOfBoundsException – 如果索引超出范围 （index < 0 || index > size()）
  **/public void add(int index, E element) {rangeCheckForAdd(index); // 进行index范围的检查，超出范围会抛出异常modCount++;final int s;Object[] elementData;if ((s = size) == (elementData = this.elementData).length)elementData = grow();//赋值并且检查是否需要扩容System.arraycopy(elementData, index,elementData, index + 1,s - index);// 拷贝插入点前后的元素elementData[index] = element; // 插入点赋值size = s + 1;}
  

  addAll:添加集合中的元素

  扩容

  扩容判断

  if (s == elementData.length)则扩容
  

  这个是扩容的通用代码。
  记录了旧容量后，如果不是默认空数组，或者容量大于0则if成立。
  这里就是默认空数组和其他构造的空数组的区别了：

  如果是默认空数组则走初始容量为10的路线，否则则按照1.5倍扩容走

       /*** 增加容量以确保它至少可以容纳最小容量参数指定的元素数。** @param minCapacity 所需的最小容量* @throws OutOfMemoryError 如果最小容量小于零*/private Object[] grow(int minCapacity) {int oldCapacity = elementData.length;//获取旧容量if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity = ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* 最小增长 */oldCapacity >> 1           /* 首选增长*/);//这个方法会从old的基础上，选取后面2个值的大的来增长。// 也就是，需要的容量和1.5倍比较return elementData = Arrays.copyOf(elementData, newCapacity);//拷贝旧的} else {return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}
  

  而一般性的,就是长度加一，调用上面的方法。

   private Object[] grow() {return grow(size + 1);}
  

  mount与迭代器

  其他常见方法

  //返回此列表中的元素数。
  public int size()//如果此列表不包含任何元素，则返回 true 。
  public boolean isEmpty()//如果此列表包含指定的元素，则返回true。更正式地说，当且仅当此列表包含至少一个元素eObjects.equals(o, e)时，返回 true .
  public boolean contains(Object o)//返回此列表中指定元素第一次出现的索引，如果此列表中不包含该元素，则返回 -1。更正式地说，返回最低索引，例如 Objects.equals(o, get(i))，如果没有这样的索引i，则返回 -1。
  public int indexOf(Object o)//返回此列表中指定元素最后一次出现的索引，如果此列表中不包含该元素，则返回 -1。更正式地说，返回最高索引，如果没有这样的索引iObjects.equals(o, get(i))，则返回 -1。public int lastIndexOf(Object o)

  不常见方法

  //将此实例的容量修剪为列表的 ArrayList 当前大小。
  public void trimToSize()  //如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳最小容量参数指定的元素数。
  //形参:minCapacity – 所需的最小容量
  public void ensureCapacity(int minCapacity) //浅克隆
  public Object clone();

  不常见方法的源码和小介绍

  这是一个缩小空间的方法，把未使用的数组删掉。
  这个方法在ArrayList里面没有调用，但是在其他地方优化的时候还挺多的。
  

      /*** 将此实例的容量修剪为列表的 ArrayList 当前大小。* 应用程序可以使用此操作来最小化实例的 ArrayList 存储*/public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}
  

  没有调用的

  public void ensureCapacity(int minCapacity) {if (minCapacity > elementData.length&& !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA&& minCapacity <= DEFAULT_CAPACITY)) {modCount++;grow(minCapacity);}}
  

  	public Object clone() {try {ArrayList<?> v = (ArrayList<?>) super.clone();v.elementData = Arrays.copyOf(elementData, size);v.modCount = 0;return v;} catch (CloneNotSupportedException e) {// this shouldn't happen, since we are Cloneablethrow new InternalError(e);}}
  

  常见方法的源码和小介绍

  把这个放后面呢是因为简单应该看的人少。

  public int size() {return size;}

   public boolean isEmpty() {return size == 0;}
  

  public boolean contains(Object o) {return indexOf(o) >= 0;}
  

  	 public int indexOf(Object o) {return indexOfRange(o, 0, size);}int indexOfRange(Object o, int start, int end) {Object[] es = elementData;if (o == null) {for (int i = start; i < end; i++) {if (es[i] == null) {return i;}}} else {for (int i = start; i < end; i++) {if (o.equals(es[i])) {return i;}}}return -1;}
  

  	public int lastIndexOf(Object o) {return lastIndexOfRange(o, 0, size);}int lastIndexOfRange(Object o, int start, int end) {Object[] es = elementData;if (o == null) {for (int i = end - 1; i >= start; i--) {if (es[i] == null) {return i;}}} else {for (int i = end - 1; i >= start; i--) {if (o.equals(es[i])) {return i;}}}return -1;}
  

  积累面试题

  ArrayList是什么？可以用来干嘛？

  ArrayList是个动态数组，实现List接口，主要用来存储数据，只存储包装类。它的特点是：
  增删慢：每次删除元素，都需要更改数组长度、拷贝以及移动元素位置。
  查询快：由于数组在内存中是一块连续空间，因此可以根据地址+索引的方式快速获取对应位置上的元素。
  

  ArrayList 的默认长度

  在jdk8以前和jdk8以后稍有不同
  jdk8以前：创建就会初始数组长度，长度为10
  jdk8及以后：是懒加载，初始的时候为空数组，在第一次添加元素的时候扩容为10
  

  ArrayList如何扩容

  定好容量后，定好会把原来的数组元素拷贝到新数组中，再把指向原数的地址换到新数组。
  这个有2种扩容机制
  对于无参构造的集合：在第一次添加元素的时候会扩容到10，存满后按照1.5倍的进行扩容。如果一次添加了多个元素1.5倍放不下，则会按照实际需要的大小进行扩容。
  对于其他的构造：就没有扩容10的步骤了，按照max(1.5倍，实际大小)
  

  ArrayList频繁扩容导致性能下降该怎么办

  这时候我们可以估算需要的容量，使用
  ArrayList(int capacity)的有参构造来指定容量的空列表
  

  在测试中甚至有几个下图这样这样的比例运行了
  
  
  

  什么情况下你会使用ArrayList？什么时候你会选择LinkedList？

  多数情况下，当你遇到访问元素比插入或者是删除元素更加频繁的时候，你应该使用ArrayList。
  另外一方面，当你在某个特别的索引中，插入或者是删除元素更加频繁，或者你压根就不需要访问元素的时候，你会选择LinkedList。
  这里的主要原因是，在ArrayList中访问元素的最糟糕的时间复杂度是”1″，
  而在LinkedList中可能就是”n”了。
  在ArrayList中增加或者删除某个元素，通常会调用System.arraycopy方法，这是一种极为消耗资源的操作，因此，在频繁的插入或者是删除元素的情况下，LinkedList的性能会更加好一点。
  

  ArrayList的插入或删除一定比LinkedList慢吗

  大多数是的，但是不一定.
  如果删除靠前的元素arraylist需要拷贝后面的元素
  如果靠中间或者靠后，linkedlist找元素需要消耗很多的时间，而arraylist拷贝的元素会少一些
  arraylist取数真的太快了，linkedlist就算能从后面找，就算是取最后一个数，也慢了很多
  

  数组长度n=10000
  a=100
  b=n-a
  c=n/2
  可以看到：

  随机向中间添加，arraylist快
  add方法添加到最后，linkedlist完胜
  随机删除Arraylist快
  删除靠前元素：linkedlist快
  删除中间的，arralist快
  删除后面的，arralist快
  

  TestArrayList.testArrayListRandonAdd          thrpt    2    12289.462          ops/s
  TestArrayList.testLinkedListRandonAdd         thrpt    2    11362.013          ops/s
  TestArrayList.testArrayListRandonAddLast      thrpt    2    12820.688          ops/s
  TestArrayList.testLinkedListRandonAddLast     thrpt    2  2482660.154          ops/s
  TestArrayList.testArrayListRandonRemove       thrpt    2   207213.498          ops/s
  TestArrayList.testLinkedListRandonRemove      thrpt    2    11402.369          ops/s
  TestArrayList.testArrayListRemove100          thrpt    2   110029.496          ops/s
  TestArrayList.testLinkedListRemove100         thrpt    2  1036584.680          ops/s
  TestArrayList.testArrayListRemoveNDividing2   thrpt    2   205019.017          ops/s
  TestArrayList.testLinkedListRemoveNDividing2  thrpt    2     6156.114          ops/s
  TestArrayList.testArrayListRemoveN_100        thrpt    2  2064240.192          ops/s
  TestArrayList.testLinkedListRemoveN_100       thrpt    2  1072619.806          ops/s
  

  
  
  接下来下调参数
  n=1000
  a=10
  b=n-a
  c=n/2

  随机向中间添加，linkedlist快
  add方法添加到最后，linkedlist完胜
  随机删除Arraylist快
  删除靠前元素：linkedlist快
  删除中间的，arralist快
  删除后面的，linkedlist快
  

  Benchmark                                     Mode  Cnt  Score   Error  Units
  TestArrayList.testArrayListRandonAdd          avgt       0.912          us/op
  TestArrayList.testLinkedListRandonAdd         avgt       0.423          us/op
  TestArrayList.testArrayListRandonAddLast      avgt       0.788          us/op
  TestArrayList.testLinkedListRandonAddLast     avgt       0.042          us/op
  TestArrayList.testArrayListRandonRemove       avgt       0.194          us/op
  TestArrayList.testLinkedListRandonRemove      avgt       0.418          us/op
  TestArrayList.testArrayListRemove100          avgt       0.211          us/op
  TestArrayList.testLinkedListRemove100         avgt       0.043          us/op
  TestArrayList.testArrayListRemoveNDividing2   avgt       0.189          us/op
  TestArrayList.testLinkedListRemoveNDividing2  avgt       0.722          us/op
  TestArrayList.testArrayListRemoveN_100        avgt       0.151          us/op
  TestArrayList.testLinkedListRemoveN_100       avgt       0.039          us/op