wen JDK成长记3：ArrayList常用方法源码探索（中）
无论是程序员的工作、学习，还是生活中的事情。都可以遵循这样一条原则：“，简单的事情重复做，正确的事情重复做。” 这样的努力会让你走到正道上，少走很多弯路。从小司机变成老司机。
上一节你应该已经掌握了ArrayList的扩容原理，System.arrayCopy方法，还有看源码的一些思想和方法。这一节更多的是练习一下学到的思想和方法，带你快速摸一下ArrayList其他常用方法的源码原理，看看他们里面的一些亮点，这一节还可以让你简单了解下fail-fast机制，之前的modCount到底是干什么的。
轻车熟路，扫一下ArrayList的set、get方法
首先你需要修改下你的Demo，如下：
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo {
public static void main(String[] args) {
List<String> hostList = new ArrayList<>();
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
System.out.println(hostList.set(1, "host4"));
System.out.println(hostList.get(1));
}
}
上面代码，假设你通过add方法向hostList添加了3个host主机地址。之后使用set方法替换了位置1的内容，并打印了一下返回值。之后调用一下get方法，获取下位置1的元素，检查是否替换成功。上面逻辑如图所示代码：
这里需要额外提一点的是，其实有运维有一条原则，就是操作完成命令和脚本后，一定要check！check！比如这里进行了set后一定get看下。其实不光是运维，很多时候你都应该这样的，线上要回测、执行SQL后要检查、代码要自测等等……这个思想你一定要铭记于心，举一反三。
话不多说，直接看源码，首先是set方法：
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
你可以从注释或者API使用上，都可以知道set方法的作用是替换某个位置的元素。通过
源码可以看到set方法的脉络：
- 第一步rangeCheck明显是范围检查，是个校验动作；
- 第二步是elementData(int index)方法，这个方法通过数组下标方式获取元素，基础的数组操作，通过oldValue记录了下原值；
- 第三步就是通过数组下标进行了赋值操作，elementData[index] =element;，最后返回了之前记录的oldValue。
其实这个源码非常简单，这里更深刻的体现了ArrayList底层使用数组的原理，如果你手写一个自定义List，可以参考这个思路。
源码逻辑如下图所示：
接着下来，再来快速看下get方法:
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
可以看到，get方法的脉络更简单，就是范围检查，校验一下，之后通过基础的数组操作，通过数组下标方式获取元素而已。
这里值得一提的一点是，JDK源码封装的方法都不会太长，很清晰，重用性也很好。这个编码风格值得我们借鉴。但是也不能过于精简，可读性会降低，JDK就有这个问题,这也是因为大多JAVA大牛们喜欢精简至极的代码，这也是可以理解的。
到这里，set和get源码逻辑如下图所示：
换汤不换药的，remove系列方法
相信，当你看过了add、get、set等方法后，已经越来越熟练和上道了。现在让我们再一起看下ArrayList的remove系列的方法，其实源码底层原理，换汤不换药，还是System.arraycopy那一套。
remove系统方法如下图所示：
以上这些就是ArrayList中的remove方法，例子就不写了，相信你已经可以直接阅读源码了。
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;
}
上面脉络很清晰，比较关键的两行就是计算移动元素的个数，和在原数组上拷贝元素到原数组。其余的几行你应该都已经知道是干什么的了，这里就不赘述了。
源码逻辑如下图所示：
System.arraycopy拷贝一般总是不太好理解，所以还是举个例子大家更能理解：
这句话你应该不陌生了，现在需要从原数组2位置开始移动3个元素到目标数组, 从目标数组的1位置开始覆盖。这里源和目标都是自己，结果就会变成elementData [0,2,3,4,4]。
remove源码的最后一句elementData[–size]= null;数组会变成elementData [0,2,3,4,null]可以让GC帮忙回收掉null值，并且size–，数组大小减1。
remove(int index)的方法是不是很简单？之后你可以再看看remove(Obejct o)方法和他有什么区别：
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方法的脉络主要是两个if，每个if中有一个for循环，都是在遍历整个数组，进行值比较。如果找到第一个匹配的元素就调用了fastRemove(index)方法，然后直接返回了。什么意思呢？我们看个例子：
public static void main(String[] args) {
List<String> hostList = new ArrayList<>();
hostList.add("host1");
hostList.add("host2");
hostList.add("host3");
hostList.add("host2");
hostList.add(null);
hostList.add(null);
System.out.println("删除前:"+hostList);
hostList.remove("host2"); //只会移除第一个匹配的元素
hostList.remove(null); //只会移除第一个匹配的元素
System.out.println("删除后:"+hostList);
}
从输出结果就能知道只是删除了第一个符合条件的元素。这个你使用起来要注意，如果想删除所有匹配的元素可以使用removeIf()方法。接着看fastRemove干了什么呢？可以发现他和remove(int 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;
}
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;
return oldValue;
}
差别可能就是rangeCheck和elementData(index)获取元素而已。
removeRange和removeAll大家可以自己去看看，真的是换汤不换药，还是System.arraycopy而已。至于removeIf方法我们下一小节具体讲，还有fail-fast机制，下一节也简单给大家提下。
看到这里可以你可以小结为，如下图片：
remove系列方法中亮点方法：removeif()
这一小节，我们最后再看下removeif()这个方法。它里面其实有一个不错的思想，可以供大家借鉴学习的。我们直接来看代码：
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
上面这个方法比较长,但整个脉络其实还是很清晰的:
第一步主要是通过BitSet和for循环找到符合条件的匹配的元素，并只记录位置index到BitSet中去。
第二步只要存在符合条件的元素，就通过for循环，进行元素交换, 这里并没有使用System.arrayCopy。
第三步通过for循环，把交换完成后，将无用的位置置为null。
第四步返回删除了元素的数量
你可以进入源码，自己尝试去画一下它的流程图，练习一下。这里画一个大致原理图给你：
这里我要重点给你讲的是它fail-fast的机制:
你可以注意到，在整个过程中一直使用了modCount和expectedModCount做判断 ，这个是用来干什么的呢？这两个值表示，如果removeIf执行，开始删除符合条件的元素时，不能有另外的线程来修改当前的这个ArrayList，如果别的线程进行add、remove等操作，modCount肯定会发生变化。在removeIf执行过程中，只要发现modCount和执行方法开始时expectedModCount的不一致了，就会报ConcurrentModificationException。并发修改异常，导致删除失败。这个就是并发是fail-fast机制，可以让当前线程快速失败，而不会产生资源竞争，导致锁之类的现象。这样也导致了ArrayList这个集合类不是线程安全的，不能并发操作。
整个removeIf的亮点主要有两个：一个是使用BitSet记录位置，节省空间且有去重性，很多时候我们只需要记录位置或者索引即可，没必要记录整个元素。一个是fail-fast机制的应用，巧妙的通过维护modCount，当并发更新的一个资源的时候，来快速失败。
整个remove系列除了removeIf没有使用拷贝，当ArrayList中元素很多或者频繁的拷贝，都是有很大性能问题的，而且remove(Objecto)删除的是第一个匹配的元素，这也要注意。
更重要的是，想必大家对阅读源码的思路已经越来越熟悉了。先摸清脉络，再看细节，可以根据方法名、注释、经验连蒙带猜，抓大放小，学会举例，画图等等。如果你已经感觉到了轻车熟路，说明你已经在阅读源码的路上，开始上道了。相信，只要你继续跟随JDK源码成长记，会为你之后阅读更难的源码，打下坚实的基础。
金句甜点
除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：榜样比说服力更重要。
其实很多人，很多时候，不是在看你说什么，而是在看你做什么。就比如有一天我回到家，总是喜欢把外套和裤子随手一扔，但是我老婆是个爱干净的人，总是希望我把衣服挂在衣架上。但是我总是习惯随便一扔，但是她从来会抱怨我把沙发或者床有弄乱了，她总会把自己的衣服挂起来，久而久之，我也就觉得，挂起来的确让家里更整洁，看起来更舒适。后来逐渐的我也就把衣服都挂在了衣架上。其实这就是榜样比说服力更重要的体现。如果你想要孩子吃饭不要总是不玩手机，你自己要先做到，不是吗？如果你想让孩子每天看一篇文章学习，你自己先做到，每天看一篇成长记是不是？
最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。
欢迎大家在评论区留言和我交流。可以的话可以点击《在看》按钮分享给更多需要的人。
（声明：JDK源码成长记基于JDK 1.8版本，部分章节会提到旧版本特点）
本文由博客群发一文多发等运营工具平台 OpenWrite 发布
