LinkedHashMap如何保證有序問題

更新時間：2022年11月21日 08:34:11 作者：小小少年_

這篇文章主要介紹了LinkedHashMap如何保證有序問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

LinkedHashMap如何保證有序

我們常說linkedHashMap是有序的，這個有序也是分為兩種的，分別是：插入順序和訪問順序，我們可以通俗的認為：linkedHashMap = hashmap + 雙向鏈表

以下的學(xué)習(xí)是基于jdk8

在這里插入圖片描述

根據(jù)linkedHashMap的結(jié)構(gòu)來看，是依賴于hashmap的，通過查看源碼，我們也會發(fā)現(xiàn)，linkedHashMap只是維護了一個鏈表，并沒有put、remove方法的具體實現(xiàn)，

因為linkedHashMap的設(shè)計思想是：對數(shù)據(jù)的操作，是依賴于hashmap中的方法，只是在其中的一些細節(jié)方法，linkedHashMap會進行擴展，接下來我們先說屬性有哪些

屬性信息

/**
     * The head (eldest) of the doubly linked list.
     * 鏈表的head節(jié)點
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     * 鏈表的尾結(jié)點
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     * false:表示插入順序；true表示讀取順序
     * @serial
     */
    final boolean accessOrder;

AccessOrder

該屬性是來區(qū)分當前l(fā)inkedHashMap是按照訪問順序排序，還是按照put順序有序，當該參數(shù)為true的時候，表示按照讀取順序有序；默認為false，按照put順序有序

newNode()

在調(diào)用put方法的時候，會調(diào)用父類hashmap的put方法，那linkedHashMap如何維護節(jié)點之間的順序呢？

在put方法中，如果得到當前key要存儲的位置，會調(diào)用newNode()方法，初始化一個node節(jié)點，

在這里插入圖片描述

linkedHashMap對該方法，進行了覆寫，

/**
     * 在向map中put元素的時候，是會初始化一個node節(jié)點，如果是linkedHashMap，調(diào)用的是該方法
     * 在該方法中，可以看到，會初始化一個LinkedHashMap.Entry節(jié)點，然后將該節(jié)點插入到linkedHashMap的雙向鏈表中
     * 默認是加到鏈表尾部
     * @param hash
     * @param key
     * @param value
     * @param e
     * @return
     */
    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;
    }

這里可以看到，除了初始化一個節(jié)點之外，還會調(diào)用linkNodeLast方法，在linkedNodeLast方法中，會將p節(jié)點添加到自己維護的雙向鏈表的尾部

/**
     * 這是加入到鏈表尾部的方法
     * 如果當前是第一個put的元素，那p就是head，否則，就把節(jié)點放到tail的后面
     * @param 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;
        }
    }

按訪問順序有序

假如在初始化linkedHashMap對象的時候，指定accessOrder為true，那表示按照訪問順序有序，在get方法中，會對訪問到的元素進行處理

public V get(Object key) {
        Node<K,V> e;
        // 這里的getNode調(diào)用的是hashmap中的方法，獲取到當前key所對應(yīng)的value
        if ((e = getNode(hash(key), key)) == null)
            return null;
        /**
         * 如果是按照訪問順序有序，會把獲取到的e節(jié)點插入到鏈表的尾部，然后返回e.value
         */
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

這里可以看到，如果是按照訪問順序有序的話，會額外調(diào)用afterNodeAccess()方法，如果為false，會直接返回獲取到的節(jié)點value值，afterNodeAccess方法簡單而言，就是將e節(jié)點移到鏈表的尾部，所以，我們可以認為，最近訪問的在元素在鏈表的最后面

所以：對于按照put順序有序的設(shè)置，在put元素的時候，本身就會把最新插入的元素放入到鏈表的尾部，如果是按照訪問順序有序的話，在get的時候，會把訪問的元素移到鏈表的尾部，根據(jù)該特點，也可以實現(xiàn)一個簡單的LRU算法

對于hashmap和linkedHashMap來說，最大的區(qū)別就是：hashmap是無序的，linkedHashMap自己維護了節(jié)點的順序

LinkedHashMap實現(xiàn)有序的原理

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數(shù)組中保存的元素Entry，該Entry除了保存當前對象的引用外，還保存了其上一個元素before和下一個元素after的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表。

這樣就能按照插入的順序遍歷原本無序的HashMap了，是不是很方便？

看源代碼：

/** 
 * 雙向鏈表的表頭元素。 
 */  
private transient Entry<K,V> header;  
  
/** 
 * LinkedHashMap的Entry元素。 
 * 繼承HashMap的Entry元素，又保存了其上一個元素before和下一個元素after的引用。 
 */  
private static class Entry<K,V> extends HashMap.Entry<K,V> {  
    Entry<K,V> before, after;  
    ……  
}

以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: