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的時候，最常用的除了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 = https://www.cnblogs.com/fanmao/archive/2021/10/16/(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 = https://www.cnblogs.com/fanmao/archive/2021/10/16/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 = https://www.cnblogs.com/fanmao/archive/2021/10/16/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 = https://www.cnblogs.com/fanmao/archive/2021/10/16/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的高級方法探索

最后你還需要來看下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 = https://www.cnblogs.com/fanmao/archive/2021/10/16/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你如果已經掌握了如下內容，就非常好了，

知識和技能

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 發布

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/319591.html

標籤：其他

上一篇：Spring框架入門

下一篇：使用python進行視頻圖片提取