关于java:JDK成长记3ArrayList常用方法源码探索中

无论是程序员的工作、学习，还是生存中的事件。都能够遵循这样一条准则：“，简略的事件反复做，正确的事件反复做。”这样的致力会让你走到邪道上，少走很多弯路。从小司机变成老司机。

上一节你应该曾经把握了 ArrayList 的扩容原理，System.arrayCopy 办法，还有看源码的一些思维和办法。这一节更多的是练习一下学到的思维和办法，带你疾速摸一下 ArrayList 其余罕用办法的源码原理，看看他们外面的一些亮点，这一节还能够让你简略理解下 fail-fast 机制，之前的 modCount 到底是干什么的。

首先你须要批改下你的 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 公布！

驾轻就熟，扫一下 ArrayList 的 set、get 办法

金句甜点