09 TreeMap 和 LinkedHashMap 核心源碼解析 · 面試官系統精講Java源碼及大廠真題

## 09 [X]TreeMap 和 LinkedHashMap 核心源碼解析 ## 引導語在熟悉 HashMap 之后，本小節我們來看下 TreeMap 和 LinkedHashMap，看看 TreeMap 是如何根據 key 進行排序的，LinkedHashMap 是如何用兩種策略進行訪問的。 ### 1 知識儲備在了解 TreeMap 之前，我們來看下日常工作中排序的兩種方式，作為我們學習的基礎儲備，兩種方式的代碼如下： ``` @Slf4j public class TreeMapDemo { @Data// DTO 為我們排序的對象 class DTO implements Comparable<DTO> { private Integer id; public DTO(Integer id) { this.id = id; } @Override public int compareTo(DTO o) { //默認從小到大排序 return id - o.getId(); } } @Test public void testIterator() { TreeMap<String,String> m = new TreeMap<>(); m.put("asdf","nihao"); m.put("sdf","nihao"); m.put("df","nihao"); m.keySet().iterator(); } @Test public void testTwoComparable() { // 第一種排序，從小到大排序，實現 Comparable 的 compareTo 方法進行排序 List<DTO> list = new ArrayList<>(); for (int i = 5; i > 0; i--) { list.add(new DTO(i)); } Collections.sort(list); log.info(JSON.toJSONString(list)); // 第二種排序，從大到小排序，利用外部排序器 Comparator 進行排序 Comparator comparator = (Comparator<DTO>) (o1, o2) -> o2.getId() - o1.getId(); List<DTO> list2 = new ArrayList<>(); for (int i = 5; i > 0; i--) { list2.add(new DTO(i)); } Collections.sort(list,comparator); log.info(JSON.toJSONString(list2)); } } ``` 第一種排序輸出的結果從小到大，結果是：`[{“id”:1},{“id”:2},{“id”:3},{“id”:4},{“id”:5}]`；第二種輸出的結果恰好相反，結果是：`[{“id”:5},{“id”:4},{“id”:3},{“id”:2},{“id”:1}]`。以上兩種就是分別通過 Comparable 和 Comparator 兩者進行排序的方式，而 TreeMap 利用的也是此原理，從而實現了對 key 的排序，我們一起來看下。 ### 2 TreeMap 整體架構 TreeMap 底層的數據結構就是紅黑樹，和 HashMap 的紅黑樹結構一樣。不同的是，TreeMap 利用了紅黑樹左節點小，右節點大的性質，根據 key 進行排序，使每個元素能夠插入到紅黑樹大小適當的位置，維護了 key 的大小關系，適用于 key 需要排序的場景。因為底層使用的是平衡紅黑樹的結構，所以 containsKey、get、put、remove 等方法的時間復雜度都是 log(n)。 #### 2.1 屬性 TreeMap 常見的屬性有： ``` //比較器，如果外部有傳進來 Comparator 比較器，首先用外部的 //如果外部比較器為空，則使用 key 自己實現的 Comparable#compareTo 方法 //比較手段和上面日常工作中的比較 demo 是一致的 private final Comparator<? super K> comparator; //紅黑樹的根節點 private transient Entry<K,V> root; //紅黑樹的已有元素大小 private transient int size = 0; //樹結構變化的版本號，用于迭代過程中的快速失敗場景 private transient int modCount = 0; //紅黑樹的節點 static final class Entry<K,V> implements Map.Entry<K,V> {} ``` #### 2.2 新增節點我們來看下 TreeMap 新增節點的步驟： 1. 判斷紅黑樹的節點是否為空，為空的話，新增的節點直接作為根節點，代碼如下： ``` Entry<K,V> t = root; //紅黑樹根節點為空，直接新建 if (t == null) { //key是不是null。 //外部比較器為空的話，也判斷key有沒有實現Comparable compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } ``` 2. 根據紅黑樹左小右大的特性，進行判斷，找到應該新增節點的父節點，代碼如下： ``` Comparator<? super K> cpr = comparator; if (cpr != null) { //找到key應該新增的位置，就是應該掛載那個節點的頭上 do { //當結束時，parent就是t上次比過的對象，t的值和parent的值最接近 parent = t; // 通過 compare 來比較 key 的大小 cmp = cpr.compare(key, t.key); //key小于t，把t左邊的值賦予t，循環再比，紅黑樹左邊的值比較小 if (cmp < 0) t = t.left; //key大于t，把t右邊的值賦予t，循環再比，紅黑樹右邊的值比較大 else if (cmp > 0) t = t.right; //如果相等的話，直接覆蓋原值 else return t.setValue(value); // t 為空，說明已經到葉子節點了 } while (t != null); } ``` 3. 在父節點的左邊或右邊插入新增節點，代碼如下： ``` //cmp 代表最后一次對比的大小，小于 0 ，代表 e 在上一節點的左邊 if (cmp < 0) parent.left = e; //cmp 代表最后一次對比的大小，大于 0 ，代表 e 在上一節點的右邊，相等的情況第二步已經處理了。 else parent.right = e; ``` 4. 著色旋轉，達到平衡，結束。從源碼中，我們可以看到： 1. 新增節點時，就是利用了紅黑樹左小右大的特性，從根節點不斷往下查找，直到找到節點是 null 為止，節點為 null 說明到達了葉子結點； 2. 查找過程中，發現 key 值已經存在，直接覆蓋； 3. TreeMap 是禁止 key 是 null 值的。類似的，TreeMap 查找也是類似的原理，有興趣的同學可以去 github 上面去查看源碼。 #### 2.3 小結 TreeMap 相對來說比較簡單，紅黑樹和 HashMap 比較類似，比較關鍵的是通過 compare 來比較 key 的大小，然后利用紅黑樹左小右大的特性，為每個 key 找到自己的位置，從而維護了 key 的大小排序順序。 ### 3 LinkedHashMap 整體架構 HashMap 是無序的，TreeMap 可以按照 key 進行排序，那有木有 Map 是可以維護插入的順序的呢？接下來我們一起來看下 LinkedHashMap。 LinkedHashMap 本身是繼承 HashMap 的，所以它擁有 HashMap 的所有特性，再此基礎上，還提供了兩大特性： * 按照插入順序進行訪問； * 實現了訪問最少最先刪除功能，其目的是把很久都沒有訪問的 key 自動刪除。接著我們來看下上述兩大特性。 #### 3.1 按照插入順序訪問 #### 3.1.1 LinkedHashMap 鏈表結構我們看下 LinkedHashMap 新增了哪些屬性，以達到了鏈表結構的： ``` // 鏈表頭 transient LinkedHashMap.Entry<K,V> head; // 鏈表尾 transient LinkedHashMap.Entry<K,V> tail; // 繼承 Node，為數組的每個元素增加了 before 和 after 屬性 static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } // 控制兩種訪問模式的字段，默認 false // true 按照訪問順序，會把經常訪問的 key 放到隊尾 // false 按照插入順序提供訪問 final boolean accessOrder; ``` 從上述 Map 新增的屬性可以看到，LinkedHashMap 的數據結構很像是把 LinkedList 的每個元素換成了 HashMap 的 Node，像是兩者的結合體，也正是因為增加了這些結構，從而能把 Map 的元素都串聯起來，形成一個鏈表，而鏈表就可以保證順序了，就可以維護元素插入進來的順序。 #### 3.1.2 如何按照順序新增 LinkedHashMap 初始化時，默認 accessOrder 為 false，就是會按照插入順序提供訪問，插入方法使用的是父類 HashMap 的 put 方法，不過覆寫了 put 方法執行中調用的 newNode/newTreeNode 和 afterNodeAccess 方法。 newNode/newTreeNode 方法，控制新增節點追加到鏈表的尾部，這樣每次新節點都追加到尾部，即可保證插入順序了，我們以 newNode 源碼為例： ``` // 新增節點到鏈表的尾部 Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { // 新增節點 LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); // 節點追加到鏈表的尾部 linkNodeLast(p); return p; } // link at the end of list private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; // 新增節點等于位節點 tail = p; // last 為空，說明鏈表為空，首位節點相等 if (last == null) head = p; // 鏈表有數據，直接建立本節點和上個尾節點之間的前后關系即可 else { p.before = last; last.after = p; } } ``` LinkedHashMap 通過新增頭節點、尾節點，給每個節點增加 before、after 屬性，每次新增時，都把節點追加到尾節點等手段，在新增的時候，就已經維護了按照插入順序的鏈表結構了。 #### 3.1.3 按照順序訪問 LinkedHashMap 只提供了單向訪問，即按照插入的順序從頭到尾進行訪問，不能像 LinkedList 那樣可以雙向訪問。我們主要通過迭代器進行訪問，迭代器初始化的時候，默認從頭節點開始訪問，在迭代的過程中，不斷訪問當前節點的 after 節點即可。 Map 對 key、value 和 entity（節點）都提供出了迭代的方法，假設我們需要迭代 entity，就可使用 LinkedHashMap.entrySet().iterator() 這種寫法直接返回 LinkedHashIterator ，LinkedHashIterator 是迭代器，我們調用迭代器的 nextNode 方法就可以得到下一個節點，迭代器的源碼如下： ``` // 初始化時，默認從頭節點開始訪問 LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; if (modCount != expectedModCount)// 校驗 throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; // 通過鏈表的 after 結構，找到下一個迭代的節點 return e; } ``` 在新增節點時，我們就已經維護了元素之間的插入順序了，所以迭代訪問時非常簡單，只需要不斷的訪問當前節點的下一個節點即可。 ### 3.2 訪問最少刪除策略 #### 3.2.1 demo 這種策略也叫做 LRU（Least recently used,最近最少使用），大概的意思就是經常訪問的元素會被追加到隊尾，這樣不經常訪問的數據自然就靠近隊頭，然后我們可以通過設置刪除策略，比如當 Map 元素個數大于多少時，把頭節點刪除，我們寫個 demo 方便大家理解。demo 如下，完整代碼可到 github 上查看： ``` public void testAccessOrder() { // 新建 LinkedHashMap LinkedHashMap<Integer, Integer> map = new LinkedHashMap<Integer, Integer>(4,0.75f,true) { { put(10, 10); put(9, 9); put(20, 20); put(1, 1); } @Override // 覆寫了刪除策略的方法，我們設定當節點個數大于 3 時，就開始刪除頭節點 protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > 3; } }; log.info("初始化：{}",JSON.toJSONString(map)); Assert.assertNotNull(map.get(9)); log.info("map.get(9)：{}",JSON.toJSONString(map)); Assert.assertNotNull(map.get(20)); log.info("map.get(20)：{}",JSON.toJSONString(map)); } ``` 打印出來的結果如下： ``` 初始化：{9:9,20:20,1:1} map.get(9)：{20:20,1:1,9:9} map.get(20)：{1:1,9:9,20:20} ``` 可以看到，map 初始化的時候，我們放進去四個元素，但結果只有三個元素，10 不見了，這個主要是因為我們覆寫了 removeEldestEntry 方法，我們實現了如果 map 中元素個數大于 3 時，我們就把隊頭的元素刪除，當 put(1, 1) 執行的時候，正好把隊頭的 10 刪除，這個體現了達到我們設定的刪除策略時，會自動的刪除頭節點。當我們調用 map.get(9) 方法時，元素 9 移動到隊尾，調用 map.get(20) 方法時，元素 20 被移動到隊尾，這個體現了經常被訪問的節點會被移動到隊尾。這個例子就很好的說明了訪問最少刪除策略，接下來我們看下原理。 #### 3.2.2 元素被轉移到隊尾我們先來看下為什么 get 時，元素會被移動到隊尾： ``` public V get(Object key) { Node<K,V> e; // 調用 HashMap get 方法 if ((e = getNode(hash(key), key)) == null) return null; // 如果設置了 LRU 策略 if (accessOrder) // 這個方法把當前 key 移動到隊尾 afterNodeAccess(e); return e.value; } ``` 從上述源碼中，可以看到，通過 afterNodeAccess 方法把當前訪問節點移動到了隊尾，其實不僅僅是 get 方法，執行 getOrDefault、compute、computeIfAbsent、computeIfPresent、merge 方法時，也會這么做，通過不斷的把經常訪問的節點移動到隊尾，那么靠近隊頭的節點，自然就是很少被訪問的元素了。 #### 3.2.3 刪除策略上述 demo 我們在執行 put 方法時，發現隊頭元素被刪除了，LinkedHashMap 本身是沒有 put 方法實現的，調用的是 HashMap 的 put 方法，但 LinkedHashMap 實現了 put 方法中的調用 afterNodeInsertion 方法，這個方式實現了刪除，我們看下源碼： ``` // 刪除很少被訪問的元素，被 HashMap 的 put 方法所調用 void afterNodeInsertion(boolean evict) { // 得到元素頭節點 LinkedHashMap.Entry<K,V> first; // removeEldestEntry 來控制刪除策略，如果隊列不為空，并且刪除策略允許刪除的情況下，刪除頭節點 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; // removeNode 刪除頭節點 removeNode(hash(key), key, null, false, true); } } ``` ### 3.3 小結 LinkedHashMap 提供了兩個很有意思的功能：按照插入順序訪問和刪除最少訪問元素策略，簡單地通過鏈表的結構就實現了，設計得非常巧妙。 ## 總結本小節主要說了 TreeMap 和 LinkedHashMap 的的數據結構，分析了兩者的核心內容源碼，我們發現兩者充分利用了底層數據結構的特性，TreeMap 利用了紅黑樹左小右大的特性進行排序，LinkedHashMap 在 HashMap 的基礎上簡單地加了鏈表結構，就形成了節點的順序，非常巧妙，很有意思，大家可以在看源碼的過程中，可以多想想設計思路，說不定會有不一樣的感悟。