wen 编程最新 2024-01-31

JDK成长记3：ArrayList常用方法源码探索（中）

file

无论是程序员的工作、学习，还是生活中的事情。都可以遵循这样一条原则：“，简单的事情重复做，正确的事情重复做。” 这样的努力会让你走到正道上，少走很多弯路。从小司机变成老司机。

上一节你应该已经掌握了ArrayList的扩容原理，System.arrayCopy方法，还有看源码的一些思想和方法。这一节更多的是练习一下学到的思想和方法，带你快速摸一下ArrayList其他常用方法的源码原理，看看他们里面的一些亮点，这一节还可以让你简单了解下fail-fast机制，之前的modCount到底是干什么的。

轻车熟路，扫一下ArrayList的set、get方法

file

首先你需要修改下你的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的元素，检查是否替换成功。上面逻辑如图所示代码：

file

这里需要额外提一点的是，其实有运维有一条原则，就是操作完成命令和脚本后，一定要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，可以参考这个思路。

源码逻辑如下图所示：

file

接着下来，再来快速看下get方法:

 public E get(int index) {
        rangeCheck(index);
        return elementData(index);
 }

可以看到，get方法的脉络更简单，就是范围检查，校验一下，之后通过基础的数组操作，通过数组下标方式获取元素而已。

这里值得一提的一点是，JDK源码封装的方法都不会太长，很清晰，重用性也很好。这个编码风格值得我们借鉴。但是也不能过于精简，可读性会降低，JDK就有这个问题,这也是因为大多JAVA大牛们喜欢精简至极的代码，这也是可以理解的。

到这里，set和get源码逻辑如下图所示：

file

换汤不换药的，remove系列方法

file

相信，当你看过了add、get、set等方法后，已经越来越熟练和上道了。现在让我们再一起看下ArrayList的remove系列的方法，其实源码底层原理，换汤不换药，还是System.arraycopy那一套。

remove系统方法如下图所示：

file

以上这些就是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;
 }

上面脉络很清晰，比较关键的两行就是计算移动元素的个数，和在原数组上拷贝元素到原数组。其余的几行你应该都已经知道是干什么的了，这里就不赘述了。

源码逻辑如下图所示：

file

System.arraycopy拷贝一般总是不太好理解，所以还是举个例子大家更能理解：

file

这句话你应该不陌生了，现在需要从原数组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);
}

file

从输出结果就能知道只是删除了第一个符合条件的元素。这个你使用起来要注意，如果想删除所有匹配的元素可以使用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机制，下一节也简单给大家提下。

看到这里可以你可以小结为，如下图片：

file

remove系列方法中亮点方法：removeif()

file

这一小节，我们最后再看下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。

第四步返回删除了元素的数量

你可以进入源码，自己尝试去画一下它的流程图，练习一下。这里画一个大致原理图给你：

file

这里我要重点给你讲的是它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源码成长记，会为你之后阅读更难的源码，打下坚实的基础。

金句甜点

file

除了今天知识，技能的成长，给大家带来一个金句甜点，结束我今天的分享：榜样比说服力更重要。

其实很多人，很多时候，不是在看你说什么，而是在看你做什么。就比如有一天我回到家，总是喜欢把外套和裤子随手一扔，但是我老婆是个爱干净的人，总是希望我把衣服挂在衣架上。但是我总是习惯随便一扔，但是她从来会抱怨我把沙发或者床有弄乱了，她总会把自己的衣服挂起来，久而久之，我也就觉得，挂起来的确让家里更整洁，看起来更舒适。后来逐渐的我也就把衣服都挂在了衣架上。其实这就是榜样比说服力更重要的体现。如果你想要孩子吃饭不要总是不玩手机，你自己要先做到，不是吗？如果你想让孩子每天看一篇文章学习，你自己先做到，每天看一篇成长记是不是？

最后，大家可以在阅读完源码后，在茶余饭后的时候问问同事或同学，你也可以分享下，讲给他听听。

欢迎大家在评论区留言和我交流。可以的话可以点击《在看》按钮分享给更多需要的人。

（声明：JDK源码成长记基于JDK 1.8版本，部分章节会提到旧版本特点）

本文由博客群发一文多发等运营工具平台 OpenWrite 发布

hmoban主题是根据ripro二开的主题，极致后台体验，无插件，集成会员系统
自学咖网 » JDK成长记3：ArrayList常用方法源码探索（中）

wen 普通

分享到：

轻车熟路，扫一下ArrayList的set、get方法

换汤不换药的，remove系列方法

remove系列方法中亮点方法：removeif()

金句甜点

wen 普通

相关推荐