Java教程

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

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

file

写在前面的话

写在前面的话

有的同学问我,开始讲的很基础,节奏比较慢,这个是因为一个为了让大家慢慢进入状态,后面的节奏会越来越快的,大家不要着急,另一个是因为简单的东西重复,温故而知新,更希望给你们带来的是思想和观念的成长,这个需要铺垫。这个有点像练武功,要想练就高深的武功,需要循序渐进,不然很容易走火入魔的,所以要把根基打扎实,不能着急。这里剧透下,后面会给大家带来一个一个绝世功法:《HDFS成长记》、《ZK成长记》、《Spring Cloud Alibaba成长记》、《Spring Cloud 成长记》、《Kafka成长记》、《Redis成长记》、《MySQL成长记》等等。也会有一些基础心法,比如《Netty 成长记》、《JVM成长记》《OS 成长记》、《网络成长记》等等。

好了,不多说了,让我们开始吧!

file

通过之前的三节,相信你已经对ArrayList中大多方法的底层逻辑都有了很深入的了解,最为ArrayList的最后一节,这节跟大家看下ArrayList的遍历和一些高级方法的底层原理,最后让你可以对ArrayList底层了如执掌,面对各种ArrayList的面试题能对答如流,甚至可以手撸一个ArrayList的代码出来。

ArrayList的遍历到底有什么猫腻呢?

ArrayList的遍历到底有什么猫腻呢?

当你使用ArrayList的时候,最常用的除了add方法,是不是就是for循环的遍历。一般你遍历ArrayList,无非就是一下几种方法:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ArrayListDemo {
  public static void main(String[] args) {
    List<String> hostList = new ArrayList<>(3);
        hostList.add("host1");
        hostList.add("host2");
        hostList.add("host3");
        //方法1
        for (int i = 0; i < hostList.size(); i++) {
            System.out.println(hostList.get(i));
        }
        //方法2
        for (String host : hostList) {
            System.out.println(host);
        }
        //方法3
        for (Iterator<String> iterator = hostList.iterator(); iterator.hasNext();) {
            String host =  iterator.next();
            System.out.println(host);
        }
        //方法4       
        hostList.forEach(host->System.out.println(host));

        //方法5 这种遍历涉及stream底层源码,这里我们不做过多探索
        hostList.stream().forEach(host->System.out.println(host));  
    }    
}

方法1,这种方式使用了for循环,通过get方法访问元素,你应该知道底层就是数组基本操作elementData[index]。

方法2底层其实和方法3是一模一样的,只不过方法2只是一种便捷的语法糖而已,方便让你使用。

方法4底层和方法1是一样的,都是用来for循环+数组基本操作elementData[index]。

方法5 是通过Java8 stream的API进行forEach,这里我们不做过多探索,一般也不建议这么使用,不如使用方法4有效率。

所以值得你探索的两个方法是方法3和方法4的源码,先看下forEach的源码:

@Override
public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    for (int i=0; modCount == expectedModCount && i < size; i++) {
         action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
         throw new ConcurrentModificationException();
    }
}

直接看到核心脉络就是for循环,通过数组基本操作elementData[index]访问数组获取到对应元素,传递给了Java8的Consumer函数表达式,执行对应的逻辑。这个和你自己写for循环,执行自己的逻辑是不是一样的,所以说这种方法和之前的方法1本质没有什么区别,也就是换了一个语法糖而已。

方法1和方法4的源码原理,如下图:

file

我们再看看方法3 Iterator的源码:

for (Iterator<String> iterator = hostList.iterator(); iterator.hasNext();) {
        String host =  iterator.next();
        System.out.println(host);
 }

根据for循环执行逻辑,第一句执行的方法应该是hostList.iterator(),你可以在ArrayList的源码中看到这个方法:

public Iterator<E> iterator() {
        return new Itr();
}

可以看到直接返回了一个new Itr()对象,这个类不知道你还有没有印象?记得第一节看ArrayList的源码脉络的时候,有几个内部类,其中是不是就有一个lrt类。如下图所示:

file

没错,这个就是我们常称的迭代器,他是集合中常见的遍历工具。你可以接着往下看:

private class Itr implements Iterator<E> {
    Itr() {}
       // 省略无关代码
}

你会发现构造函数什么都没有做。那么for循环接着执行条件表达式iterator.hasNext();即如下代码:

private int size;
private class Itr implements Iterator<E> {
  int cursor;
  public boolean hasNext() {
      return cursor != size;
   }   
   // 省略无关代码
}

这里意思是如果cursor的值和数组大小不相等,就返回false。cursor是int类型,所以默认值是0。上面的Demo中,size=3,第一次遍历肯定cursor=0 != size=3所以直接返回true。

源码原理如下所示:

file

之后for循环执行循环体,会执行Stringhost = iterator.next();这句话的源码如下:

private int size;
transient Object[] elementData;
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
        public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
 }
  final void checkForComodification() {
      if (modCount != expectedModCount)
          throw new ConcurrentModificationException();
   }
// 省略无关代码
 }

还是先看下脉络,首先checkForComodification应该是在做并发访问检查,使用i变量保存了cusor值,之后if在做了校验,再之后获取到了ArrayList的elementData数组,再次做了并发访问检查,之后修改了下cursor 值,将i的值赋值给了lastRet变量,并且通过下标访问了下数组,最后就返回了。看上去是不是有点找不到重点?让我们抓大放小下,其实去掉并发校验和普通校验,代码逻辑就很清楚了,就会变成如下所示:

private int size;
transient Object[] elementData;
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
        public E next() {
            int i = cursor;
            Object[] elementData = ArrayList.this.elementData;
            cursor = i + 1;
            return (E) elementData[lastRet = i];
 }
// 省略无关代码
}

只有四行代码是不是就个很清晰了?你还可以在画个图:

file

执行过程就如左边的图所示,结果就是如右图所示。通过抓大放小和画图,是不是对源码的思路就清晰很多了?

执行完成一次循环后,Itr变量如下图所示:

file

ltr的next()方法本质其实就是通过一个内部cursor变量,每次向后遍历数组时,保存遍历数组的位置,通过数组基本的下标访问元素返回而已,这下你就掌握了ArrayList迭代器的本质或者说是底层原理了吧。

ArrayList竟然有一个优化后的迭代器!

ArrayList竟然还有一个优化后的迭代器!

看过了各种遍历方式的源码,大家不知道有什么感觉?是不是感觉也没有神秘的,其实原理很简单,让你自己写一个类似的功能是不是就可以参考这个思路呢?但是不知道你有没有发现ArrayList还有一个迭代器叫做ListItr的内部类,它优势做什么的呢?

直接可以看下源码:

  private class ListItr extends Itr implements ListIterator<E> {
        ListItr(int index) {
            super();
            cursor = index;
        }

        public boolean hasPrevious() {
            return cursor != 0;
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor - 1;
        }

        @SuppressWarnings("unchecked")
        public E previous() {
            checkForComodification();
            int i = cursor - 1;
            if (i < 0)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i;
            return (E) elementData[lastRet = i];
        }
    // 省略无关代码
}

从可以发现它继承了Itr这个类,之后你可以根据方法名字连蒙带猜下,可以猜到它只是实现了向前遍历的功能而已,因为正常情况的迭代器是只能向后迭代,不能向前访问的。但是你可以通过这个ListItr迭代器实现向前访问。比如:

public static void main(String[] args) {
    List<String> hostList = new ArrayList<>(3);
    hostList.add("host1");
    hostList.add("host2");
    hostList.add("host3");
    //方法3
    for (ListIterator<String> iterator = hostList.listIterator(); iterator.hasNext();) {
         System.out.println(iterator.next());
         System.out.println(iterator.next());
         System.out.println(iterator.previous());
         break;
    }
}

结果会输出如下:

host1

host2

host2

其实这是一个优化后的迭代器,可以向前向后移动cursor,previous()源码逻辑和next()向后移动没什么区别。你到这里就可以总结下:

1. ArrayList有两个迭代器Itr和ListItr,一个可以向后迭代,一个可以既向前又向后迭代访问ArrayList。(其实ArrayList父类AbstractList有2个通用的迭代器,和这个原理是一样的,大家有兴趣可以去看看,如果子类没有自定义自己的迭代器,会使用父类的迭代器。)

2. 这两个迭代器不是并发安全的,如果有别的线程修改modCount,通过fail-fast机制,迭代访问会抛出ConcurrentModificationException,并发修改的异常,中断迭代。

3. 遍历List的思想万变不离其宗,主要就是通过for循环+下标的方式或者指针移动的两种方式实现思路而已。

ArrayList的高级方法探索

ArrayList的高级方法探索

最后你还需要来看下ArrayList的一些高级方法的源码,这里建议你看下它内部提供的toArray方法、subList方法的源码。至于其他的addAll()、indexof()之类的方法大家可以自行去看下。这里主要看下toArray和subList相关的内部类和方法,它们主要有如下脉络:

file

可以先看下toArray方法的源码:

public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
}}

    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

第一个toArray方法的源码,底层直接使用了Arrays.copyOf。你应该知道它底层其实就是使用System.arraycopy方法,拷贝的元素个数是size个,也就是全部元素到一个copy数组中,之后就直接返回了。

第二个T[]toArray(T[] a),需要你传递一个目标数组,它内部有两个if判断,根据目标数组大小,拷贝元素。

  • 如果目标数组比ArrayList的数据少,通过Arrays.copyOf扩容成和ArrayList一样大小的数组返回。

  • 如果目标数组比当前ArrayList的大,就直接用System.arraycopy拷贝ArrayList中所有元素,目标数组多余元素置为null。

toArray方法本质就是使用System.arraycopy从ArrayList的Obeject数组拷贝元素到新数组。

原理图如下:

file

之后我们再看下subList方法,可以先写个demo体验下:

public static void main(String[] args) {
    List<String> hostList = new ArrayList<>(3);
    hostList.add("host1");
    hostList.add("host2");
    hostList.add("host3");

    List<String> subList = hostList.subList(1,2);
    System.out.println(subList);
    System.out.println(hostList);
    subList.set(0, "host4");
    System.out.println(subList);
    System.out.println(hostList);
}

file

为什么呢?可以看源码来找下原因。这就是阅读源码的好处之一。因为很多时候当你线上遇到技术问题的时候,你对源码很熟悉,就能很快定位问题原因,解决问题。当你技术调研的时候,选型后,最好要摸下你选的技术的源码,当使用除了问题你也能hold住,是不是?

subList的源码如下:

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

和Itr类似,创建了一个内部类SubList的对象。继续点进去看下:

private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }

        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            return ArrayList.this.elementData(offset + index);
        }

        public int size() {
            checkForComodification();
            return this.size;
        }

        public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            E result = parent.remove(parentOffset + index);
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }
  //省略其他方法
}

可以看出来在构造函数的传入了this, new SubList(this, 0, fromIndex, toIndex);而这个this就是ArrayList创建的对象本身,将this赋值给了Sublist的一个变量:private final AbstractList parent。再看看subList的其他方法,都是基于原数组的数据进行操作,只不过是自己根据fromIndex,toIndex限定了访问范围而已。

那最终意思不就是说SubList和ArrayList共用了通过Object[]数组的数据么,所以当修改的时候都会变化。这是你使用subList一定要要注意的。

源码原理图如下所示:

file

到这里,ArrayList的源码你应该掌握了大部分了,但是记住还是那句话,重要的不是知识和技能本身,你更应该需学会的是看源码的思想和技巧,解决问题的思路和方法。

ArrayList的小结

ArrayList小结

对了这里,附加一个小结,总结也是非常重要的思想。后面我会逐渐讲到。学完ArrayList你如果已经掌握了如下内容,就非常好了。

知识和技能

  1. ArrayList底层数据结构是Objec[]数组,优点是便于随机访问,常用语向尾部添加元素后,遍历访问。缺点是频繁扩容或者中间增加数据,删除数据会造成拷贝,影响性能。
  2. ArrayList默认初始化大小为0,第一次添加元素时,大小初始为10。
  3. ArrayList第一次添加就会产生扩容,为10,之后每次扩容大小为原来的1.5倍。内部通过右移1位进行扩容大小的计算的。
  4. ArrayList add元素到尾部发生的扩容时或add元素到某个位置时,又或者删除元素时,会发生数组拷贝,底层通过system.copyOf实现拷贝功能。
  5. ArrayList不是线程安全的,多线程操作,在遍历和removeIf等时候,会触发fail-fast机制,通过modCount来实现的。
  6. 掌握了基本的基本方法和高级方法toArray、subList、迭代器Itr、ListItr等底层源码的原理

观念和思想

  1. 学会了先脉络后细节、抓大放小、连蒙带猜等阅读源码的思想
  2. 学会了画图、举例子分析问题的方法
  3. 有了成长比成功更重要、榜样比说服力更重要、改变自己比改变别人更重要、借力比努力更重要的观念

金句甜点

金句甜点

除了今天知识,技能的成长,给大家带来一个金句甜点,结束我今天的分享:借力比努力更重要。

一个人的努力固然很重要,但是很多时候借力更重要。就像有句名言所说:站在巨人的肩膀上。这个不是真的站在某个人的肩膀上,而是指的前人的智慧和经验上很重要。就比如有一次我参加公司的晋升演讲,自己做好了PPT,还练习了几次,觉得肯定没有问题了,就直接参加了晋升演讲评审。结果,很不幸的是,PPT右下角的公司log是去年的,公司已经更换了品牌log,最后一页的致谢的PPT,公司名称也写错了。导致有一位评审支出,后来我才知道他是人力部门的HR总监。很遗憾的由于错失了她这一票,刚好导致我落选了。其实演讲前,我的Leader跟我说过,写好了PPT要给他看一下,我当初觉得完全没必要。其实就是犯了很大一个错误,因为我的Leader的经验比我丰富,他晋升过很多次,汇报过很多次,在这方便很有见地,我没有借他的力,导致了这次失败。所以我吸取教训,下次晋升时,找了Leader,他帮我一页一页的过PPT,最终顺利的通过了晋升。

这个故事其实就告诉我们,借力比努力更重要。你一定要向比你有经验的人请教,他就是你的老师,这就是一种借力。当然选一个平台也是借力,就像大家通过成长记来成长自己,站在我的经验上少走弯路是不是一样在借力。所以欢迎大家继续关注成长记。

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

欢迎大家在评论区留言和我交流。

(声明:JDK源码成长记基于JDK 1.8版本,部分章节会提到旧版本特点)

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

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