為了賬號安全,請及時綁定郵箱和手機立即綁定

LinkedHashMap原理和底層實現

2018.02.01 23:55 10773瀏覽
1.概述

在使用HashMap的時候,可能會遇到需要按照當時put的順序來進行哈希表的遍歷。通過上篇對HashMap的了解,我們知道HashMap中不存在保存順序的機制。本篇文章要介紹的LinkedHashMap專為此特性而生。在LinkedHashMap中可以保持兩種順序,分別是插入順序和訪問順序,這個是可以在LinkedHashMap的初始化方法中進行指定的。相對于訪問順序,按照插入順序進行編排被使用到的場景更多一些,所以默認是按照插入順序進行編排。

看一下實際的運行效果,測試代碼如下:

public static void main(String[] args)
    {
        Map<String, String> test = new LinkedHashMap<String, String>(9);

        test.put("化學","93");
        test.put("數學","98");
        test.put("生物","92");
        test.put("英語","97");
        test.put("物理","94");
        test.put("歷史","96");
        test.put("語文","99");
        test.put("地理","95");

        for (Map.Entry entry : test.entrySet())
        {
            System.out.println(entry.getKey().toString() + ":" + entry.getValue().toString());
        }
    }

運行結果如下圖所示,可以看到,輸出的順序與插入的順序是一致的。
圖片描述

2.原理
  1. 在LinkedHashMap中,是通過雙聯表的結構來維護節點的順序的。上文中的程序,實際上在內存中的情況如下圖所示,每個節點都進行了雙向的連接,維持插入的順序(默認)。head指向第一個插入的節點,tail指向最后一個節點。
    圖片描述
  2. LinkedHashMap是HashMap的親兒子,直接繼承HashMap類。LinkedHashMap中的節點元素為Entry<K,V>,直接繼承HashMap.Node<K,V>。UML類圖關系如下:
    圖片描述
3.源碼分析
3.1 節點構造方法

剛剛看LinkedHashMap的實現的時候有個疑問。LinkedHashMap繼承HashMap,HashMap中的數組是Node<K,V>[]類型的,在LinkedHashMap中定義了Entry<K,V>繼承Node<K,V>[],但是在LinkedHashMap中并沒有找到新建節點的方法。仔細研究之后發現,在HashMap類的put方法中,新建節點是使用的newNode方法。而在LinkedHashMap沒有重寫父類的put方法,而是重寫了newNode方法來構建自己的節點對象。

HashMap中的newNode方法:

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

LinkedHashMap中的newNode方法:

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;
    }
3.2 put方法

在LinkedHashMap類使用的仍然是父類HashMap的put方法,所以插入節點對象的流程基本一致。不同的是,LinkedHashMap重寫了afterNodeInsertionafterNodeAccess方法。

afterNodeInsertion方法用于移除鏈表中的最舊的節點對象,也就是鏈表頭部的對象。但是在JDK1.8版本中,可以看到removeEldestEntry一直返回false,所以該方法并不生效。如果存在特定的需求,比如鏈表中長度固定,并保持最新的N的節點數據,可以通過重寫該方法來進行實現。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

afterNodeAccess方法實現的邏輯,是把入參的節點放置在鏈表的尾部。

void afterNodeAccess(Node<K,V> e) { // move node to last
    LinkedHashMap.Entry<K,V> last;
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a != null)
            a.before = b;
        else
            last = b;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}
3.3 get方法

LinkedHashMap中的get方法與父類HashMap處理邏輯相似,不同之處在于增加了一處鏈表更新的邏輯。如果LinkedHashMap中存在要尋找的節點,那么判斷如果設置了accessOrder,則在返回值之前,將該節點移動到對應桶中鏈表的尾部。

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}
3.4 remove方法

LinkedHashMap重寫了afterNodeRemoval方法,用于在刪除節點的時候,調整雙鏈表的結構。

void afterNodeRemoval(Node<K,V> e) { // unlink
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    p.before = p.after = null;
    if (b == null)
        head = a;
    else
        b.after = a;
    if (a == null)
        tail = b;
    else
        a.before = b;
}
4.小結

LinkedHashMap相對于HashMap,增加了雙鏈表的結果(即節點中增加了前后指針),其他處理邏輯與HashMap一致,同樣也沒有鎖保護,多線程使用存在風險。

點擊查看更多內容

本文原創發布于慕課網 ,轉載請注明出處,謝謝合作

24人點贊

若覺得本文不錯,就分享一下吧!

評論

相關文章推薦

正在加載中
意見反饋 幫助中心 APP下載
官方微信

舉報

0/150
提交
取消
lpl竞猜