共计 8997 个字符，预计需要花费 23 分钟才能阅读完成。
ArrayList 概述
（1）ArrayList 是一种变长的汇合类，基于定长数组实现。
（2）ArrayList 容许空值和反复元素，当往 ArrayList 中增加的元素数量大于其底层数组容量时，其会通过扩容机制从新生成一个更大的数组。
（3）因为 ArrayList 底层基于数组实现，所以其能够保障在 O(1) 复杂度下实现随机查找操作。
（4）ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的异样或谬误。
ArrayList 的成员属性
在介绍对于 ArrayList 的各种办法之前先看一下根底属性成员。其中 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的区别是：当咱们向数组中增加第一个元素时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA 将会晓得数组该裁减多少。
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 默认的空的数组，这个次要是在构造方法初始化一个空数组的时候应用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 应用默认 size 大小的空数组实例，和 EMPTY_ELEMENTDATA 辨别开来，
// 这样能够晓得当第一个元素增加的时候进行扩容至多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList 底层存储数据就是通过数组的模式，ArrayList 长度就是数组的长度。
// 一个空的实例 elementData 为下面的 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当增加第一个元素的时候
// 会进行扩容，扩容大小就是下面的默认容量 DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access
//arrayList 的大小
private int size;
复制代码 static 润饰的 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
ArrayList 构造方法
（1）带有初始化容量的构造方法
参数大于 0，elementData 初始化为 initialCapacity 大小的数组
参数小于 0，elementData 初始化为空数组
参数小于 0，抛出异样
// 参数为初始化容量
public ArrayList(int initialCapacity) {
// 判断容量的合法性
if (initialCapacity > 0) {
//elementData 才是理论寄存元素的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 如果传递的长度为 0，就是间接应用本人曾经定义的成员变量(一个空数组)
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
}}
复制代码（2）无参结构
构造方法中将 elementData 初始化为空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
当调用 add 办法增加第一个元素的时候，会进行扩容
扩容至大小为 DEFAULT_CAPACITY=10
// 无参结构，应用默认的 size 为 10 的空数组，在构造方法中没有对数组长度进行设置，会在后续调用 add 办法的时候进行扩容
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
复制代码（3）参数为 Collection 类型的结构器
// 将一个参数为 Collection 的汇合转变为 ArrayList（实际上就是将汇合中的元素换为了数组的模式）。如果
// 传入的汇合为 null 会抛出空指针异样（调用 c.toArray() 办法的时候）
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {//c.toArray()可能不会正确地返回一个 Object[]数组，那么应用 Arrays.copyOf()办法
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 如果汇合转换为数组之后数组长度为 0，就间接应用本人的空成员变量初始化 elementData
this.elementData = EMPTY_ELEMENTDATA;
}}
复制代码 下面的这些构造方法了解起来比较简单，关注前两个构造方法做的事件，目标都是初始化底层数组 elementData(this.elementData=XXX)。区别在于无参构造方法会将 elementData 初始化一个空数组，插入元素时，扩容将会按默认值从新初始化数组。而有参的构造方法则会将 elementData 初始化为参数值大小（>= 0）的数组。个别状况下，咱们用默认的构造方法即可。假使在可晓得将会向 ArrayList 插入多少元素的状况下，能够应用有参构造方法。
下面说到了应用无参结构的时候，在调用 add 办法的时候会进行扩容，所以上面咱们就看看 add 办法以及扩容的细节
ArrayList 的 add 办法
add 办法大抵流程
// 将指定元素增加到 list 的开端
public boolean add(E e) {
// 因为要增加元素，所以增加之后可能导致容量不够，所以须要在增加之前进行判断（扩容）ensureCapacityInternal(size + 1); // Increments modCount!!（待会会介绍到 fast-fail）elementData[size++] = e;
return true;}
复制代码咱们看到 add 办法中在增加元素之前，会先判断 size 的大小，所以咱们来看看 ensureCapacityInternal 办法的细节
ensureCapacityInternal 办法剖析
private void ensureCapacityInternal(int minCapacity) {
// 这里就是判断 elementData 数组是不是为空数组
//（应用的无参结构的时候，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA）// 如果是，那么比拟 size+1(第一次调用 add 的时候 size+1=1)和 DEFAULT_CAPACITY，// 那么显然容量为 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);}
复制代码 当 要 add 进第 1 个元素时，minCapacity 为 (size+1=0+1=)1，在 Math.max() 办法比拟后，minCapacity 为 10。而后紧接着调用 ensureExplicitCapacity 更新 modCount 的值，并判断是否须要扩容
ensureExplicitCapacity 办法剖析
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 这里就是 add 办法中正文的 Increments modCount
// 溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);// 这里就是执行扩容的办法}
复制代码 上面来看一下扩容的次要办法 grow。
grow 办法剖析
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
private void grow(int minCapacity) {
// oldCapacity 为旧数组的容量
int oldCapacity = elementData.length;
// newCapacity 为新数组的容量（oldCap+oldCap/2: 即更新为旧容量的 1.5 倍）int newCapacity = oldCapacity + (oldCapacity >> 1);
// 查看新容量的大小是否小于最小须要容量，如果小于那旧将最小容量最为数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE，应用 hugeCapacity 比拟二者
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 将原数组中的元素拷贝
elementData = Arrays.copyOf(elementData, newCapacity);}
复制代码 hugeCapacity 办法
这里简略看一下 hugeCapacity 办法
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;}
复制代码 add 办法执行流程总结
咱们用一幅图来简略梳理一下，当应用无参结构的时候，在第一次调用 add 办法之后的执行流程
这是第一次调用 add 办法的过程，当扩容值 capacity 为 10 之后，
持续增加第 2 个元素（先留神调用 ensureCapacityInternal 办法传递的参数为 size+1=1+1=2）
在 ensureCapacityInternal 办法中，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 不成立，所以间接执行 ensureExplicitCapacity 办法
ensureExplicitCapacity 办法中 minCapacity 为刚刚传递的 2，所以第二个 if 判断（2-10=-8）不会成立，即 newCapacity 不比 MAX_ARRAY_SIZE 大，则不会进入 grow 办法。数组容量为 10，add 办法中 return true,size 增为 1。
假如又增加 3、4……10 个元素（其中过程相似，然而不会执行 grow 扩容办法）
当 add 第 11 个元素时候，会进入 grow 办法时，计算 newCapacity 为 15，比 minCapacity（为 10+1=11）大，第一个 if 判断不成立。新容量没有大于数组最大 size，不会进入 hugeCapacity 办法。数组容量扩为 15，add 办法中 return true,size 增为 11。
add(int index,E element)办法
// 在元素序列 index 地位处插入
public void add(int index, E element) {
rangeCheckForAdd(index); // 校验传递的 index 参数是不是非法
// 1. 检测是否须要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 将新元素插入至 index 处
elementData[index] = element;
size++;}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) // 这里判断的 index>size（保障数组的连续性），index 小于 0
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
复制代码 add(int index, E element)办法（在元素序列指定地位（假如该地位正当）插入）的过程大略是上面这些
检测数组是否有足够的空间 (这里的实现和下面的)
将 index 及其之后的所有元素向后移一位
将新元素插入至 index 处.
将新元素插入至序列指定地位，须要先将该地位及其之后的元素都向后挪动一位，为新元素腾出地位。这个操作的工夫复杂度为 O(N)，频繁挪动元素可能会导致效率问题，特地是汇合中元素数量较多时。在日常开发中，若非所需，咱们该当尽量避免在大汇合中调用第二个插入方法。
ArrayList 的 remove 办法
ArrayList 反对两种删除元素的形式
1、remove(int index) 依照下标删除
public E remove(int index) {
rangeCheck(index); // 校验下标是否非法（如果 index>size，旧抛出 IndexOutOfBoundsException 异样）modCount++;// 批改 list 构造，就须要更新这个值
E oldValue = elementData(index); // 间接在数组中查找这个值
int numMoved = size - index - 1;// 这里计算所须要挪动的数目
// 如果这个值大于 0 阐明后续有元素须要左移(size=index+1)
// 如果是 0 阐明被移除的对象就是最初一位元素(不须要挪动别的元素)
if (numMoved > 0)
// 索引 index 只有的所有元素左移一位 笼罩掉 index 地位上的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 挪动之后，原数组中 size 地位 null
elementData[--size] = null; // clear to let GC do its work
// 返回旧值
return oldValue;}
//src: 源数组
//srcPos: 从源数组的 srcPos 地位处开始挪动
//dest: 指标数组
//desPos: 源数组的 srcPos 地位处开始挪动的元素，这些元素从指标数组的 desPos 处开始填充
//length: 挪动源数组的长度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);复制代码 删除过程如下图所示
2、remove(Object o) 依照元素删除，会删除和参数匹配的第一个元素
public boolean remove(Object o) {
// 如果元素是 null 遍历数组移除第一个 null
if (o == null) {for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 遍历找到第一个 null 元素的下标 调用下标移除元素的办法
fastRemove(index);
return true;
}
} else {
// 找到元素对应的下标 调用下标移除元素的办法
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {fastRemove(index);
return true;
}
}
return false;}
// 依照下标移除元素（通过数组元素的地位挪动来达到删除的成果）
private void fastRemove(int index) {
modCount++;
int numMoved = size – index – 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);elementData[–size] = null; // clear to let GC do its work
}
复制代码 ArrayList 的其余办法
ensureCapacity 办法
最好在 add 大量元素之前用 ensureCapacity 办法，以缩小增量从新调配的次数
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);
}}
复制代码 ArrayList 总结
（1）ArrayList 是一种变长的汇合类，基于定长数组实现，应用默认构造方法初始化进去的容量是 10（1.7 之后都是提早初始化，即第一次调用 add 办法增加元素的时候才将 elementData 容量初始化为 10）。
（2）ArrayList 容许空值和反复元素，当往 ArrayList 中增加的元素数量大于其底层数组容量时，其会通过扩容机制从新生成一个更大的数组。ArrayList 扩容的长度是原长度的 1.5 倍
（3）因为 ArrayList 底层基于数组实现，所以其能够保障在 O(1) 复杂度下实现随机查找操作。
（4）ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的异样或谬误。
（5）程序增加很不便
（6）删除和插入须要复制数组，性能差（能够应用 LinkindList）
（7）Integer.MAX_VALUE – 8：次要是思考到不同的 JVM, 有的 JVM 会在退出一些数据头, 当扩容后的容量大于 MAX_ARRAY_SIZE, 咱们会去比拟最小须要容量和 MAX_ARRAY_SIZE 做比拟, 如果比它大, 只能取 Integer.MAX_VALUE, 否则是 Integer.MAX_VALUE -8。这个是从 jdk1.7 开始才有的
fast-fail 机制
fail-fast 的解释：
在零碎设计中，疾速生效零碎一种能够立刻报告任何可能表明故障的状况的零碎。疾速生效零碎通常设计用于进行失常操作，而不是试图持续可能存在缺点的过程。这种设计通常会在操作中的多个点查看零碎的状态，因而能够及早检测到任何故障。疾速失败模块的职责是检测谬误，而后让零碎的下一个最高级别处理错误。
就是在做零碎设计的时候先思考异常情况，一旦产生异样，间接进行并上报，比方上面的这个简略的例子
// 这里的代码是一个对两个整数做除法的办法，在 fast_fail_method 办法中，咱们对被除数做了个简略的查看，如果其值为 0，那么就间接抛出一个异样，并明确提醒异样起因。这其实就是 fail-fast 理念的理论利用。
public int fast_fail_method(int arg1,int arg2){
if(arg2 == 0){throw new RuntimeException("can't be zero");
}
return arg1/arg2;}
复制代码 在 Java 汇合类中很多中央都用到了该机制进行设计，一旦使用不当，触发 fail-fast 机制设计的代码，就会产生非预期状况。咱们通常说的 Java 中的 fail-fast 机制，默认指的是 Java 汇合的一种谬误检测机制。当多个线程对局部汇合进行构造上的扭转的操作时，有可能会触发该机制时，之后就会抛出并发批改异样ConcurrentModificationException. 当然如果不在多线程环境下，如果在 foreach 遍历的时候应用 add/remove 办法，也可能会抛出该异样。参考 fast-fail 机制，这里简略做个总结
之所以会抛出 ConcurrentModificationException 异样，是因为咱们的代码中应用了加强 for 循环，而在加强 for 循环中，汇合遍历是通过 iterator 进行的，然而元素的 add/remove 却是间接应用的汇合类本人的办法。这就导致 iterator 在遍历的时候，会发现有一个元素在本人人不知; 鬼不觉的状况下就被删除 / 增加了，就会抛出一个异样，用来提醒可能产生了并发批改！所以，在应用 Java 的汇合类的时候，如果产生 ConcurrentModificationException，优先思考 fail-fast 无关的状况，实际上这可能并没有真的产生并发，只是 Iterator 应用了 fail-fast 的爱护机制，只有他发现有某一次批改是未通过本人进行的，那么就会抛出异样。
作者：RoadTrip
链接：https://juejin.cn/post/684490…
起源：稀土掘金
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。
