源码分析路线图：
初级部分：ArrayList->LinkedList->Vector->HashMap(红黑树数据结构，如何翻转，变色，手写红黑树)->ConcurrentHashMap
中级部分：Spring->Spring MVC->Spring Boot->Mybatis核心类源码
高级部分：中间件源码（有生之年系列）
第一篇，从最简单的ArrayList入手分析
1、成员变量
集合的初始容量：
private static final int DEFAULT_CAPACITY = 10;下面两个成员变量都是Object类型的空数组，区分在于变量名，是用于区别通过何种构造方法创建了ArrayList集合，后面会提到。
private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};elementData用于存放集合中元素的数组（ArrayList的底层本质上也是数组）
为什么要用transient修饰？我们首先简单复习一下transient关键字的作用：
字段声明为 transient表示该字段不会被序列化，即在对象被序列化为字节流时，transient字段的值不会被包含在序列化结果中。在对象反序列化后，elementData 数组将恢复为 null。
transient Object[] elementData;记录当前集合的大小
private int size;2、构造方法
2.1、无参构造
将空数组赋值给成员变量的elementData：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}2.2、有参构造一
参数部分：
- int initialCapacity：数组的大小，范围从0到Integer的最大值。
使用该构造方法，会传递一个初始数组的大小，然后进行if判断。
- 分支一：传入的参数大于0，就创建一个长度为参数的空数组，赋值给成员变量的elementData。
- 分支二：传入的参数为0，就将空数组赋值给成员变量的elementData。
- 分支三：传入的参数小于0，抛出异常，数组的长度不可能为负数。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}通过上面两种构造的分析，可以得出一个结论：成员变量EMPTY_ELEMENTDATA用于区分用户使用的是有参构造，但是传递的参数为0。DEFAULTCAPACITY_EMPTY_ELEMENTDATA代表用户使用的是无参构造。
2.3、有参构造二
参数部分：
- Collection<? extends E> c：Collection及其子类集合。
首先会将传入的集合转换为数组并赋值给成员变量elementData。
然后进入条件判断：
- 分支一：将传入的集合转换为数组的长度赋值给成员变量size，如果不为0，就再次进入判断，检查 elementData 的实际类型是否为 Object[]。如果不是，就将其复制为一个新的 Object[] 类型的数组，并将其赋值给 elementData。
- 分支二：将空数组赋值给成员变量的elementData。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}3、add方法
重点介绍两个重载的方法：方法一是将一个元素放入链表的末尾，方法二是将元素放入指定的下标：
3.1、add(E e)
首先会跳转到ensureCapacityInternal(size + 1); 方法：
分支一：
假设目前是通过无参构造或有参构造传递0实例化的ArrayList，此时的size应该为0，size+1=0+1 = 1。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}条件块满足，取得传入参数（1）和DEFAULT_CAPACITY（10）的最大值，赋值给参数minCapacity，然后再次跳转入ensureExplicitCapacity(minCapacity);方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}modCount++;是其父类AbstractList 中的成员变量，用于记录并发修改次数（不能一边遍历集合一边增删元素，否则会抛出并发修改异常。如果需要，请使用迭代器遍历）
然后会进入条件块。10-0>0，进入最关键的grow(minCapacity); 扩容方法，传入参数10：
private void grow(int minCapacity) {
//0
int oldCapacity = elementData.length;
//0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//0-10 = -10 <0
if (newCapacity - minCapacity < 0)
//10
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//扩容成一个长度为10的新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}扩容使用了Arrays.copyOf(elementData, newCapacity); 方法，将原有数组中的元素复制到一个长度为10的新数组中，然后重新赋值给elementData。（也就是此时的elementData是一个长度为10的空数组）
然后回到add(E e)方法的elementData[size++] = e; 这一行，将元素赋值给elementData的第0索引的元素，然后size+1。（数组的长度为1，元素在0索引上，复习一下，数组的最大下标等于长度-1）
上述过程，证明了ArrayList的扩容时机是在加入第一个元素前进行扩容，然后才会加入元素。
分支二：
假设目前集合中已经有了10个元素，现在调用add(E e)添加第11个元素：
同样首先进入ensureCapacityInternal(int minCapacity)方法，参数为size + 1 = 10 + 1 = 11。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}这时的条件就不满足了，直接进入ensureExplicitCapacity(minCapacity) 方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}11 - 10 = 1 > 0，条件块满足，进入grow(minCapacity); 扩容方法，传入参数11：
private void grow(int minCapacity) {
//10
int oldCapacity = elementData.length;
//10 + 10 / 2 = 15
int newCapacity = oldCapacity + (oldCapacity >> 1);
//15 - 10 = 5 > 0 条件不满足
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//条件也不满足
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}扩容同样使用Arrays.copyOf(elementData, newCapacity); 方法，将原有数组中的元素复制到一个长度为15的新数组中，然后重新赋值给elementData。（也就是此时的elementData是一个长度为15的数组。注意，此时数组中还是只有10个元素，最新的一个仍未添加）
然后回到add(E e)方法的elementData[size++] = e; 这一行，将元素赋值给elementData的第10个索引的元素，然后size+1。
上述过程，证明了ArrayList的扩容机制是，首次添加元素前扩容为10，以后都是扩容为旧容量的1.5倍。
并且元素是放在链表的末尾。
最后值得一提的是，ArrayList并不是无限制扩容，最大容量为Integer的长度。详见hugeCapacity(int minCapacity) 方法，逻辑很简单，有兴趣的请自己研究下！
3.2、add(int index, E element)
这个方法的意思是将元素加到指定的索引上。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}rangeCheckForAdd(index)方法用于检查数组下标越界异常。
ensureCapacityInternal(size + 1) 方法用于判断是否扩容，并执行扩容逻辑，不再重复说明。
System.arraycopy(elementData, index, elementData, index + 1,size - index) 是实现将元素添加到指定索引的前置工作，将 elementData 数组中从索引 index 开始到末尾的元素向右移动一个位置，为在索引 index 处插入新元素腾出空间。
然后将元素加到index所在的索引上，并且size长度+1。
此方法涉及到数组元素的移动，所以效率较低！
4、remove方法
重点介绍两个remove方法，方法一是删除指定索引的元素，方法二是删除指定的元素。
4.1、remove(int index)
此方法是删除传递参数所在索引的元素。
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}既然传递进来的是索引，就必须进行下标合法性的检查，通过rangeCheck(index) 方法。
E oldValue = elementData(index); 方法的作用是返回index索引位置的元素。
int numMoved = size - index - 1; 假设目前数组的长度为3，需要删除1索引处的元素，计算得到的值就是3 - 1 - 1 = 1。
System.arraycopy(elementData, index+1, elementData, index,numMoved) 将 elementData 数组中从索引 index+1 开始的 numMoved 个元素向左移动一个位置，以覆盖索引 index 处的元素。
为了方便理解我们来画个图：
初始情况：
执行System.arraycopy(elementData, index+1, elementData, index,numMoved) 代码，将要删除元素的索引是1：
执行完上面的代码后，将即将删除元素所在索引的后面元素向前移动，覆盖掉删除的元素。
elementData[--size] = null; 然后将链表末尾的元素的指针指向null，方便垃圾回收。
最后返回被删除的元素。
由此可见，ArrayList指定索引删除的效率不高，因为和指定索引新增一样，也涉及到其余元素的移动，如果元素较多则速度较慢。
4.2、remove(Object o)
此方法是删除指定的元素
- 分支一：传递的参数为null，则从0索引开始遍历整个集合，如果某个索引下的元素为null，就调用fastRemove(index)方法删除对应索引的元素。
- 分支二：传递的参数不为null，则从0索引开始遍历整个集合，如果某个索引下的元素和传入的元素相等，就调用fastRemove(index)方法删除对应索引的元素。
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}可以看出，remove(Object o) 的本质依旧是遍历集合，删除指定索引的元素，但是利用的是fastRemove(index)方法：
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
}虽然名字叫fast，实际上依旧涉及到数组元素下标的移动，所以效率依旧不高。
5、并发修改异常原因分析
有这样一段代码，通过增强for循环一边遍历一边增删元素：
public class Test {
public static void main(String[] args) {
ArrayList<String> strings = new ArrayList<>();
strings.add("a");
strings.add("b");
strings.add("c");
for (String s : strings) {
if (s.equals("a")){
strings.remove(s);
}
}
}
}毫无悬念的出现了并发修改异常：
我们来跟踪一下堆栈信息，这个异常出现在ArrayList的私有内部类Itr中的next()方法中的checkForComodification()。
Itr实现了迭代器接口，成员变量expectedModCount的值是ArrayList 父抽象类的成员变量modCount
首先通过打断点的方式了解一下modCount的机制，在Test的第7行打上断点，以及启动程序后，在AbstractList 类的modCount成员变量上打上断点，方便查看不同操作时modCount值的变化情况。
当我们添加第一个元素时，modCount+1 = 1
后续每添加一个元素，modCount都会+1，最终所有元素添加完成后，modCount = 3。
然后进入for循环的if块，删除a元素：
底层调用的fastRemove()方法，modCount = 3 + 1 = 4
在进入下一次循环时，Itr的成员变量expectedModCount为3
而实际modCount = 3 + 1 = 4 ，所以在checkForComodification() 中抛出异常。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}总结
ArrayList是线程不安全的集合，一边遍历一边增删元素会导致并发修改异常。它的底层实现是数组，在构造时，可以自定义集合的长度，如果没有定义，则在添加第一个元素前扩容长度为10，然后会添加元素，后续扩容量为原有容量的1.5倍。插入和删除都可以指定下标位置，增删的效率较低，因为无论何种方式都涉及到数组元素的移动。如果没有指定下标，新增的元素默认在集合的尾部。相对的查询效率较高。
标签：index,minCapacity,元素,int,ArrayList,elementData,源码,浅析,size From： https://blog.csdn.net/2301_77599076/article/details/139378432