wen JDK成长记2：ArrayList常用方法源码探索（上）
上一节相信你不光学会ArrayList构造函数的知识，更学会了先脉络后细节、连蒙带猜的思想。在之后的几节中，你将学会ArrayList常用方法的源码原理。学完之后，你将不会再被ArrayList的面试题问倒了，更可以得心应手的使用ArrayList。
今天这一节，你主要可以学到以下几点：
- ArrayList扩容原理
- 影响ArrayList性能的根本原因是什么
- 学会新的源码阅读思想和方法
让我们开始吧！
ArrayList第一次调用add方法发生了什么？
首先你要修改下上一节之前的Demo，修改如下：
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo {
public static void main(String[] args) {
//默认大小是0
List<String> hostList = new ArrayList<>();
hostList.add("host1");
}
}
上面代码，假设你通过add方法向hostList添加了1个host主机地址。ArrayList第一次调用add方法发生了什么？
你可以点击进去，看到如下代码清单：
/**
* 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!!
elementData[size++] = e;
return true;
}
看之前，我又要多说两句，源码的注释和方法名，有时候能帮助你了解这个方法大致的作用。这是很关键的一点。比如注释的意思是add方法是追加一个具体的元素到list的末尾；方法名ensureCapacityInternal，是确保内部容量的意思。看过之后，你应该可以猜到这方法大致是确认容量相关的，可能是判断容量能否添加元素用的。
还要注意的是，你看一个方法的时候，不要着急直接从第一个行就开始看，也是先根据注释和方法名有一个大概的认识后，你需要看下整个方法的结构之后再开始。比如调用了哪些其他方法，有几个for循环或if结构。就像这个add方法，他主要有2步，第一步是调用了一个方法，应该是确保内部容量是否够添加元素，第二步是一个数组基本赋值操作并且size++一下。
如下图所示：
ArrayList的数组大小为0也能可以添加元素？
接着当你知道了整个方法的脉络，你再来看下细节，先看第一步：ensureCapacityInternal()。
这个方法入参是size + 1，size之前说你应该看到过，就是一个成员变量int size。它的默认值是0，所以size+1后，这个方法的实参就是1，那么形参minCapacity的值就是1。（实参就是传入方法实际的值，形参就是方法括号中使用的参数名）。可以看到ensureCapacityInternal的代码清单如下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
接着你可以看到这里又调用了calculateCapacity方法和ensureExplicitCapacity方法。我们先进入calculateCapacity看下，你可以记下它的实参是minCapacity=1，elementData还记得么？是ArrayList核心的那个成员变量Object[]数组。calculateCapacity代码如下：
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private static final int DEFAULT_CAPACITY = 10;
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。
在ArrayList无参构造函数的时候就看到过。第一次调用add方法的时候，它们俩的引用地址和值都是应该一样的，因为在构造函数中有过这么一句话this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
所以这里进入第一个if条件，然后使用DEFAULT_CAPACITY和minCapacity作比较，可以看到DEFAULT_CAPACITY这个变量的值是10，也就是说这里Math.max操作后会返回10。
到这里你可以在完善下之前画的图，就会变成如下所示：
也就是说calculateCapacity返回后，回到ensureCapacityInternal这个方法，会传入ensureExplicitCapacity的实参是10，因为calculateCapacity(elementData, minCapacity)= 10。
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
接着你又会进入ensureExplicitCapacity方法，看到如下代码:
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
此时形参minCapacity也就是刚才传入的10，你可以从名字上看这个方法，ensureExplicitCapacity意思是确保精确的容量的意思。还是先看下方法的脉络，第一行有一个modCount++,之后你可以看到一行代码注释，overflow-consciouscode意思是说具有溢出意思的代码，之后有一个if条件，满足会进入grow方法。
到这里你可以连蒙带猜下，这里的grow方法，是不是就是说容量不够，会进行增长，也就是扩容呢？
因为我们知道，无参构造函数创建的ArrayList大小默认是一个为0的Object[]数组elementdata。而且elementdata.length肯定是0，难道也能添加元素么？肯定是不可以的。
接着我们逐行看下，第一行的modCount好像不太知道是什么，你可以点击下它，看到它是一个成员变量，而且有一大堆注释，好像也没看懂什么意思。所以这里要告诉大家另一个看源码的思想了：抓大放小。比如这里看上去modeCount和添加操作没啥关系，就先跳过！（其实这个modCount是并发操作ArrayList时，fail-fast机制的实现,下一节我会讲到的）
目前执行代码如下图所示：
ArrayList第一次添加元素会扩容么？
你接着往下看，很明显，minCapacity=10，elementData这个空数组length肯定是0。所以10-0>0，会满足if条件，进入grow方法，它的实参是10。它的代码清单如下:
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);
}
grow方法形参minCapacity的值是10，你进入这个grow方法后，从脉络上来看，有两个if分支，有两个局部变量oldCapacity和newCapacity，还有一步elementData通过Arrays.copyOf方法的赋值操作。
而且oldCapacity应该是0，因为我们知道elementData数组是空的。接着你会看到一句：intnewCapacity = oldCapacity +(oldCapacity >> 1);
这句话是什么意思呢？其实就是oldCapacity右位移1位。如果你还记得计算机基础中的话，右移一位，有点类似于除以2，底层是二进制的运算而已。这里可以举个例子：
比如oldCapacity=10，如果先左移1，就是乘以2，在右移 1就是除以2，如下所示：
那么int newCapacity = oldCapacity +(oldCapacity >> 1); 其实这句话的意思就是在原有大小基础上增加一半大小。
但是由于oldCapacity=0，所以增加一半大小,newCapacity=0+0>>1=0+0=0。
而此时minCapacity=10。这样就会进入第一个if条件，因为newCapacity – minCapacity < 0，即0-10<0，然后进行了一步赋值操作，newCapacity就会变成和minCapacity一样，值是10。
这里你可以总结一下，也就是说如果创建ArrayList时，不指定大小， ArrayList第一次添加元素，会指定默认的容量大小为10。
你可以继续完善你的图,grow方法逻辑如下：
ArrayList计算完扩容容量大小后，又干了什么？
除了上面计算扩容容量大小的代码，是grow的核心逻辑之一。
第一次添加元素时，在grow中，最后还会执行一行代码：
elementData****= Arrays.copyOf(elementData, newCapacity);
这个也是grow方法中另一个核心步骤，数组的拷贝。
你可以点击Arrays.copyOf，看看它底层做了些什么。代码如下：
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength ,
Class<? extends T[]> newType) {
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,Math.min(original.length, newLength));
return copy;
}
还是从脉络上看下，这里Arrays.copyOf它实参是elementData（Object[]空数组）和newCapacity=10。可以看到它内部直接调用了一个重载方法。
在重载方法中，首先调用了一个三元表达式和一个System.arraycopy方法调用，接着执行了
System.arraycopy(original, 0, copy, 0,Math.min(original.length,newLength));
这句话,它看样子像是操作了original和 copy的样子。
之后你再来仔细分析下细节。
ArrayList的缺点，原因原来是在这里！
根据传递的参数elementData的class是Object[].class的类型，可以看出三元表达式会执行(T[]) new Object[newLength]。
接着就会执行System.arraycopy这个方法。你可以查阅下JDK的API，它的主要是作用是数组的拷贝。
由于这个方法的API不是很好理解。这里我给大家讲下,它的方法签名如下：
System.arraycopy(Objectsrc,int srcPos,Object dest,int destPos, int length)****。
这里，如果大家遇见难以理解的代码，除了画图，另外一个方法就是举例子。比如：
好了，你知道了这个API基本的使用，再来看源码中的代码：
System.arraycopy(original,0,copy,0,Math.min(original.length, newLength));
首先original就是我们传递进来的elementData。它的length是0。newLength是传递进来的newCapacity，也就是10。copy 是我们刚创建的Object[]数组，长度为10。Math.min取最小后是0。也就是变成：
System.arraycopy(original,0, copy, 0,0);
这个就很好理解了，就是从original位置0开始移动0个元素到copy数组，从copy数组0位置开始覆盖。这就等于什么都没拷贝，直接返回了我们新创建的数组T[] copy，这个数组大小为10。
最终Arrays.copyOf获得了一个长度为10的数组，但里面没有任何元素。接着这句话就执行完了。elementData = Arrays.copyOf(elementData, newCapacity);结束grow方法的也就执行完了。
而grow方法执行完就意味着ensureCapacityInternal执行完了。这个方法已经确保了内部数组的容量大小可以放入新元素。
我们回到开始，执行完第一步，内部容量确保后，接着第二步直接执行了elementData[size++]= e;通过数组的赋值操作，就完成第一次元素的添加了！
到这里可以发现，当添加的时候，如果大小不够就会进入grow方法，进入grow方法就会进行一次1.5倍的扩容。而且代码规范一般都建议我们要指定ArrayList的大小，如果不指定，可能会造成频繁的扩容和拷贝，造成性能低下。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
好了，到这里ArrayList最常用的add(E e)方法的源码原理就已经研究透彻了。
最终的源码原理图如下：
最后我给大家把收获到的总结下：
1、你知道了ArrayList的扩容机制：底层通过grow方法。它的核心一个是计算出扩容大小，是基于右移1位来计算，一般扩容大小为1.5倍，另一个核心是进行数组拷贝，底层通过System.arraycopy来创建新数组，来最终实现空间的扩容。
2、你也知道了频繁扩容会造成频繁的数组拷贝，会造成耗时，影响ArrayList的性能。
3、更重要的是，这一节你学会了抓大放小的思想、对先脉络后细节、连蒙带猜的思想更熟练了，还进行了适当的举例子和画图分析源码。
你可以通过今天学的思路和方法，去看看ArrayList的另一个方法源码：add(int index, E element)这个方法意思是在指定位置添加一个元素，研究下它的源码原理。
金句甜点
除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：改变自己比改变别人更重要。
其实生活中很多矛盾和问题，都来自于我们总是无形的要求别人做什么，夫妻之间，亲人之间，朋友之间……当别人没有做到你期望的，你就可能会不开心，抱怨，甚至吵架，有脾气。一个人有脾气，其实你对事，对人的包容不够，想想你对一个美女和一个丑女的包容肯定是不一样的。
比如不要总是希望父母理解你做什么，而是改变自己去理解他们，他们的认知和你不一样。比如我的父亲，他比我快要大一倍的岁数，过了今年就60岁了，他的思想观念很多都是和毛主席那个年代的人一样，他有时候不理解这个时代，他的家里和手机壁纸都是毛主席的画像，他甚至不会用微信转账，还在用现金，不知道大数据，云计算到底是什么，总被微信朋友圈忽悠的一塌糊涂。我不应该要求他们非要用微信转账，支付宝付款，也不应该总是给他非要讲明白大数据云计算。而是应该改变我自己下，我应该理解他，理解他可能没什么文化，他认知就比较越低，认知越低，有时候也就越顽固，更要改变自己，不总是逼我爸学习，当然他想学我就耐心教他。渐渐地他还是学会了基本转账，因为他喜欢抢红包。
所以，其实你可以想想，生活中，很多时候男女朋友或者夫妻吵架，大多都是因为你要求对方做什么导致的。那么你就不要总想着改变别人，要求别人，改变自己比改变别人更重要。改变了自己才能更好的影响别人。相信各位每天改变一下，学习一篇成长记，会更能影响别人，跟你一起学习和成长。
最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。
欢迎大家在评论区留言和我交流。
（声明：JDK源码成长记基于JDK 1.8版本，部分章节会提到旧版本特点）
本文由博客群发一文多发等运营工具平台 OpenWrite 发布
