在源码分析系列的文档中，笔者会尽量使用CURD操作的角度来分析JDK的源码。是因为多数程序员都是CURD阶段，当然最熟悉的还是CURD操作，因此以CURD的角度来看JDK的源码，相信会容易不少，毕竟万物皆可CURD，万物离不开CURD

注1：开发工具为IntelliJ IDEA 2020.1.2 x64 

注2:  JDK版本为JDK8  版本号为 jdk1.8.0_191

talk is cheap，show me the code ---undefined

代码段如下，有清晰明了的注释

import java.util.ArrayList;
import java.util.List;public class ArrayListTest  {public static void main(String[] args) {//无参构造函数new一个ArrayListList arraylist=new ArrayList();//ArrayList的add操作arraylist.add("hello world");arraylist.add("world hello");System.out.println("当前ArrayList的容量大小"+arraylist.size());//循环增长，查看动态grow函数for (int i=0;i<10;i++){arraylist.add(i);}System.out.println("当前ArrayList的容量大小"+arraylist.size());//Arraylist的getter setter操作System.out.println("getter"+arraylist.get(3));System.out.println("setter"+arraylist.set(3,"huhu"));System.out.println("当前ArrayList的容量大小"+arraylist.size());//arraylist的addall操作arraylist.addAll(arraylist);System.out.println("当前ArrayList的容量大小"+arraylist.size());//arraylist的index操作System.out.println("这是索引"+arraylist.indexOf("world hello"));System.out.println("这是最后索引"+arraylist.lastIndexOf("world"));System.out.println("当前ArrayList的容量大小"+arraylist.size());System.out.println("是否包含有"+arraylist.contains("huhu"));System.out.println("是否包含所有"+arraylist.containsAll(arraylist));System.out.println("当前ArrayList的容量大小"+arraylist.size());//arraylist的remove操作System.out.println("删除元素"+arraylist.remove("world hello"));System.out.println("删除元素"+arraylist.remove(4));System.out.println("当前ArrayList的容量大小"+arraylist.size());//arraylist的retain操作arraylist.retainAll(arraylist);arraylist.removeAll(arraylist);System.out.println("当前ArrayList的容量大小"+arraylist.size());}}

OK，下面我们试着断点分析来看看ArrayList的源码

到此步，请保留你的耐心，因为看源码是一个非常枯燥和非常花时间的过程，如果你觉得看不下去，可以休息一会儿，再继续。毕竟看源码，如同登山，当你在山顶时，相信看的风景会非常不一样的。

1. 看new ArrayList发生了什么

         //无参构造函数new一个ArrayListList arraylist=new ArrayList();

此行打断点（ctrl+F8），启用单步调试（F7）或者强制进入（Alt+Shift+F7）可以看到

  /*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;         //无参构造函数初始化容量为10的空数组，目前代码只是初始化为空数组，并没有指定容量？什么时候指定的容量？}

可以看见new ArrayList（）调用了无参构造函数，在此构造函数中ArrayList将之前初始化过后的静态变量  DEFAULTCAPACITY_EMPTY_ELEMENTDATA  （初始化构造了一个默认容量为10的空数组列表）并将其引用赋值给了ArrayList的本地真实的存储结构即elementData。

注3：无参仅仅初始化了一个空的数组列表，并没有指定数组的大小 （此为无参构造函数做的事）那么是什么时候指定了默认容量为10呐？是在calculateCapacity方法中，当elementData为默认容量的空数组列表时，返回一个10的值表示为列表的容量大小（后文会叙述）

2. 看 ArrayList的add操作发生了什么

        //ArrayList的add操作arraylist.add("hello world");arraylist.add("world hello");System.out.println("当前ArrayList的容量大小"+arraylist.size());//循环增长，查看动态grow函数for (int i=0;i<10;i++){arraylist.add(i);}System.out.println("当前ArrayList的容量大小"+arraylist.size());

在第一个add方法代码行出打一个断点，操作如同上文，在循环中的add又打一个断点（是为了方便查看ArrayList的动态扩容机制），启用单步调试（F7）或者强制进入（Alt+Shift+F7）可以看到

  /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return <tt>true</tt> (as specified by {@link Collection#add})*/public boolean add(E e) {                           //此函数将指定的元素放在列表末尾(以追加的方式)ensureCapacityInternal(size + 1);  // Increments modCount!!     //以当前大小+1为最小容量值为参数来判断所需要的容量大小elementData[size++] = e;return true;}private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {         //当elementData是默认容量数组列表时，则返回默认容量大小10return Math.max(DEFAULT_CAPACITY, minCapacity);             //在这儿返回指定了elementData的默认容量大小10}return minCapacity;                                             //当elementData数组元素时候。则返回最小的容量大小}private void ensureExplicitCapacity(int minCapacity) {modCount++;                                 //结构性变化+1// overflow-conscious code               //此代码可能会造成溢出if (minCapacity - elementData.length > 0)              //如果最小容量大小都大于当前数组列表的大小则调用增长函数grow(minCapacity);}/*** Increases the capacity to ensure that it can hold at least the* number of elements specified by the minimum capacity argument.** @param minCapacity the desired minimum capacity*/private void grow(int minCapacity) {// overflow-conscious codeint 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);}

代码比较复杂也比较多，所以需要耐心，不要慌，我们按照方法的调用顺序来看看，add操作都发生了什么？

add->ensureCapacityInternal->ensureExplicitCapacity->calculateCapacity

1. calculateCapacity是计算ArrayList的最小容量的

如果最开始是初始化的空数组列表，则返回10的初始化容量，如果不是，则返回代入的参数即最小容量值

注4： 在看此源码的过程中，需要分清这么几个概念，通常概念不清，就看源码比较困难

长度指的是ArrayList的长度，表示是ArrayList可以容纳的元素多少个数

最小容量值指的是ArrayList在结构性变化的过程中所需要的容纳空间

大小指的是ArrayList实际上所拥有的元素个数的大小即size方法所返回的size值，也即ArrayList中的size属性

2. ensureExplicitCapacity是用来调用grow方法和针对modCount自增的

注5： modCount表示针对ArrayList的结构性变化的指针标识，如add，remove等

3. grow实现了ArrayList的动态扩容机制（重点）（面试常问）

在grow方法体内我们可以看到

旧容量为原来的ArrayList的长度大小

而新容量则是旧容量的1.5倍

若新容量都小于所需要的最小容量，则将最小容量赋值给新容量

若新容量比极限容量要大，那么就将极限容量和最大整型数当中的最大值赋值给新容量

完成以上的步骤后，就根据新容量来初始化一个新的数组，将原来的elementData的所有元素都等位的复制到新的数组当中，然后将新的数组引用赋值给elementData，这样就完成了ArrayList的动态扩容机制

Q1：ArrayList的动态扩容机制是怎么回事？

Q2：什么时候会触发ArrayList的扩容？

Q3：为什么新容量会设置成旧容量的1.5倍？为什么会采取位运算而不是简单的乘除运算？

Q4：若需要的最小容量都达到了极限容量值，是否还需要扩容？是否会报异常？

Q5： grow方法会被哪些方法给调用？哪些是显式调用？哪些是隐式调用？

Q6：ArrayList的扩容机制的时间复杂和空间复杂度是？频繁的动态扩容会导致什么样的问题？

4. 经过了以上的动态扩容之后

elementData就是新容量的数组列表了，然后执行了size++，并将这个位置上的元素填上所传入的参数值。

注6: add操作是在数组列表末尾直接追加元素，所以才使用了size++，并元素赋值

5. 成功之后，返回真值

3. 看ArrayList的getter setter操作发生了什么

           //Arraylist的getter setter操作System.out.println("getter"+arraylist.get(3));System.out.println("setter"+arraylist.set(3,"huhu"));System.out.println("当前ArrayList的容量大小"+arraylist.size());

按照上面的方法同样的打断点进入调试，可以看见

  /*** Returns the element at the specified position in this list.*3* @param  index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);}/*** Replaces the element at the specified position in this list with* the specified element.** @param index index of the element to replace* @param element element to be stored at the specified position* @return the element previously at the specified position* @throws IndexOutOfBoundsException {@inheritDoc}*/public E set(int index, E element) {rangeCheck(index);E oldValue = elementData(index);elementData[index] = element;return oldValue;}/*** Checks if the given index is in range.  If not, throws an appropriate* runtime exception.  This method does *not* check if the index is* negative: It is always used immediately prior to an array access,* which throws an ArrayIndexOutOfBoundsException if index is negative.*/private void rangeCheck(int index) {if (index >= size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}// Positional Access Operations@SuppressWarnings("unchecked")E elementData(int index) {return (E) elementData[index];}

此源码可以分3部分看，一部分是getter setter操作，一部分是rangeCheck，一部分是elementData

先看getter，可以看到

1. 先调用了rangecheck

步入rangeCheck，发现是针对传入的索引值进行合法性检查，若传入的索引值大于或者等ArrayList的大小，就抛出了 IndexOutOfBoundsException 说明了是索引溢出边界异常，在上面的注释可以发现，若索引值是负数的，就抛出 ArrayIndexOutOfBoundsException 说明了是数组索引溢出边界异常

2. 若传入索引值合法

则调用elementData方法，返回该索引位置上的元素

注7：为什么会有两个索引异常？一个是 IndexOutOfBoundsException 另外一个是 ArrayIndexOutOfBoundsException？ 是针对什么情况呢？针对索引值的检查？如此代码就足够了吗？

注8：为什么要编写一个elementData方法？通过这个方法来返回元素？而不是直接使用 e=elementData(index)?

再看setter，可以看到

1. 调用rangeCheck检查索引合法性

2. 将索引值上的元素作为旧元素返回

3. 传入的新值赋值给索引值上的元素

此getter setter方法都比较简单，就不多说了

4. 看addAll操作发生了什么

           //arraylist的addall操作arraylist.addAll(arraylist);System.out.println("当前ArrayList的容量大小"+arraylist.size());

同上一样的进入调试，可以发现

/*** Appends all of the elements in the specified collection to the end of* this list, in the order that they are returned by the* specified collection's Iterator.  The behavior of this operation is* undefined if the specified collection is modified while the operation* is in progress.  (This implies that the behavior of this call is* undefined if the specified collection is this list, and this* list is nonempty.)** @param c collection containing elements to be added to this list* @return <tt>true</tt> if this list changed as a result of the call* @throws NullPointerException if the specified collection is null*/public boolean addAll(Collection<? extends E> c) {Object[] a = c.toArray();int numNew = a.length;ensureCapacityInternal(size + numNew);  // Increments modCountSystem.arraycopy(a, 0, elementData, size, numNew);size += numNew;return numNew != 0;}

1. 将传入的集合通过toArray方法转为object的数组对象列表

2. 调用ensureCapacityInternal方法来计算当前size+集合中的元素大小是否能够有容纳空间？如果有，就继续，如果没有就需要调用grow方法进行扩容，直到了有容纳空间为止（grow的具体操作可以参考上文）

3. 调用System.arraycopy方法完成一次数组之间的复制，将集合中的元素追加复制到elementData中

4. size+numNew完成size大小的更新

5. 返回boolean值

5. 看index操作和contain操作都发生了什么

            //arraylist的index操作System.out.println("这是索引"+arraylist.indexOf("world hello"));System.out.println("这是最后索引"+arraylist.lastIndexOf("world"));System.out.println("当前ArrayList的容量大小"+arraylist.size());System.out.println("是否包含有"+arraylist.contains("huhu"));System.out.println("是否包含所有"+arraylist.containsAll(arraylist));System.out.println("当前ArrayList的容量大小"+arraylist.size());

同上一样的进入调试，可以发现

    /*** Returns <tt>true</tt> if this list contains the specified element.* More formally, returns <tt>true</tt> if and only if this list contains* at least one element <tt>e</tt> such that* <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.** @param o element whose presence in this list is to be tested* @return <tt>true</tt> if this list contains the specified element*/public boolean contains(Object o) {return indexOf(o) >= 0;}/*** Returns the index of the first occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the lowest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.*/public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}/*** Returns the index of the last occurrence of the specified element* in this list, or -1 if this list does not contain the element.* More formally, returns the highest index <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,* or -1 if there is no such index.*/public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}

先看indexOf，可以看出

1. 对传入的object对象引用判空

2. 如果是空，就for循环来获取整个ArrayList中第一次出现null的值，如果有，就返回该处索引值，如果循环完了，都没有，就返回-1

3. 如果object不是空，一样的for循环遍历整个ArrayList，查找第一次出现该值相同的位置，并返回该值所处的索引值，若遍历完了，都没有，就返回-1

再看lastindexOf，可以看出

实现的逻辑是跟indexOf是差不多的，都是遍历整个ArrayList来查找object，唯一不同是，遍历是倒序遍历，返回自然是最后一次出现该值的索引

再看contain，也可以发现

调用了indexOf，只不过是是通过indexOf来查找该元素的索引值，然后比对索引值是否大于等于0，若是就返回真，否则就是假，表示该元素在整个ArrayList中不存在

注9：为什么需要对传入的object判空？空值和非空值对判断查找是否有区别？

6. 看remove操作发生了什么

//arraylist的remove操作System.out.println("删除元素"+arraylist.remove("world hello"));System.out.println("删除元素"+arraylist.remove(4));System.out.println("当前ArrayList的容量大小"+arraylist.size());

同上一样，调试进入源代码，可以看出

  /*** Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices).** @param index the index of the element to be removed* @return the element that was removed from the list* @throws IndexOutOfBoundsException {@inheritDoc}*/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 workreturn oldValue;}/*** Removes the first occurrence of the specified element from this list,* if it is present.  If the list does not contain the element, it is* unchanged.  More formally, removes the element with the lowest index* <tt>i</tt> such that* <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>* (if such an element exists).  Returns <tt>true</tt> if this list* contained the specified element (or equivalently, if this list* changed as a result of the call).** @param o element to be removed from this list, if present* @return <tt>true</tt> if this list contained the specified element*/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;}/** Private remove method that skips bounds checking and does not* return the value removed.*/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}

remove这个操作有两个重载函数，一个是根据索引来remove，一个是根据对象来remove

先看根据索引来remove的代码

1. 检验索引是否合法

2. 结构性标识变化加1

3. 计算需要开始移动的索引位置

4. 如果索引位置大于0，就调用System.arraycopy从需要移动的索引位置开始从后往前覆盖复制

5. elementData的最后一个元素位置设置为null

6. 返回旧值

注10：为什么要对elementData最后一个末尾元素设置为null？注释解释为了让gc能工作，那么仅仅是为了让gc工作么？gc又是什么时候发生gc的呢？若对不需要的元素引用设置为null，是否能马上gc?

再看根据object来remove的代码

1. 很显然首先需要判断object是否为null

2. 根据是否为null值，分两种方法，循环遍历查找对应的值

3. 调用fastremove方法

4. fastremove方法中的代码跟上文的remove（int index）步骤下2到5一致，也就是2到5封装成了一个fastremove方法

注11：为什么步骤2到5封装成了一个fastremove方法？是否能快速删除？

7. 看retainAll和removeAll发生了什么

        //arraylist的retain操作arraylist.retainAll(arraylist);arraylist.removeAll(arraylist);System.out.println("当前ArrayList的容量大小"+arraylist.size());

同上一样，调试进入源代码，可以发现

    /*** Removes from this list all of its elements that are contained in the* specified collection.** @param c collection containing elements to be removed from this list* @return {@code true} if this list changed as a result of the call* @throws ClassCastException if the class of an element of this list*         is incompatible with the specified collection* (<a href="Collection.html#optional-restrictions">optional</a>)* @throws NullPointerException if this list contains a null element and the*         specified collection does not permit null elements* (<a href="Collection.html#optional-restrictions">optional</a>),*         or if the specified collection is null* @see Collection#contains(Object)*/public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, false);}/*** Retains only the elements in this list that are contained in the* specified collection.  In other words, removes from this list all* of its elements that are not contained in the specified collection.** @param c collection containing elements to be retained in this list* @return {@code true} if this list changed as a result of the call* @throws ClassCastException if the class of an element of this list*         is incompatible with the specified collection* (<a href="Collection.html#optional-restrictions">optional</a>)* @throws NullPointerException if this list contains a null element and the*         specified collection does not permit null elements* (<a href="Collection.html#optional-restrictions">optional</a>),*         or if the specified collection is null* @see Collection#contains(Object)*/public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);return batchRemove(c, true);}private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;int r = 0, w = 0;boolean modified = false;try {for (; r < size; r++)if (c.contains(elementData[r]) == complement)elementData[w++] = elementData[r];} finally {// Preserve behavioral compatibility with AbstractCollection,// even if c.contains() throws.if (r != size) {System.arraycopy(elementData, r,elementData, w,size - r);w += size - r;}if (w != size) {// clear to let GC do its workfor (int i = w; i < size; i++)elementData[i] = null;modCount += size - w;size = w;modified = true;}}return modified;}

1. 调用object.requireNonNull检查元素object是否为空

2. 不管是retainAll还是removeAll都调用了batchRemove方法，只不过传入参数一个正一个负

3. 来看看batchRemove究竟发生了什么