JDK成長記8：HashMap的兄弟姐妹們-有解無憂

file

LinkedHashMap的原始碼底層原理

LinkedHashMap繼承自HashMap,但是它的底層增加了一個鏈表來維護插入或者訪問順序，使得LinkedHashMap變動有順序性，如下圖所示：

file

上圖中可以看出，LinkedHashMap繼承了HashMap，多了兩個成員變數，tail和head指標，還使用Entry內部類繼承了HashMap的Node內部類，在原有基礎上增加了before和after指標，

默認情況下，是按照插入順序的，也就是put的順序，LiknedHashMap在put元素的時候會記錄用指標，將陣列元素的插入順序記錄下來，

通過重寫HashMap的newNode()方法，在put方法，插入一個Entry后，Entry的before和last指標類似鏈表會連起來，并且LinkedHashMap的tail和head指標也會記錄下首尾元素，將插入順序用鏈表記錄下來，

至于訪問順序的情況，你可以在一會后面的例子會提到，

TreeMap的原始碼底層原理

同理TreeMap也是一個有序的Map，底層是通過紅黑樹來維持順序的，并且TreeMap支持自定義排序規則，原理下圖所示：

file

TreeMap沒有繼承HashMap，他自己實作了put方法，主要邏輯是生成樹root節點和普通葉子節點，

剛開始樹為空，肯定是進入第一步，生成root節點，創建一個Entry就結束了，這個Entry中多了left和partent、right，color等變數，

創建TreeMap的時候可以指定排序規則，默認不指定使用Key值默認的compare方法,進行排序生成一棵排序后的二叉樹，之后調整為紅黑樹，

而且它沒有陣列的結構，它就是一個純粹的紅黑樹，get的時候通過遍歷紅黑樹獲取元素，

在遍歷的時候，TreeMap通過EntryIterator進行從小到大的遍歷，實作有序訪問，

HashTable、HashSet、LinkedHashSet、TreeSet底層原理

最后我們聊一下HashMap的其他兄弟姐妹，為什么這么說呢？

因為HashTable和HashMap核心區別就是使用synchronized保證執行緒安全，這個和Vector+ArrayList很像，

因為HashSet使用了HashMap，只不過add方法時候的value都是new Object()而已，結合map的特性，同一個key值只能存在一個，map在put的時候，會hash尋址到陣列的同一個位置去，然后覆寫原來的值，所以Set是去重的，默認是無序的，核心代碼如下：

public boolean add(E e) {
       return map.put(e, PRESENT)==null;
}

因為LinkedHashSet繼承了HashSet,此時HashSet通過使用LinkedHashMap是可以進行訪問有序的保證，

因為TreeSet也同理，默認是根據key值的compare方法來排序的，可以自定義Comparator，底層使用了TreeMap，add元素時，同樣是空的Object，同樣去重，但是TreeSet訪問是可以有序，

 public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }

它們的原始碼都極其簡單，沒什么好研究的，所以重點是，你懂了之前的HashMap、LinkedHashMap、TreeMap才是關鍵，**

下面我們來看一些使用這些集合的場景：

LinkedHashMap應用：Storm中的LRUMap

之前你應該熟悉了LinkedHashMap的的插入有序性，呼叫put方法時，通過鏈表記錄插入的順序，但是LinkedHashMap還可以支持訪問有序性，按照get方法的訪問順序，進行排序，比如：

這個底層和插入有序很像，也是通過一個變數叫做accessOrder和HashMap的put方法和get中重寫預留的方法做到的，

每訪問一次元素，會將元素移動鏈表的指標，將剛訪問的元素移動到鏈表的尾部，

基于這個機制我們可以實作一個LRU的Map，實作有自動失效LRU記憶體快取Map,這樣當元素個數超過快取容量時，通過LRU可以保證最近最少訪問的元素被移除掉，

如果你看過storm的原始碼的話，你會看到有這樣一個LRUMap實作：

import java.util.LinkedHashMap;
import java.util.Map;


public class LRUMap<A, B> extends LinkedHashMap<A, B> {
    private int maxSize;


    public LRUMap(int maxSize) {
        super(maxSize + 1, 1.0f, true);
        this.maxSize = maxSize;
    }


    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return size() > maxSize;
    }
}

這個方法很巧妙的基于LinkedHashMap訪問有序，實作了一個LRUMap，

首先通過maxSize限定快取Map的大小，呼叫父類建構式，擴容因子為1.0f，第三個入參表示accessOrder=true，重寫了removeEldestEntry，

其次通過LinkedHashMap,在get方法時候，如果accessOrder是true，會將get到的元素，放到鏈表的尾部，保證Map快取中最新訪問的元素的不會被LRU掉，get方法原始碼如下：

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

可以看到有一個方法afterNodeAccess,通過這個來控制LinkedList訪問時，單向鏈表的順序，從而達到訪問有序，

在put方法的時候有一個擴展的入口afterNodeInsertion中，HashMap默認這個方法是空的，什么都不做，但是LinkedHashMap實作了這個方法，并且通過removeEldestEntry+accessOrder控制，如果訪問有序引數為true，并且頭節點有元素，且 removeEldestEntry 滿足，即size() > maxSize，快取大小達到上限maxSize，會進行一次removeNode操作，移除鏈表第一個元素，第一個元素就是最近最少訪問的元素，如下圖所示：

file

TreeSet和TreeMap應用：HDFS中檔案租約時長維護

在HDFS中LeaseManager，有一個非常經典契約檢查的機制，對所有的契約，按照續約的時間在TreeSet里排序，后面檢查的時候，每次就挑最老的那個契約來檢查，是否超過60分鐘，如果超過，就釋放契約再檢查第二老的那個契約，如果最老的契約都沒過期，那就說明其他的契約肯定都沒過期，

用這個方法，可以巧妙的避免說，后臺執行緒每隔一定時間，就要把所有的契約都遍歷一遍來檢查里面的最近一次續約的時間

如果一個客戶端申請契約過后，超過1小時，都還沒有續約，那么這個契約會被自動釋放掉，這是他的一個很重要的機制，

如下圖所示：

file

好了，到這里，《JDK原始碼成長記》集合篇的知識基本就帶大家學習完了，當然，你一定要結合學到的，不斷自己看原始碼分析思路，之后講給同事，和他們討論一下，才能更多的融會貫通，而不是看過文章之后，80%還給我了，

你可以在評論區回復你遇見的使用這些集合的場景，歡迎你評論，

你也可以搜索下你們的業務代碼，看看使用了哪些集合類，怎么用的，有沒什么隱患？

下一篇我會進行章節總結，也會給大家提供一些常見面試題，讓大家檢測下學習成果，相信大家掌握了原始碼原理后，無論是看原始碼，還是面試，或者應用都可以游刃有余，

金句甜點

除了今天知識，技能的成長，給大家帶來一個金句甜點，結束我今天的分享：堅持的三個秘訣之一個性化，

堅持的秘訣除了之前提到的視徑訓、目標化，最后一個就是個性化，每個人都自己喜歡的事情，你不能堅持你不喜歡的事情，還是那個例子，假如你要減肥，比如你就不喜歡吃西藍花，他雖然是熱量低的食物，的確很適合減脂塑形的時候吃，但是非要你吃，頭兩天還好，你能忍受，但是你肯定是堅持不下來的，你要找到適合你自己的低熱量食物，定制化的調整，不喜歡的事情怎么能堅持下來呢？運動也是一樣，你就是不喜歡做俯臥撐，就喜歡平板支撐，那就換成你喜歡的，你做不了Burbee跳，你就可以做半個等等....而且個性化很重要的一點是比如不喜歡看成長記的時候，覺得費腦子，就看看今日頭條，微博，朋友圈獎勵自己一下，再看一篇成長記，之后再獎勵自己做些自己喜歡的事情，可以做一些重要的事情，在做一些自己喜歡的事情，適當的個性化調整，也是讓你堅持前進，漸漸形成習慣的個性化，時間久了相信你不這么做都會覺得難受的，

所以，當你選擇你能堅持而且喜歡的，變成一個好的習慣，還一直提醒自己覺得值，就一定能堅持下來，記住堅持的秘訣視徑訓、目標化、個性化，你可以試試，

最后，大家可以在閱讀完原始碼后，在茶余飯后的時候問問同事或同學，你也可以分享下，講給他聽聽，

歡迎大家在評論區留言和我交流，

（宣告：JDK原始碼成長記基于JDK 1.8版本，部分章節會提到舊版本特點）

本文由博客群發一文多發等運營工具平臺 OpenWrite 發布

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

標籤：Java

上一篇：常見的JVM引數

下一篇：資料服務基礎能力之元資料管理