ArrayList底层结构和源码分析笔记
ArrayList底层结构和源码分析笔记
参考视频：
ArrayList特点
ArrayList 可以加入 null，包括多个。
ArrayList 是由数组来实现数据存储的
ArrayList 基本等同于 Vector，除了 ArrayList 是线程不安全（执行效率高）。在多线程情况下，不建议使用 ArrayList
- 例如 ArrayList 的 add() 的源码：可以发现没有 synchronized 关键词修饰
public boolean add(E e) { modCount++; add(e, elementData, size); return true; }
ArrayList 源码分析（重难点🚩）
ArrayList 中维护了一个 Object 类型的数组 elementData
transient意为短暂的；表示该属性不会被序列化transient Object[] elementData;当创建对象时，如果使用的是无参构造器，则初始 elementData 容量为 0 (jdk7是10)
当添加元素时：先判断是否需要扩容，如果需要扩容，则调用 grow 方法，否则直接添加元素到合适位置
如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容 elementData 为 10，如果需要再次扩容的话，则扩容 elementData 为 1.5 倍。
如果使用的是指定容量大小的构造器，则初始 elementData 容量为指定大小
如果使用的是指定容量大小的构造器，如果需要扩容，则直接扩容 elementData 为 1.5 倍。
[[ArrayList源码分析]]
源码示例
未指定初始容量
注意将 idea 的调式工具设置一下，以便更好的观察数据：
测试源码：
- 观察调用构造器，创建 ArrayList 的实例的细节
- 观察第一次添加元素（初次扩容）
- 观察第二次添加元素（不用扩容）
- 观察第十一次添加元素（第二次扩容）
- 观察第十六次添加元素（第三次扩容）
@Test public void test1(){ ArrayList list = new ArrayList(); for (int i = 11; i <= 20; i++) { list.add(i); } for (int i = 21; i < 26; i++) { list.add(i); } list.add(100); list.add(200); list.add(null); System.out.println(list); }
创建 ArrayList 实例
创建一个长度为 0 的空数组，并赋给 elementData，elementData 就是集合底层存储数据的数组。
第一次添加元素“11”
将 int 数据进行装箱
添加这个数据“11”，要保证数组的长度至少为当前元素数+1。 （size+1=1）
ensureCapacityInternal()的作用就是检查数组够不够此次添加所需的容量，如果不够，则扩容，更改 elementData ，将其用扩容后的数组替代。calculateCapacity()的作用仅仅在于，检查当前操作是否是第一次添加数据。因为第一次添加元素，扩容机制应该将其扩容到 10（除非要添加的元素本身需要的容量大于 10）。而对于非第一次添加的元素，其所需容量依旧是传进来的参数
那么根据判断，此次显然是第一次添加元素，数组为空数组，且所需容量 var1=1，<10。那么此时 var0=10 ，这就确定了最终数组所需要的容量大小。作为参数传递给
ensureExplicitCapacity()中。modCount 为当前集合被修改的次数。需要自增。
最后进行检查：目前数组的容量（
elementData.length）是否满足所需要的容量大小（var1）呢？显然，目前的数组大小为 0，而我们所需要的容量为 10。所以需要扩容。进入到
grow()中，进行真正的扩容操作。所需的容量大小为 var1=10，作为参数传递进来。
var2=数组目前的容量==（var2=0）==
var3=扩容为当前数组容量的 1.5 倍，不过在初次扩容中，此次操作不起作用==（var3=0）==
判断扩容后的容量大小 var3 是否满足，所需的大小 var1，不满足则依照 var1。 （var3=10）
判断扩容后的容量是否在数组的取值范围内。
Arrays.copyOf()：创建一个指定长度的数组==（10）==的数组，并将原数组中的数据拷贝至该数组，并赋值给elementData。至此，数组的扩容完成（elementData.length 从 0 扩容到 10）回到 add 的主逻辑中：
添加元素“11”添加到数组 elementData[0]中，并且 size=1；
第二次添加元素“12”（不用扩容）
将 int 数据进行装箱
添加这个数据“12”，要保证数组的长度至少为当前元素数+1。 （size+1=2）
ensureCapacityInternal()的作用就是检查数组是否大于等于 2（够不够此次添加所需的容量）。如果不够，则扩容，更改 elementData ，将其用扩容后的数组替代。此时由于不是第一次添加，数组长度不为 0，所以
calculateCapacity()执行后返回 2 。集合修改次数+1
当前数组长度==（elementData.length=10） 满足所需长度 (var1=2)==，所以不需要扩容。
回到主逻辑中：
elementData[1]存放 var1。size 变为 2。
观察第十一次添加元素（第二次扩容）
此时数组容量为 elementData.length=10 ，所需容量大小为 var1=11 ，在这一步时，容量不够，所以需要进行扩容，进入
grow()。var2=10，var3=15（扩容 1.5 倍）
同理，后面每一次添加和扩容都与以上的步骤一致。
指定初始容量
与未指定的区别在于，调用的是带参的构造器。
指定了初始容量 var1，则创建一个初始容量为 var1 的数组。如果本身为 0，就仍旧赋值为空数组（与无参的一致）
在之后的扩容中，依旧是按照 1.5 倍扩容。
例如指定初始容量为 8，则初次扩容为 8->12
