【JAVA集合】LinkedHashMap及其源碼分析

来源:http://www.cnblogs.com/chenpi/archive/2016/03/19/5294077.html
-Advertisement-
Play Games

以下內容基於jdk1.7.0_79源碼； 繼承自HashMap，一個有序的Map介面實現，這裡的有序指的是元素可以按插入順序或訪問順序排列； 與HashMap的異同：同樣是基於散列表實現，區別是，LinkedHashMap內部多了一個雙向迴圈鏈表的維護，該鏈表是有序的，可以按元素插入順序或元素最近訪


以下內容基於jdk1.7.0_79源碼；

什麼是LinkedHashMap

繼承自HashMap，一個有序的Map介面實現，這裡的有序指的是元素可以按插入順序或訪問順序排列；

LinkedHashMap補充說明

與HashMap的異同：同樣是基於散列表實現，區別是，LinkedHashMap內部多了一個雙向迴圈鏈表的維護，該鏈表是有序的，可以按元素插入順序或元素最近訪問順序(LRU)排列，

簡單地說：LinkedHashMap=散列表+迴圈雙向鏈表

LinkedHashMap的數組結構

用畫圖工具簡單畫了下散列表和迴圈雙向鏈表，如下圖，簡單說明下：

第一張圖是LinkedHashMap的全部數據結構，包含散列表和迴圈雙向鏈表，由於迴圈雙向鏈表線條太多了，不好畫，簡單的畫了一個節點(黃色圈出來的)示意一下，註意左邊的紅色箭頭引用為Entry節點對象的next引用(散列表中的單鏈表)，綠色線條為Entry節點對象的before, after引用(迴圈雙向鏈表的前後引用)；

第二張圖專門把迴圈雙向鏈表抽取出來，直觀一點，註意該迴圈雙向鏈表的頭部存放的是最久訪問的節點或最先插入的節點，尾部為最近訪問的或最近插入的節點，迭代器遍歷方向是從鏈表的頭部開始到鏈表尾部結束，在鏈表尾部有一個空的header節點，該節點不存放key-value內容，為LinkedHashMap類的成員屬性，迴圈雙向鏈表的入口；

LinkedHashMap繼承的類與實現的介面

LinkedHashMap源碼中雙向鏈表的操作

同樣畫了一張圖，主要是插入刪除、操作，如下圖，應該挺好理解的，鏈表的操作

LinkedHashMap源碼解析，基本全部加了註釋，建議看之前，先看HashMap的源碼

package java.util;
import java.io.*;


public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 雙向迴圈鏈表，  頭結點(空節點)
     */
    private transient Entry<K,V> header;

    /**
     * accessOrder為true時，按訪問順序排序，false時，按插入順序排序
     */
    private final boolean accessOrder;

    /**
     * 生成一個空的LinkedHashMap,並指定其容量大小和負載因數，
     * 預設將accessOrder設為false，按插入順序排序
     */
    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    /**
     * 生成一個空的LinkedHashMap,並指定其容量大小，負載因數使用預設的0.75，
     * 預設將accessOrder設為false，按插入順序排序
     */
    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    /**
     * 生成一個空的HashMap,容量大小使用預設值16，負載因數使用預設值0.75
     * 預設將accessOrder設為false，按插入順序排序.
     */
    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    /**
     * 根據指定的map生成一個新的HashMap,負載因數使用預設值，初始容量大小為Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,DEFAULT_INITIAL_CAPACITY)
     * 預設將accessOrder設為false，按插入順序排序.
     */
    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super(m);
        accessOrder = false;
    }

    /**
     * 生成一個空的LinkedHashMap,並指定其容量大小和負載因數，
     * 預設將accessOrder設為true，按訪問順序排序
     */
    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

    /**
     * 覆蓋HashMap的init方法，在構造方法、Clone、readObject方法里會調用該方法
     * 作用是生成一個雙向鏈表頭節點，初始化其前後節點引用
     */
    @Override
    void init() {
        header = new Entry<>(-1, null, null, null);
        header.before = header.after = header;
    }

    /**
     * 覆蓋HashMap的transfer方法，性能優化，這裡遍歷方式不採用HashMap的雙重迴圈方式
     * 而是直接通過雙向鏈表遍歷Map中的所有key-value映射
     */
    @Override
    void transfer(HashMap.Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍歷舊Map中的所有key-value
        for (Entry<K,V> e = header.after; e != header; e = e.after) {
            if (rehash)
                e.hash = (e.key == null) ? 0 : hash(e.key);
            //根據新的數組長度，重新計算索引，
            int index = indexFor(e.hash, newCapacity);
            //插入到鏈表表頭
            e.next = newTable[index];
            //將e放到索引為i的數組處
            newTable[index] = e;
        }
    }


    /**
     * 覆蓋HashMap的transfer方法，性能優化，這裡遍歷方式不採用HashMap的雙重迴圈方式
     * 而是直接通過雙向鏈表遍歷Map中的所有key-value映射,
     */
    public boolean containsValue(Object value) {
        // Overridden to take advantage of faster iterator
        if (value==null) {
            for (Entry e = header.after; e != header; e = e.after)
                if (e.value==null)
                    return true;
        } else {
            for (Entry e = header.after; e != header; e = e.after)
                if (value.equals(e.value))
                    return true;
        }
        return false;
    }

    /**
     * 通過key獲取value，與HashMap的區別是：當LinkedHashMap按訪問順序排序的時候，會將訪問的當前節點移到鏈表尾部(頭結點的前一個節點)
     */
    public V get(Object key) {
        Entry<K,V> e = (Entry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

    /**
     * 調用HashMap的clear方法，並將LinkedHashMap的頭結點前後引用指向自己
     */
    public void clear() {
        super.clear();
        header.before = header.after = header;
    }

    /**
     * LinkedHashMap節點對象
     */
    private static class Entry<K,V> extends HashMap.Entry<K,V> {
        // 節點前後引用
        Entry<K,V> before, after;

        //構造函數與HashMap一致
        Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
            super(hash, key, value, next);
        }

        /**
         * 移除節點，並修改前後引用
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * 將當前節點插入到existingEntry的前面
         */
        private void addBefore(Entry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

        /**
         * 在HashMap的put和get方法中，會調用該方法，在HashMap中該方法為空
         * 在LinkedHashMap中，當按訪問順序排序時，該方法會將當前節點插入到鏈表尾部(頭結點的前一個節點)，否則不做任何事
         */
        void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            //當LinkedHashMap按訪問排序時
            if (lm.accessOrder) {
                lm.modCount++;
                //移除當前節點
                remove();
                //將當前節點插入到頭結點前面
                addBefore(lm.header);
            }
        }

        void recordRemoval(HashMap<K,V> m) {
            remove();
        }
    }
    
    //迭代器
    private abstract class LinkedHashIterator<T> implements Iterator<T> {
        //初始化下個節點引用
        Entry<K,V> nextEntry    = header.after;
        Entry<K,V> lastReturned = null;

        /**
         * 用於迭代期間快速失敗行為
         */
        int expectedModCount = modCount;
        
        //鏈表遍歷結束標誌，當下個節點為頭節點的時候
        public boolean hasNext() {
            return nextEntry != header;
        }

        //移除當前訪問的節點
        public void remove() {
            //lastReturned會在nextEntry方法中賦值
            if (lastReturned == null)
                throw new IllegalStateException();
            //快速失敗機制
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();

            LinkedHashMap.this.remove(lastReturned.key);
            lastReturned = null;
            //迭代器自身刪除節點，並不是其他線程修改Map結構，所以這裡要修改expectedModCount
            expectedModCount = modCount;
        }

        //返回鏈表下個節點的引用
        Entry<K,V> nextEntry() {
            //快速失敗機制
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            //鏈表為空情況
            if (nextEntry == header)
                throw new NoSuchElementException();
            
            //給lastReturned賦值，最近一個從迭代器返回的節點對象
            Entry<K,V> e = lastReturned = nextEntry;
            nextEntry = e.after;
            return e;
        }
    }
    //key迭代器
    private class KeyIterator extends LinkedHashIterator<K> {
        public K next() { return nextEntry().getKey(); }
    }
    //value迭代器
    private class ValueIterator extends LinkedHashIterator<V> {
        public V next() { return nextEntry().value; }
    }
    //key-value迭代器
    private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
        public Map.Entry<K,V> next() { return nextEntry(); }
    }

    // 返回不同的迭代器對象
    Iterator<K> newKeyIterator()   { return new KeyIterator();   }
    Iterator<V> newValueIterator() { return new ValueIterator(); }
    Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }

    /**
     * 創建節點，插入到LinkedHashMap中，該方法覆蓋HashMap的addEntry方法
     */
    void addEntry(int hash, K key, V value, int bucketIndex) {
        super.addEntry(hash, key, value, bucketIndex);

        // 註意頭結點的下個節點即header.after，存放於鏈表頭部，是最不經常訪問或第一個插入的節點，
        //有必要的情況下(如容量不夠,具體看removeEldestEntry方法的實現，這裡預設為false，不刪除)，可以先刪除
        Entry<K,V> eldest = header.after;
        if (removeEldestEntry(eldest)) {
            removeEntryForKey(eldest.key);
        }
    }

    /**
     * 創建節點，並將該節點插入到鏈表尾部
     */
    void createEntry(int hash, K key, V value, int bucketIndex) {
        HashMap.Entry<K,V> old = table[bucketIndex];
        Entry<K,V> e = new Entry<>(hash, key, value, old);
        table[bucketIndex] = e;
        //將該節點插入到鏈表尾部
        e.addBefore(header);
        size++;
    }

    /**
     * 該方法在創建新節點的時候調用，
     * 判斷是否有必要刪除鏈表頭部的第一個節點(最不經常訪問或最先插入的節點，由accessOrder決定)
     */
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }
}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • C#基本語法學習（九）
    C#中的介面 在C#中介面是一組公共方法或屬性的集合。介面可以被其他介面或是類繼承，但不能被實例化。 1、介面中包含的屬性和方法都是公共的，不是繼承或是私有的。事實上，在C#中定義介面中的成員時，不允許顯示指定介面成員的可訪問性，而是自動預設為公共的。 2、介面中只能包含普通方法或屬性，而不能包含其
  • C#基本語法學習（八）
    C#中的結構 在C#中用關鍵字struct定義一個結構。從語法上來看，結構與類很相似，在類中可以包含的成員幾乎都可以包含在結構中。例如，結構中可以定義欄位、方法、構造函數、屬性、事件等。定義結構語法如下： 訪問修飾符 struct 結構名 { //結構成員 } 在結構中不能定義預設構造函數（即不帶參
  • Dos.ORM使用教程
    Dos.ORM（原Hxj.Data）於2009年發佈，併發布實體生成工具。在開發過程參考了多個ORM框架，特別是NBear，MySoft、EF、Dapper等。吸取了他們的一些精華，加入自己的新思想。該組件已在上百個成熟企業項目中應用 首先·在 App.config文件中配置連接資料庫字元串。或者在
  • EntityFramework.Extended 實現 update count+=1
    在使用 EF 的時候，EntityFramework.Extended 的作用：使 轉換為 ，這樣使我們在修改實體對象的時候，避免先查詢再修改，而是直接 Update，大致寫法： 但有時候，我們還有一種操作，就是在實體屬性值的基礎上，進行加減操作，不要被上面的 嚇到（誤以為只能賦新值），其實用 En
  • C# 解析XML
    解析文件內容： 解析代碼：
  • 從前端性能優化的角度提高自己的博客的訪問速度
    這段時間狀態比較清閑，我想是時候以一個前端開發人員的態度來整理下自己的博客設置了，除了UI上的一些調整，考慮最多的就是怎麼優化我的這些個性化內容，讓博客的訪問速度的更快
  • ASP.NET跨頁面傳值技巧[總結]
    關於頁面傳值的方法，我就我個人觀點做了些總結，希望對大家有所幫助。 1. 使用QueryString變數 QueryString是一種非常簡單的傳值方式，他可以將傳送的值顯示在瀏覽器的地址欄中。如果是傳遞一個或多個安全性要求不高或是結構簡單的數值時，可以使用這個方法。但是對於傳遞數組或對象的話...
  • .net視圖中日期格式化
    昨天在做一個功能，要在界面上按照規定的格式顯示一個時間，如果直接在expression那裡格式化的話（如下:） 以上情形，執行期間會報拒絕訪問的問題，當然這並非難事，解決方案有好幾種（本人前端時間控制項用的是My97Datepicker): （ps.這裡忽略那種非綁定Model的情形，因為不綁定Mod
一周排行
    -Advertisement-
    Play Games
  • C# + WPF 音頻播放器 界面優雅，體驗良好
    前言 本文介紹一款使用 C# 與 WPF 開發的音頻播放器，其界面簡潔大方，操作體驗流暢。該播放器支持多種音頻格式（如 MP4、WMA、OGG、FLAC 等），並具備標記、實時歌詞顯示等功能。 另外，還支持換膚及多語言（中英文）切換。核心音頻處理採用 FFmpeg 組件，獲得了廣泛認可，目前 Git ...
  • OAuth2.0授權-gitee授權碼模式
    OAuth2.0授權驗證-gitee授權碼模式 本文主要介紹如何筆者自己是如何使用gitee提供的OAuth2.0協議完成授權驗證並登錄到自己的系統，完整模式如圖 1、創建應用 打開gitee個人中心->第三方應用->創建應用 創建應用後在我的應用界面，查看已創建應用的Client ID和Clien ...
  • FastReport.OpenSource .Net下開源免費報表列印組件
    解決了這個問題：《winForm下，fastReport.net 從.net framework 升級到.net5遇到的錯誤“Operation is not supported on this platform.”》 本文內容轉載自：https://www.fcnsoft.com/Home/Sho ...
  • 如何在 ASP.NET Core Web API 方法執行前後 “偷偷“ 作一些 “壞“ 事？初識 ActionFilterAttribute
    國內文章 WPF 從裸 Win 32 的 WM_Pointer 消息獲取觸摸點繪製筆跡 https://www.cnblogs.com/lindexi/p/18390983 本文將告訴大家如何在 WPF 裡面，接收裸 Win 32 的 WM_Pointer 消息，從消息裡面獲取觸摸點信息，使用觸摸點 ...
  • 在 ASP.NET Core Web API 中使用異常篩選器捕獲和統一處理異常
    前言 給大家推薦一個專為新零售快消行業打造了一套高效的進銷存管理系統。 系統不僅具備強大的庫存管理功能，還集成了高性能的輕量級 POS 解決方案，確保頁面載入速度極快，提供良好的用戶體驗。 項目介紹 Dorisoy.POS 是一款基於 .NET 7 和 Angular 4 開發的新零售快消進銷存管理 ...
  • AbpHelper CLI積累與實戰分享
    ABP CLI常用的代碼分享 一、確保環境配置正確 安裝.NET CLI： ABP CLI是基於.NET Core或.NET 5/6/7等更高版本構建的，因此首先需要在你的開發環境中安裝.NET CLI。這可以通過訪問Microsoft官網下載並安裝相應版本的.NET SDK來實現。 安裝ABP ...
  • 記一次HttpClient使用問題分析
    問題 問題是這樣的：第三方的webapi，需要先調用登陸介面獲取Cookie，訪問其它介面時攜帶Cookie信息。 但使用HttpClient類調用登陸介面，返回的Headers中沒有找到Cookie信息。 分析 首先，使用Postman測試該登陸介面，正常返回Cookie信息，說明是HttpCli ...
  • .NET周刊【9月第3期 2024-09-15】
    國內文章 關於.NET在中國為什麼工資低的分析 https://www.cnblogs.com/thinkingmore/p/18406244 .NET在中國開發者的薪資偏低，主要因市場需求、技術棧選擇和企業文化等因素所致。歷史上，.NET曾因微軟的閉源策略發展受限，儘管後來推出了跨平臺的.NET ...
  • 我的網站集成ElasticSearch初體驗
    在WPF開發應用中，動畫不僅可以引起用戶的註意與興趣，而且還使軟體更加便於使用。前面幾篇文章講解了畫筆（Brush），形狀（Shape），幾何圖形（Geometry），變換（Transform）等相關內容，今天繼續講解動畫相關內容和知識點，僅供學習分享使用，如有不足之處，還請指正。 ...
  • 第23篇 委托的概述
    什麼是委托？ 委托可以說是把一個方法代入另一個方法執行，相當於指向函數的指針；事件就相當於保存委托的數組； 1.實例化委托的方式： 方式1：通過new創建實例： public delegate void ShowDelegate(); 或者 public delegate string ShowDe ...
所有分類