阿里的上下班時間是1095,這么忙也不能耽誤更新《解讀Java源碼專欄》,在這個系列中,我將手把手帶著大家剖析Java核心組件的源碼,內容包含集合、線程、線程池、并發、隊列等,深入了解其背后的設計思想和實現細節,輕松應對工作面試。
這是解讀Java源碼系列的第五篇,將跟大家一起學習Java中比較神秘的數據結構 - LinkedHashMap。
新手程序員在使用HashMap的時候,會有個疑問,為什么存到HashMap中的數據不是有序的?
這其實跟HashMap的底層設計有關,HashMap并不是像ArrayList那樣,按照元素的插入順序存儲。而是先計算key的哈希值,再用哈希值對數組長度求余,算出數組下標,存儲到下標所在的位置,如果該位置上存在鏈表或者紅黑樹,再把這個元素插入到鏈表或者紅黑樹上面。
這樣設計,可以實現快速查詢,也就犧牲了存儲順序。因為不同key的哈希值差別很大,所以在數組中存儲是無序的。
然而,有時候我們在遍歷HashMap的時候,又希望按照元素插入順序迭代,有沒有什么方式能實現這個需求?
有的,就是今天的主角LinkedHashMap,不但保證了HashMap的性能,還實現了按照元素插入順序或者訪問順序進行迭代。
在這篇文章中,你將學到以下內容:
LinkedHashMap繼承自HashMap,是HashMap的子類,內部額外維護了一個雙鏈表,來保證元素的插入順序或訪問順序,用空間換時間。 與HashMap相比,LinkedHashMap有三個優點:
圖片
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> { /** * 頭節點 */ transient Entry<K, V> head; /** * 尾節點 */ transient Entry<K, V> tail; /** * 迭代排序方式,true表示按照訪問順序,false表示按照插入順序 */ final boolean accessOrder; /** * 雙鏈表的節點類 */ static class Entry<K, V> extends HashMap.Node<K, V> { /** * 雙鏈表的前驅節點和后繼節點 */ Entry<K, V> before, after; /** * 構造雙鏈表的節點 * * @param hash 哈希值 * @param key 鍵 * @param value 值 * @param next 后繼節點 */ Entry(int hash, K key, V value, Node<K, V> next) { super(hash, key, value, next); } }}
可以看出LinkedHashMap繼承自HashMap,在HashMap的單鏈表Node節點的基礎上,增加了前驅節點before、后繼節點after、頭節點head、尾節點tail,擴展成了雙鏈表節點Entry,并記錄了迭代排序方式accessOrder。
LinkedHashMap常見的初始化方法有四個方法:
/** * 無參初始化 */Map<Integer, Integer> map1 = new LinkedHashMap<>();/** * 指定容量大小的初始化 */Map<Integer, Integer> map2 = new LinkedHashMap<>(16);/** * 指定容量大小、負載系數的初始化 */Map<Integer, Integer> map3 = new LinkedHashMap<>(16, 0.75f);/** * 指定容量大小、負載系數、迭代順序的初始化 */Map<Integer, Integer> map4 = new LinkedHashMap<>(16, 0.75f, true);
再看一下構造方法的底層實現:
/** * 無參初始化 */public LinkedHashMap() { super(); accessOrder = false;}/** * 指定容量大小的初始化 */public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false;}/** * 指定容量大小、負載系數的初始化 * * @param initialCapacity 初始容量 * @param loadFactor 負載系數 */public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;}/** * 指定容量大小、負載系數、迭代順序的初始化 * * @param initialCapacity 初始容量 * @param loadFactor 負載系數 * @param accessOrder 迭代順序,true表示按照訪問順序,false表示按照插入順序 */public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;}
LinkedHashMap的構造方法底層都是調用的HashMap的構造方法,迭代順序accessOrder默認是false,表示按照元素插入順序迭代,可以在初始化LinkedHashMap的時候指定為 true,表示按照訪問順序迭代。
LinkedHashMap的put方法完全使用的是HashMap的put方法,并沒有重新實現。不過HashMap中定義了一些空方法,留給子類LinkedHashMap去實現。 有以下三個方法:
public class HashMap<K, V> { /** * 在訪問節點后執行的操作 */ void afterNodeAccess(Node<K, V> p) { } /** * 在插入節點后執行的操作 */ void afterNodeInsertion(boolean evict) { } /** * 在刪除節點后執行的操作 */ void afterNodeRemoval(Node<K, V> p) { } }
在HashMap的put源碼中就調用前兩個方法:
圖片
看一下afterNodeInsertion()方法的源碼,看一下再插入節點后要執行哪些操作? 在插入節點后,只執行了一個操作,就是判斷是否刪除最舊的節點。removeEldestEntry()方法默認返回false,表示不需要刪除節點。我們也可以重寫removeEldestEntry()方法,當元素數量超過閾值時,返回true,表示刪除最舊的節點。
/** * 在插入節點后執行的操作(刪除最舊的節點) */void afterNodeInsertion(boolean evict) { Entry<K, V> first; // 判斷是否需要刪除當前節點 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; // 調用HashMap的刪除節點的方法 removeNode(hash(key), key, null, false, true); }}/** * 是否刪除最舊的節點,默認是false,表示不刪除 */protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return false;}
由于afterNodeInsertion()方法并沒有把新節點插入到雙鏈表中,所以LinkedHashMap又重寫創建節點的newNode()方法,在newNode()方法中把新節點插入到雙鏈表。
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V> { /** * 創建鏈表節點 */ @Override Node<K, V> newNode(int hash, K key, V value, Node<K, V> e) { // 1. 創建雙鏈表節點 LinkedHashMap.Entry<K, V> p = new LinkedHashMap.Entry<K, V>(hash, key, value, e); // 2. 追加到鏈表末尾 linkNodeLast(p); return p; } /** * 創建紅黑樹節點 */ @Override TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) { // 1. 創建紅黑樹節點 TreeNode<K, V> p = new TreeNode<K, V>(hash, key, value, next); // 2. 追加到鏈表末尾 linkNodeLast(p); return p; } /** * 追加到鏈表末尾 */ private void linkNodeLast(LinkedHashMap.Entry<K, V> p) { LinkedHashMap.Entry<K, V> last = tail; tail = p; if (last == null) { head = p; } else { p.before = last; last.after = p; } }}
再看一下 get 方法源碼,LinkedHashMap的 get 方法是直接調用的HashMap的get方法邏輯,在獲取到value 后,判斷 value 不為空,就執行afterNodeAccess()方法邏輯,把該節點移動到鏈表末尾,afterNodeAccess()方法邏輯在前面已經講過。
/** * get方法入口 */public V get(Object key) { Node<K,V> e; // 直接調用HashMap的get方法源碼 if ((e = getNode(hash(key), key)) == null) { return null; } // 如果value不為空,并且設置了accessOrder為true(表示迭代順序為訪問順序),就執行訪問節點后的操作 if (accessOrder) { afterNodeAccess(e); } return e.value;}
看一下afterNodeAccess()方法的源碼實現,看一下在訪問節點要做哪些操作?afterNodeAccess()方法的邏輯也很簡單,核心邏輯就是把當前節點移動到鏈表末尾,分為三步:
/** * 在訪問節點后執行的操作(把節點移動到鏈表末尾) */void afterNodeAccess(Node<K, V> e) { Entry<K, V> last; // 當accessOrder為true時,表示按照訪問順序,這時候才需要更新鏈表 // 并且判斷當前節點不是尾節點 if (accessOrder && (last = tail) != e) { Entry<K, V> p = (Entry<K, V>) e, b = p.before, a = p.after; // 1. 斷開當前節點與后繼節點的連接 p.after = null; if (b == null) { head = a; } else { b.after = a; } // 2. 斷開當前節點與前驅節點的連接 if (a != null) { a.before = b; } else { last = b; } // 3. 把當前節點插入到鏈表末尾 if (last == null) { head = p; } else { p.before = last; last.after = p; } tail = p; ++modCount; }}
LinkedHashMap的 remove 方法完全使用的是 HashMap 的 remove 方法,并沒有重新實現。不過 HashMap的 remove 中調用了afterNodeRemoval?(),執行刪除節點后邏輯,LinkedHashMap重寫了該方法的邏輯。
圖片
/** * 在刪除節點后執行的操作(從雙鏈表中刪除該節點) */void afterNodeRemoval(Node<K, V> e) { LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e, b = p.before, a = p.after; p.before = p.after = null; // 1. 斷開當前節點與前驅節點的連接 if (b == null) { head = a; } else { b.after = a; } // 2. 斷開當前節點與后繼節點的連接 if (a == null) { tail = b; } else { a.before = b; }}
現在可以回答文章開頭提出的問題:
答案:LinkedHashMap繼承自HashMap,是HashMap的子類。
答案:除了保證了與HashMap一樣高效的查詢和插入性能外,還支持以插入順序或者訪問順序進行迭代訪問。
答案:LinkedHashMap底層源碼都是使用了HashMap的邏輯實現,使用雙鏈表維護元素的順序,并重寫了以下三個方法:
答案:由于LinkedHashMap內部已經實現按照訪問元素的迭代順序,所以只需復用LinkedHashMap的邏輯,繼承LinkedHashMap,重寫removeEldestEntry()方法。
import java.util.LinkedHashMap;import java.util.Map;/** * @author 一燈架構 * @apiNote 使用LinkedHashMap實現LRU緩存 */public class LRUCache<K, V> extends LinkedHashMap<K, V> { /** * 緩存容量大小 */ private final int capacity; /** * 構造方法 * * @param capacity 緩存容量大小 */ public LRUCache(int capacity) { // 底層使用LinkedHashMap的構造方法 super(capacity, 0.75f, true); this.capacity = capacity; } /** * 當緩存容量達到上限時,移除最久未使用的節點 */ @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > capacity; } public static void main(String[] args) { LRUCache<Integer, String> cache = new LRUCache<>(3); cache.put(1, "One"); cache.put(2, "Two"); cache.put(3, "Three"); System.out.println(cache); // 輸出: {1=One, 2=Two, 3=Three} cache.get(2); System.out.println(cache); // 輸出: {1=One, 3=Three, 2=Two} cache.put(4, "Four"); System.out.println(cache); // 輸出: {3=Three, 2=Two, 4=Four} }}
本文鏈接:http://www.www897cc.com/showinfo-26-34645-0.html阿里面試官:LinkedHashMap是怎么保證元素有序的?
聲明:本網頁內容旨在傳播知識,若有侵權等問題請及時與本網聯系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 我們一起聊聊 State of JS 2023、CSS 容器查詢、Rspack、Bruno、H3、medium-zoom