ArrayList你真的懂么？
构造方法
先来看看ArrayList的无参构造方法：
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}源码的解释是构造一个初始容量为10的空列表，elementData是ArrayList中的一个成员变量：
transient Object[] elementData;这是ArrayList的核心，之后所有的数据添加和删除都是在这个数组中完成的，所以ArrayList是基于数组的一个数据结构实现，那DEFAULTCAPACITY_EMPTY_ELEMENTDATA是什么呢？
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};它是一个空的Object数组，由此得出结论，若是调用ArrayList的无参构造，则会创建一个容量为0的空数组，那为何源码的文档上说的是构造一个初始容量为10的空列表呢，这个我们放到后面揭晓。
再来看看ArrayList的带参构造：
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);
}
}该方法会构造出一个指定容量的空列表，当传入的值大于0时，则直接创建指定大小的Object数组；当传入的值等于0时，它创建的仍然是一个容量为0的空数组：
private static final Object[] EMPTY_ELEMENTDATA = {};而当传入的值为其它值，比如负数，则会抛出异常。
ArrayList的另一个带参构造方法：
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;
}
}通过该方法可以得到一个包含指定集合元素的列表，它首先会将传入的集合转为Object数组，然后判断这个数组的长度是否不等于0，若满足条件，则调用Arrays类的copyOf方法得到一个指定大小的数组。
add方法
接下来介绍ArrayList集合中的重中之重，add方法，ArrayList中共有两个add的方法重载，先看第一个：
public boolean add(E e) {
// 判断是否需要扩容 size + 1 = 1
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}该方法用于将指定的元素添加到此列表的末尾，但如果此时的ArrayList是通过无参构造方法创建的，它的底层实际上是一个空容量的数组，那么该如何将元素放到这个数组中呢？所以，add方法的第一步一定是扩容：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}该方法调用了ensureExplicitCapacity方法，ensureExplicitCapacity方法内部又以calculateCapacity方法的返回值作为参数，所以先看看calculateCapacity方法的源码：
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}该方法中首先进行了一个判断，elementData和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的值分别是：
transient Object[] elementData;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};我们知道，这两个参数目前一定是相等的，因为：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}所以执行：
return Math.max(DEFAULT_CAPACITY, minCapacity);在DEFAULT_CAPACITY和minCapacity中取一个最大值，DEFAULT_CAPACITY是ArrayList中的一个成员变量，它是用来定义集合的默认初始容量的，而minCapacity就是前面传递过来的值 size + 1，即：当前列表所需的容量，10肯定大于1，所以10就被返回了。此时再执行：
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));ensureExplicitCapacity方法的源码为：
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}现在我们知道，minCapacity的值为10，该方法首先让modCount++，modCount也是ArrayList的一个成员变量：
protected transient int modCount = 0;它的作用是记录集合在结构上被修改的次数，然后是一个判断，目前minCapacity的值肯定大于当前列表的长度，所以会执行grow方法：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}该方法才是真正将数组扩容的方法，首先保存旧容量，然后使用旧容量加上旧容量右移一位（右移一位表示除以2）的值作为新容量，此时判断新容量减minCapacity是否小于0，也就是比较新容量是否小于minCapacity，若满足，则新容量就变成10了，最后通过Arrays的copyOf方法拷贝到一个新的数组。
到这里，集合的扩容操作就完成了，原来容量为0的数组变成了一个容量为10的新数组，接下来就可以将元素存入数组了：
elementData[size++] = e;由此也可以得知，变量size其实是数组最后一个元素的索引，通过它就可以知道ArrayList究竟有多少个元素。
我们再来分析一下扩容算法是如何进行的，先写一段测试代码：
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
for (int i = 0;i < 10;++i){
list.add(i);
}
list.add(1);
}无参构造的ArrayList初始容量为10，所以 list.add(1);
一定会再次触发ArrayList的扩容机制：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}此时的minCapacity为11，首先记录数组的旧容量，为10；然后用旧容量加上旧容量除以2的值作为新容量，为15，这样新容量的值就大于了minCapacity，它就会以15作为新容量去拷贝新数组，由此我们得出一个结论，
ArrayList每次扩容之后的容量都为原容量的1.5倍
。
第二个重载的add方法：
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方法：
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}该方法是用来校验索引的，即：索引如果大于了ArrayList的大小或者小于0，说明不是一个合法的索引，直接抛出异常。校验索引之后，调用ensureCapacityInternal方法，这个方法相信大家非常熟悉了，刚才已经分析过，对于向指定位置添加一个元素，仍然需要去判断数组是否需要扩容，扩容完成后调用System.arraycopy方法，它是一个本地方法：
System.arraycopy(elementData, index, elementData, index + 1,size - index);其实现原理如下：
对于这样的一个列表{1、2、、4、5}，若是想在索引为2的位置插入元素3，使其成为{1、2、3、4、5}，那么System.arraycopy是如何做到的呢？先介绍一下该方法的四个参数：
public static native void arraycopy(Object src,int srcPos,Object dest, int destPos,int length);
- src：源数组
- srcPos：源数组的起始位置
- dest：目标数组
- destPos：目标数组的起始位置
- length：复制的长度
所以刚才的需求可以这样实现：
System.arraycopy({1,2,4,5}, 2, {1,2,4,5}, 3,2);也就是说从列表中索引为2的元素开始，将两个元素复制到原列表中索引3的位置，即：
有数据结构基础的同学应该很快就能明白，它就相当于把要插入位置后面的元素全部后移了，此时就将要插入的位置空出来，这样就可以真正执行赋值代码将其插入进去：
elementData[index] = element;最后集合大小加1：
size++;addAll方法
addAll方法在ArrayList中也有两个重载，先看第一个：
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}该方法用于将指定集合中的所有元素添加到此列表的末尾，首先将传入的集合转为了Object数组，然后取出了该数组的大小，接着仍然是熟悉的操作，判断原列表是否能够存储下这么多的元素，所以将size
+
numNew作为参数去扩容，最后还是调用System.arraycopy方法进行拷贝，从要添加集合的0索引元素开始，将numNew个元素添加到elementData数组中，添加的位置是从size，也就是最后一个元素开始。
第二个addAll方法：
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index); Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved); System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}该方法用于将指定集合添加到此列表的指定位置，对于这个方法，相信大家已然能够猜出具体的做法了，就是先将指定位置后面的元素右移一定的长度，该长度就是需要添加的集合大小，然后将该集合存入空出来的位置：
System.arraycopy(elementData, index, elementData, index + numNew,numMoved);如图所示：
set方法
public E set(int index, E element) {
rangeCheck(index); E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}set方法用于将指定的元素替换指定位置的元素，这个方法非常的源码也非常地简单，第一个方法rangeCheck仍然是一个索引的合法性检测，然后获取到需要替换的位置上的元素值，再将新元素赋值给该位置，最后返回原来的值，所以该方法的返回值是集合原位置上的值：
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Integer num = list.set(1, 4);
System.out.println(num);
System.out.println(list);
}运行结果为：
2
[1, 4, 3]get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}对于get方法，那就更加简单了，直接返回指定索引的元素即可。
迭代器
对于一个ArrayList集合，我们可以很轻松地使用迭代器来遍历它：
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}它的底层又是如何实现的呢？
首先是iterator方法，通过它可以获取集合的迭代器：
public Iterator<E> iterator() {
return new Itr();
}该方法创建了一个Itr对象，该对象是ArrayList的一个内部类：
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount; Itr() {}
......
}此时开始进行迭代，调用迭代器的hasNext方法：
public boolean hasNext() {
return cursor != size;
}cursor为游标，初始值为0，若cursor不等于size，则返回true，说明该方法能够判断是否迭代完成，前提是游标会移动，若返回true，则执行迭代器的next方法：
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}该方法首先调用checkForComodification：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}该方法用于校验预期修改集合次数是否与实际修改集合次数一致，若不一致，则抛出异常，它的作用则是用来阻止迭代时并发修改集合操作的。接着进行一些校验，然后获取到外部类的elementData，这个elementData就是ArrayList真正存储数据的数组，最后让游标加1，返回元素；重复这两个方法，就实现了迭代器遍历集合。
迭代器并发修改异常
先来看一个现象：
public static void main(String[] args) throws Exception {
List<String> list = new ArrayList<>();
list.add("Java");
list.add("Python");
list.add("C++");
Iterator<String> iterator = list.iterator();
while(iterator.hasNext()){
String str = iterator.next();
if("Java".equals(str)){
list.remove("Java");
}
}
}程序的本意是想删除集合中的 Java
字符串，但事与愿违：
Exception in thread "main" java.util.ConcurrentModificationException程序抛处了并发修改异常，来看看异常产生的原因。还记得在add方法执行过程中的一个变量吗：
protected transient int modCount = 0;这样变量是用来记录列表在结构上被修改的次数，当你调用add、remove向列表添加或删除一个元素时，列表结构就会被改变，相应的，modCount就会加1。在迭代器Itr类中有这么一个成员变量：
int expectedModCount = modCount;它的初始值就等于modCount，也就是说，迭代器现在已经知道我们对列表的结构修改次数，此时我们就要来看看next方法中的checkForComodification：
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}该方法判断modCount和expectedModCount是否相等，目前肯定是相等的，但如果你在迭代的过程中添加或者删除了一个元素，势必会导致列表的结构被修改，modCount就会加1，那么它们俩就不会相等了，由此抛出了并发修改异常。那么JDK为什么要这么设计呢？我们假设它不会抛出这个异常，那么就会出现一个问题，比如：
对于这样的一个列表，首先Cursor从第一个元素开始进行迭代，当迭代到数值4时，向前添加一个元素：
此时会间接导致Cursor前移，这样就重复遍历到了元素，代码如下：
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer num = iterator.next();
if(num == 4){
list.add(2,10);
}
}
System.out.println(list);
}但这样是绝对不被允许的，所以肯定会抛出并发修改异常。
那难道在迭代器迭代集合的时候就不能对集合进行操作了吗？当然是可以的，只不过必须使用迭代器提供的方法，比如：
public static void main(String[] args) throws Exception {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer num = iterator.next();
if(num == 1){
iterator.remove();
}
}
System.out.println(list);
}然而迭代器只提供了remove方法，所以在迭代器迭代时只能执行删除操作。
欢迎关注公众号，学习更多进阶技术。
往期热门文章推荐画图带你理清TCP协议三次握手和四次挥手继续画图带你学习TCP 其他 7 大特性面试常问的dubbo的spi机制到底是什么？（上）面试常问的dubbo的spi机制到底是什么？（下）
常见的分布式事务解决方案，你会几种？ Mybatis 面试连环炮，你能接住几个？一文带你看懂nacos是如何整合springcloud -- 注册中心篇
Java中的volatile关键字最全总结通俗讲解分布式锁：场景和使用方法
聊一聊nacos是如何进行服务注册的 你还在用tomcat?out了点分享点收藏点点赞点在看