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

写在后面的话

有的同学问我，开始讲的很根底，节奏比较慢，这个是因为一个为了让大家缓缓进入状态，前面的节奏会越来越快的，大家不要焦急，另一个是因为简略的货色反复，温故而知新，更心愿给你们带来的是思维和观点的成长，这个须要铺垫。这个有点像练武功，要想练就浅近的文治,须要循序渐进，不然很容易走火入魔的，所以要把根基打扎实，不能焦急。这里剧透下，前面会给大家带来一个一个绝世功法：《HDFS成长记》、《ZK成长记》、《Spring Cloud Alibaba成长记》、《Spring Cloud 成长记》、《Kafka成长记》、《Redis成长记》、《MySQL成长记》等等。也会有一些根底心法，比方《Netty 成长记》、《JVM成长记》《OS 成长记》、《网络成长记》等等。

好了，不多说了，让咱们开始吧！

通过之前的三节，置信你曾经对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的源码原理，如下图：

咱们再看看办法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类。如下图所示：

没错，这个就是咱们常称的迭代器，他是汇合中常见的遍历工具。你能够接着往下看：

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。

源码原理如下所示：

之后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];
 }
// 省略无关代码
}

只有四行代码是不是就个很清晰了？你还能够在画个图：

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

执行实现一次循环后，Itr变量如下图所示：

ltr的next()办法实质其实就是通过一个外部cursor变量，每次向后遍历数组时，保留遍历数组的地位，通过数组根本的下标拜访元素返回而已，这下你就把握了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

其实这是一个优化后的迭代器，能够向前向后挪动cursor，previous()源码逻辑和next()向后挪动没什么区别。你到这里就能够总结下：

1. ArrayList有两个迭代器Itr和ListItr，一个能够向后迭代，一个能够既向前又向后迭代拜访ArrayList。(其实ArrayList父类AbstractList有2个通用的迭代器，和这个原理是一样的，大家有趣味能够去看看，如果子类没有自定义本人的迭代器，会应用父类的迭代器。)

2. 这两个迭代器不是并发平安的，如果有别的线程批改modCount，通过fail-fast机制，迭代拜访会抛出ConcurrentModificationException，并发批改的异样，中断迭代。

3. 遍历List的思维万变不离其宗，次要就是通过for循环+下标的形式或者指针挪动的两种形式实现思路而已。

ArrayList的高级办法摸索

<div class=”output_wrapper” id=”output_wrapper_id” style=”width:fit-content;font-size: 16px; color: rgb(62, 62, 62); line-height: 1.6; word-spacing: 0px; letter-spacing: 0px; font-family: ‘Helvetica Neue’, Helvetica, ‘Hiragino Sans GB’, ‘Microsoft YaHei’, Arial, sans-serif;”><h3 id=”hdddd” style=”width:fit-content;line-height: inherit; margin: 1.5em 0px; font-weight: bold; font-size: 1.3em; margin-bottom: 2em; margin-right: 5px; padding: 8px 15px; letter-spacing: 2px; background-image: linear-gradient(to right bottom, rgb(43,48,70), rgb(43,48,70)); background-color: rgb(63, 81, 181); color: rgb(255, 255, 255); border-left: 10px solid rgb(255,204,0); border-radius: 5px; text-shadow: rgb(102, 102, 102) 1px 1px 1px; box-shadow: rgb(102, 102, 102) 1px 1px 2px;”><span style=”font-size: inherit; color: inherit; line-height: inherit; margin: 0px; padding: 0px;”>ArrayList的高级办法摸索</span></h3></div>

最初你还须要来看下ArrayList的一些高级办法的源码，这里倡议你看下它外部提供的toArray办法、subList办法的源码。至于其余的addAll()、indexof()之类的办法大家能够自行去看下。这里次要看下toArray和subList相干的外部类和办法，它们次要有如下脉络：

能够先看下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数组拷贝元素到新数组。

原理图如下：

之后咱们再看下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);
}

为什么呢？能够看源码来找下起因。这就是浏览源码的益处之一。因为很多时候当你线上遇到技术问题的时候，你对源码很相熟，就能很快定位问题起因，解决问题。当你技术调研的时候，选型后，最好要摸下你选的技术的源码，当应用除了问题你也能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<E> parent。再看看subList的其余办法，都是基于原数组的数据进行操作，只不过是本人依据fromIndex,toIndex限定了拜访范畴而已。

那最终意思不就是说SubList和ArrayList共用了通过Object[]数组的数据么，所以当批改的时候都会变动。这是你应用subList肯定要要留神的。

源码原理图如下所示：

到这里，ArrayList的源码你应该把握了大部分了，然而记住还是那句话，重要的不是常识和技能自身，你更应该需学会的是看源码的思维和技巧，解决问题的思路和办法。

ArrayList的小结

对了这里，附加一个小结，总结也是十分重要的思维。前面我会逐步讲到。学完ArrayList你如果曾经把握了如下内容，就十分好了。

常识和技能

ArrayList底层数据结构是Objec[]数组，长处是便于随机拜访，常用语向尾部增加元素后，遍历拜访。毛病是频繁扩容或者两头减少数据，删除数据会造成拷贝，影响性能。
ArrayList默认初始化大小为0，第一次增加元素时，大小初始为10。
ArrayList第一次增加就会产生扩容，为10，之后每次扩容大小为原来的1.5倍。外部通过右移1位进行扩容大小的计算的。
ArrayList add元素到尾部产生的扩容时或add元素到某个地位时，又或者删除元素时，会产生数组拷贝，底层通过system.copyOf实现拷贝性能。
ArrayList不是线程平安的，多线程操作，在遍历和removeIf等时候，会触发fail-fast机制，通过modCount来实现的。
把握了根本的根本办法和高级办法toArray、subList、迭代器Itr、ListItr等底层源码的原理

观点和思维

学会了先脉络后细节、抓大放小、连蒙带猜等浏览源码的思维
学会了画图、举例子剖析问题的办法
有了成长比胜利更重要、楷模比说服力更重要、扭转本人比扭转他人更重要、借力比致力更重要的观点

金句甜点

除了明天常识，技能的成长，给大家带来一个金句甜点，完结我明天的分享：借力比致力更重要。

一个人的致力诚然很重要，然而很多时候借力更重要。就像有句名言所说：站在伟人的肩膀上。这个不是真的站在某个人的肩膀上，而是指的前人的智慧和教训上很重要。就比方有一次我加入公司的降职演讲，本人做好了PPT，还练习了几次，感觉必定没有问题了，就间接加入了降职演讲评审。后果，很可怜的是，PPT右下角的公司log是去年的，公司曾经更换了品牌log，最初一页的致谢的PPT，公司名称也写错了。导致有一位评审收入，起初我才晓得他是人力部门的HR总监。很遗憾的因为错失了她这一票，刚好导致我落选了。其实演讲前，我的Leader跟我说过，写好了PPT要给他看一下，我当初感觉齐全没必要。其实就是犯了很大一个谬误，因为我的Leader的教训比我丰盛，他降职过很屡次，汇报过很屡次，在这不便很有见地，我没有借他的力，导致了这次失败。所以我吸取教训，下次降职时，找了Leader，他帮我一页一页的过PPT，最终顺利的通过了降职。

这个故事其实就通知咱们，借力比致力更重要。你肯定要向比你有教训的人求教，他就是你的老师，这就是一种借力。当然选一个平台也是借力，就像大家通过成长记来成长本人，站在我的教训上少走弯路是不是一样在借力。所以欢送大家持续关注成长记。

最初，你能够浏览完源码后，在茶余饭后的时候问问共事或同学，你也能够分享下，讲给他听听。

欢送大家在评论区留言和我交换。

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

本文由博客一文多发平台 OpenWrite 公布！

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

写在后面的话

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

ArrayList居然有一个优化后的迭代器！

ArrayList的高级办法摸索

ArrayList的小结

金句甜点

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

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

写在后面的话

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

ArrayList居然有一个优化后的迭代器！

ArrayList的高级办法摸索

ArrayList的小结

金句甜点

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复