阿里的上下班時間是1095，這么忙也不能耽誤更新《解讀Java源碼專欄》，在這個系列中，我將手把手帶著大家剖析Java核心組件的源碼，內容包含集合、線程、線程池、并發、隊列等，深入了解其背后的設計思想和實現細節，輕松應對工作面試。IrE28資訊網——每日最新資訊28at.com

這是解讀Java源碼系列的第五篇，將跟大家一起學習Java中比較神秘的數據結構 - LinkedHashMap。IrE28資訊網——每日最新資訊28at.com

引言

新手程序員在使用HashMap的時候，會有個疑問，為什么存到HashMap中的數據不是有序的？IrE28資訊網——每日最新資訊28at.com

這其實跟HashMap的底層設計有關，HashMap并不是像ArrayList那樣，按照元素的插入順序存儲。而是先計算key的哈希值，再用哈希值對數組長度求余，算出數組下標，存儲到下標所在的位置，如果該位置上存在鏈表或者紅黑樹，再把這個元素插入到鏈表或者紅黑樹上面。IrE28資訊網——每日最新資訊28at.com

這樣設計，可以實現快速查詢，也就犧牲了存儲順序。因為不同key的哈希值差別很大，所以在數組中存儲是無序的。IrE28資訊網——每日最新資訊28at.com

然而，有時候我們在遍歷HashMap的時候，又希望按照元素插入順序迭代，有沒有什么方式能實現這個需求？IrE28資訊網——每日最新資訊28at.com

有的，就是今天的主角LinkedHashMap，不但保證了HashMap的性能，還實現了按照元素插入順序或者訪問順序進行迭代。IrE28資訊網——每日最新資訊28at.com

在這篇文章中，你將學到以下內容：IrE28資訊網——每日最新資訊28at.com

1. LinkedHashMap與HashMap區別？
2. LinkedHashMap特點有哪些？
3. LinkedHashMap底層實現原理？
4. 怎么使用``LinkedHashMap實現 LRU 緩存？

簡介

LinkedHashMap繼承自HashMap，是HashMap的子類，內部額外維護了一個雙鏈表，來保證元素的插入順序或訪問順序，用空間換時間。 與HashMap相比，LinkedHashMap有三個優點：IrE28資訊網——每日最新資訊28at.com

1. 維護了元素插入順序，支持以元素插入順序進行迭代。
2. 維護了元素的訪問順序，支持以元素訪問順序進行迭代。最近訪問或者更新的元素，會被移動到鏈表末尾，類似于LRU（Least Recently Used，最近最少使用）。當面試的時候，手寫LRU緩存，需要用到或者參考LinkedHashMap。
3. 迭代效率更高，迭代LinkedHashMap的時候，不需要遍歷整個數組，只需遍歷雙鏈表即可，效率更高。

圖片IrE28資訊網——每日最新資訊28at.com

類屬性

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。IrE28資訊網——每日最新資訊28at.com

初始化

LinkedHashMap常見的初始化方法有四個方法：IrE28資訊網——每日最新資訊28at.com

1. 無參初始化
2. 指定容量大小的初始化
3. 指定容量大小、負載系數的初始化
4. 指定容量大小、負載系數、迭代順序的初始化

/** * 無參初始化 */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);

再看一下構造方法的底層實現：IrE28資訊網——每日最新資訊28at.com

/** * 無參初始化 */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，表示按照訪問順序迭代。IrE28資訊網——每日最新資訊28at.com

put源碼

LinkedHashMap的put方法完全使用的是HashMap的put方法，并沒有重新實現。不過HashMap中定義了一些空方法，留給子類LinkedHashMap去實現。 有以下三個方法：IrE28資訊網——每日最新資訊28at.com

public class HashMap<K, V> {        /**     * 在訪問節點后執行的操作     */    void afterNodeAccess(Node<K, V> p) {    }    /**     * 在插入節點后執行的操作     */    void afterNodeInsertion(boolean evict) {    }    /**     * 在刪除節點后執行的操作     */    void afterNodeRemoval(Node<K, V> p) {    }    }

在HashMap的put源碼中就調用前兩個方法：IrE28資訊網——每日最新資訊28at.com

圖片IrE28資訊網——每日最新資訊28at.com

看一下afterNodeInsertion()方法的源碼，看一下再插入節點后要執行哪些操作？ 在插入節點后，只執行了一個操作，就是判斷是否刪除最舊的節點。removeEldestEntry()方法默認返回false，表示不需要刪除節點。我們也可以重寫removeEldestEntry()方法，當元素數量超過閾值時，返回true，表示刪除最舊的節點。IrE28資訊網——每日最新資訊28at.com

/** * 在插入節點后執行的操作（刪除最舊的節點） */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()方法中把新節點插入到雙鏈表。IrE28資訊網——每日最新資訊28at.com

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源碼

再看一下 get 方法源碼，LinkedHashMap的 get 方法是直接調用的HashMap的get方法邏輯，在獲取到value 后，判斷 value 不為空，就執行afterNodeAccess()方法邏輯，把該節點移動到鏈表末尾，afterNodeAccess()方法邏輯在前面已經講過。IrE28資訊網——每日最新資訊28at.com

/** * 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()方法的邏輯也很簡單，核心邏輯就是把當前節點移動到鏈表末尾，分為三步：IrE28資訊網——每日最新資訊28at.com

1. 斷開當前節點與后繼節點的連接
2. 斷開當前節點與前驅節點的連接
3. 把當前節點插入到鏈表末尾

/** * 在訪問節點后執行的操作（把節點移動到鏈表末尾） */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;    }}

remove源碼

LinkedHashMap的 remove 方法完全使用的是 HashMap 的 remove 方法，并沒有重新實現。不過 HashMap的 remove 中調用了afterNodeRemoval?()，執行刪除節點后邏輯，LinkedHashMap重寫了該方法的邏輯。IrE28資訊網——每日最新資訊28at.com

圖片IrE28資訊網——每日最新資訊28at.com

/** * 在刪除節點后執行的操作（從雙鏈表中刪除該節點） */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;    }}

總結

現在可以回答文章開頭提出的問題：IrE28資訊網——每日最新資訊28at.com

1. LinkedHashMap與HashMap區別？

答案：LinkedHashMap繼承自HashMap，是HashMap的子類。IrE28資訊網——每日最新資訊28at.com

2. LinkedHashMap特點有哪些？

答案：除了保證了與HashMap一樣高效的查詢和插入性能外，還支持以插入順序或者訪問順序進行迭代訪問。IrE28資訊網——每日最新資訊28at.com

3. LinkedHashMap底層實現原理？

答案：LinkedHashMap底層源碼都是使用了HashMap的邏輯實現，使用雙鏈表維護元素的順序，并重寫了以下三個方法：IrE28資訊網——每日最新資訊28at.com

1. afterNodeAccess()，在訪問節點后執行的操作
2. afterNodeInsertion()，在插入節點后執行的操作。
3. afterNodeRemoval()，在刪除節點后執行的操作。
4. 怎么使用``LinkedHashMap實現 LRU 緩存？

答案：由于LinkedHashMap內部已經實現按照訪問元素的迭代順序，所以只需復用LinkedHashMap的邏輯，繼承LinkedHashMap，重寫removeEldestEntry()方法。IrE28資訊網——每日最新資訊28at.com

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}    }}

IrE28資訊網——每日最新資訊28at.com

本文鏈接：http://www.www897cc.com/showinfo-26-34645-0.html阿里面試官：LinkedHashMap是怎么保證元素有序的？

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com

上一篇： 我們一起聊聊 State of JS 2023、CSS 容器查詢、Rspack、Bruno、H3、medium-zoom

下一篇： 通過Spring AOP結合SpEL表達式：構建強大且靈活的權限控制體系