Java教程

JDK成长记3:ArrayList常用方法源码探索(中)

本文主要是介绍JDK成长记3:ArrayList常用方法源码探索(中),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

file

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方法的脉络:

  1. 第一步rangeCheck明显是范围检查,是个校验动作;
  2. 第二步是elementData(int index)方法,这个方法通过数组下标方式获取元素,基础的数组操作,通过oldValue记录了下原值;
  3. 第三步就是通过数组下标进行了赋值操作,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 发布

这篇关于JDK成长记3:ArrayList常用方法源码探索(中)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!