日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

當前位置:首頁 > 科技  > 軟件

阿里面試官:LinkedHashMap是怎么保證元素有序的?

來源: 責編: 時間:2023-11-28 09:36:07 242觀看
導讀阿里的上下班時間是1095,這么忙也不能耽誤更新《解讀Java源碼專欄》,在這個系列中,我將手把手帶著大家剖析Java核心組件的源碼,內容包含集合、線程、線程池、并發、隊列等,深入了解其背后的設計思想和實現細節,輕松應對工作

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

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

引言

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

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

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

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

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

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

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

簡介

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

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

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

初始化

LinkedHashMap常見的初始化方法有四個方法:DY428資訊網——每日最新資訊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);

再看一下構造方法的底層實現:DY428資訊網——每日最新資訊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,表示按照訪問順序迭代。DY428資訊網——每日最新資訊28at.com

put源碼

LinkedHashMap的put方法完全使用的是HashMap的put方法,并沒有重新實現。不過HashMap中定義了一些空方法,留給子類LinkedHashMap去實現。 有以下三個方法:DY428資訊網——每日最新資訊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源碼中就調用前兩個方法:DY428資訊網——每日最新資訊28at.com

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

看一下afterNodeInsertion()方法的源碼,看一下再插入節點后要執行哪些操作? 在插入節點后,只執行了一個操作,就是判斷是否刪除最舊的節點。removeEldestEntry()方法默認返回false,表示不需要刪除節點。我們也可以重寫removeEldestEntry()方法,當元素數量超過閾值時,返回true,表示刪除最舊的節點。DY428資訊網——每日最新資訊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()方法中把新節點插入到雙鏈表。DY428資訊網——每日最新資訊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()方法邏輯在前面已經講過。DY428資訊網——每日最新資訊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()方法的邏輯也很簡單,核心邏輯就是把當前節點移動到鏈表末尾,分為三步:DY428資訊網——每日最新資訊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重寫了該方法的邏輯。DY428資訊網——每日最新資訊28at.com

圖片圖片DY428資訊網——每日最新資訊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;    }}

總結

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

  1. LinkedHashMap與HashMap區別?

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

  1. LinkedHashMap特點有哪些?

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

  1. LinkedHashMap底層實現原理?

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

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

答案:由于LinkedHashMap內部已經實現按照訪問元素的迭代順序,所以只需復用LinkedHashMap的邏輯,繼承LinkedHashMap,重寫removeEldestEntry()方法。DY428資訊網——每日最新資訊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}    }}

DY428資訊網——每日最新資訊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表達式:構建強大且靈活的權限控制體系

標簽:
  • 熱門焦點
  • 鴻蒙OS 4.0公測機型公布:甚至連nova6都支持

    華為全新的HarmonyOS 4.0操作系統將于今天下午正式登場,官方在發布會之前也已經正式給出了可升級的機型產品,這意味著這些機型會率先支持升級享用。這次的HarmonyOS 4.0支持
  • 印度登月最關鍵一步!月船三號今晚進入環月軌道

    8月5日消息,據印度官方消息,月船三號將于北京時間今晚21時30分左右開始近月制動進入環月軌道。這是該探測器能夠成功的最關鍵步驟之一,如果成功將開始圍
  • 2023 年的 Node.js 生態系統

    隨著技術的不斷演進和創新,Node.js 在 2023 年達到了一個新的高度。Node.js 擁有一個龐大的生態系統,可以幫助開發人員更快地實現復雜的應用。本文就來看看 Node.js 最新的生
  • 十個簡單但很有用的Python裝飾器

    裝飾器(Decorators)是Python中一種強大而靈活的功能,用于修改或增強函數或類的行為。裝飾器本質上是一個函數,它接受另一個函數或類作為參數,并返回一個新的函數或類。它們通常用
  • 慕巖炮轟抖音,百合網今何在?

    來源:價值研究所 作者:Hernanderz&ldquo;難道就因為自己的一個產品牛逼了,從客服到總裁,都不愿意正視自己產品和運營上的問題,選擇逃避了嗎?&rdquo;這一番話,出自百合網聯合創
  • 2天漲粉255萬,又一賽道在抖音爆火

    來源:運營研究社作者 | 張知白編輯 | 楊佩汶設計 | 晏談夢潔這個暑期,旅游賽道徹底火了:有的「地方」火了&mdash;&mdash;貴州村超旅游收入 1 個月超過 12 億;有的「博主」火了&m
  • 消息稱小米汽車開始篩選交付中心:需至少120個車位

    IT之家 7 月 7 日消息,日前,有微博簡介為“汽車行業從業者、長三角一體化擁護者”的微博用戶 @長三角行健者 發文表示,據經銷商集團反饋,小米汽車目前
  • 超閉合精工鉸鏈 徹底消滅縫隙 三星Galaxy Z Flip5與Galaxy Z Fold5發布

    2023年7月26日,三星電子正式發布了Galaxy Z Flip5與Galaxy Z Fold5。三星新一代折疊屏手機采用超閉合精工鉸鏈,讓折疊后的縫隙不再可見。同時,配合處
  • Windows 11發布,微軟一改往常對老機型開放的態度

    距離 Windows 11 發布已經過去一周,在過去一周里,很多數碼愛好者圍繞其對 Android 應用的支持、對老機型的升級問題展開了激烈討論。與以往不同的是,在這次大
Top 主站蜘蛛池模板: 彭州市| 日照市| 卓资县| 屏东市| 铜梁县| 湘阴县| 绵竹市| 荔浦县| 民权县| 如东县| 内丘县| 荆门市| 仙游县| 阿克苏市| 清远市| 云霄县| 内丘县| 壶关县| 新化县| 商都县| 扬中市| 城口县| 定安县| 宝鸡市| 白水县| 巴林左旗| 高碑店市| 洪湖市| 惠安县| 泰来县| 望江县| 合肥市| 安达市| 阳城县| 晋宁县| 怀化市| 大石桥市| 施甸县| 磐安县| 陇西县| 宜良县|