Java ArrayList源码阅读笔记（基于JDK17）

Java ArrayList源码阅读笔记（基于JDK17）

虽然不喜欢看源码，但是据说会让人变强啊，看别的大佬的代码也许才知道怎么处理自己的一坨吧，因此冒着秃顶的风险还是来看看吧。。。
第一遍先简单看看吧，搞不清楚的地方也许会在遥远的将来再复习下吧

1、简介

其实在搞不清楚这玩意儿究竟是什么的情况下，已经稀里糊涂地用它写了好多代码了，而且每当找不到数据结构的时候，口袋里一摸就是ArrayList，所以它到底是个啥？

https://www.runoob.com/java/java-arraylist.html

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素

ArrayList 继承了 AbstractList ，并实现了 List 接口

以上便是比较标准的定义，大概就是一个特殊的数组，可以方便地变大变小

2、类图及类定义

ArrayList继承自AbstractList类，实现了List、RandomAccess、Cloneable、java.io.Serializable接口

• List接口：表明它是一个有序列表，支持添加、删除、查找等操作，并且可以通过下标进行访问
• RandomAccess接口：标记接口，表明实现这个接口的List支持快速随机访问，即直接通过索引下标访问列表的元素
• Cloneable接口：表明支持拷贝操作，支持深拷贝或浅拷贝操作
• java.io.Serializable接口：表明支持序列化操作，可以将对象转换为字节流进行持久化存储或网络传输，非常方便

3、扩容机制

这块经常会被提到，并且所谓“动态”指的也就是这个机制，是该数据结构设计的关键

3.1、构造函数

要看ArrayList怎样进行扩容，那么自然绕不开创建类的实例
以下两个常量，其中DEFAULT_CAPACITY 表示创建ArrayList默认的初始容量10，而EMPTY_ELEMENTDATA 表示的是一个空数组，这是一个共享的空对象数组

// 默认的初始容量 private static final int DEFAULT_CAPACITY = 10; // 共享的空数组实例 private static final Object[] EMPTY_ELEMENTDATA = {}; 

在ArrayList中，有3个构造函数：

• ArrayList()
• ArrayList(int initialCapacity)
• ArrayList(Collection<? extends E> c)

ArrayList()是无参构造，默认会创建一个空对象数组，在第一次添加元素时会扩容到容量10

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

ArrayList(int initialCapacity)构造函数需要指定一个初始容量，依据给定的初始容量的大小，创建不同长度的对象数组，或是抛出异常

public ArrayList(int initialCapacity) { 	if (initialCapacity > 0) {   // 初始容量大于0     	this.elementData = new Object[initialCapacity];     } else if (initialCapacity == 0) {         // 创建空数组         this.elementData = EMPTY_ELEMENTDATA;     } else {         // 小于0抛出异常         throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity);    } } 

ArrayList(Collection<? extends E> c)构造函数可以指定另一个集合对象作为参数，将其转换为对象数组（存在空指针风险），按顺序进行返回

public ArrayList(Collection<? extends E> c) {     Object[] a = c.toArray();  // 存在空指针风险     if ((size = a.length) != 0) {         if (c.getClass() == ArrayList.class) {             elementData = a;         } else {             elementData = Arrays.copyOf(a, size, Object[].class);         }     } else {         // replace with empty array.         elementData = EMPTY_ELEMENTDATA;     } } 

3.2、扩容时机

那么，到底什么时候需要扩容呢，以及怎样进行扩容呢？
接下来，借助ArrayList的add(E e)方法一探究竟

public boolean add(E e) {     modCount++;   // 修改次数加1     add(e, elementData, size);   // 调用重载方法     return true; } 

add(E e)内部又调用了另一个重载方法add(E e, Object[] elementData, int s)，是为了在字节码转化上优化，把方法进行了拆分

/**  * This helper method split out from add(E) to keep method  * bytecode size under 35 (the -XX:MaxInlineSize default value),  * which helps when add(E) is called in a C1-compiled loop.  */ private void add(E e, Object[] elementData, int s) {     if (s == elementData.length)         elementData = grow();   // 长度达到最大，调用grow()扩容     elementData[s] = e;  // 数组索引赋值，并且size+1     size = s + 1; } 

s代表size，用来记录元素的个数，当元素个数达到当前对象数组的长度的时候，就需要进行扩容了，此时会调用grow()方法，扩容后，长度就够应付一阵子了，此时将元素填到对应位置上就可以了，结合前面默认容量为10，可知，第一次扩容将会是在增加第11个元素的时候

3.3、扩容方法

grow()便是用来处理扩容的方法，内部又调用了另一个重载方法，将当前size + 1作为参数

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

oldCapacity 代表的就是旧对象数组的长度，判断其大于0也就是有元素，elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是判断数组元素是否由默认无参构造器初始化
通过ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth)进行扩容
其中oldLength代表的就是旧的数组容量，minGrowth则是最少需要保证的扩容大小，没有富余，prefGrowth则是表示推荐的扩容大小，一般会有富余
oldCapacity >> 1是一个位运算，表示0.5倍的原数组容量，那么对应的含义就是推荐扩容到原数组的1.5倍

 private Object[] grow(int minCapacity) {     int oldCapacity = elementData.length;   // 原来数组的容量     if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {         int newCapacity = ArraysSupport.newLength(oldCapacity,               minCapacity - oldCapacity, /* minimum growth */               oldCapacity >> 1           /* preferred growth */);         return elementData = Arrays.copyOf(elementData, newCapacity);     } else {         return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];     } } 

newLength()是有可能OOM的，如果成功的话就返回扩容后的长度

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {     // preconditions not checked because of inlining     // assert oldLength >= 0     // assert minGrowth > 0      int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow     if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {         return prefLength;     } else {         // put code cold in a separate method         return hugeLength(oldLength, minGrowth);     } } 

Arrays.copyOf(elementData, newCapacity)将原数组依照新的容量进行拷贝

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

最终其实调用的是native的arraycopy()，将源数组src从指定位置srcPos拷贝指定长度length到目标数组dest的destPos位置
最终，实现将数据从旧数组拷贝到扩容后的新数组，返回给elementData
这边应该是浅拷贝，但是引用的对象数组地址肯定变了

public static native void arraycopy(Object src,  int  srcPos,                                     Object dest, int destPos,                                     int length); 

比如我们先创建ArrayList，扔10个数据给它，此时引用的对象数组地址为728，然后再增加一个，触发扩容

新容量计算出来是15，然后创建一个地址在760的新数组，容量为15

拷贝完成后，原来的元素地址没有变，说明仅仅是拷贝了引用，内容没有变，因此拷贝效率比较高，但是elementData的对象数组地址变了

先看这么多，如有问题和不足欢迎指正~~

https://www.runoob.com/manual/jdk11api/java.base/java/util/ArrayList.html
https://javaguide.cn/java/collection/arraylist-source-code.html
https://www.cnblogs.com/KRDecad3/p/17800902.html