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 = https://www.cnblogs.com/fanmao/p/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 = https://www.cnblogs.com/fanmao/p/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 = https://www.cnblogs.com/fanmao/p/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 發布

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

標籤：Java

上一篇：oracle踩坑

下一篇：二(二)、基于注解形式配置bean