快捷導(dǎo)航

Java的LinkedHashMap的實現(xiàn)原理詳解

更新時間：2023年09月05日 11:25:14 作者：敲代碼的喬幫主

這篇文章主要介紹了Java的LinkedHashMap的實現(xiàn)原理詳解,???LinkedHashMap是Map接口的哈希表和鏈接列表實現(xiàn),具有可預(yù)知的迭代順序,此實現(xiàn)提供所有可選的映射操作,并允許使用null值和null鍵,此類不保證映射的順序,特別是它不保證該順序恒久不變,需要的朋友可以參考下

1. LinkedHashMap概述

LinkedHashMap是Map接口的哈希表和鏈接列表實現(xiàn)，具有可預(yù)知的迭代順序。此實現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。

LinkedHashMap實現(xiàn)與HashMap的不同之處在于，后者維護(hù)著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。

注意，此實現(xiàn)不是同步的。如果多個線程同時訪問鏈接的哈希映射，而其中至少一個線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步。

2. LinkedHashMap的實現(xiàn)

對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。

其基本操作與父類HashMap相似，它通過重寫父類相關(guān)的方法，來實現(xiàn)自己的鏈接列表特性。

下面我們來分析LinkedHashMap的源代碼：

Entry元素

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

/** 
 * 雙向鏈表的表頭元素。 
 */  
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;  
    ……  
}

初始化

通過源代碼可以看出，在LinkedHashMap的構(gòu)造方法中，實際調(diào)用了父類HashMap的相關(guān)構(gòu)造方法來構(gòu)造一個底層存放的table數(shù)組。如：

public LinkedHashMap(int initialCapacity, float loadFactor) {  
    super(initialCapacity, loadFactor);  
    accessOrder = false;  
}

HashMap中的相關(guān)構(gòu)造方法：

public HashMap(int initialCapacity, float loadFactor) {  
    if (initialCapacity < 0)  
        throw new IllegalArgumentException("Illegal initial capacity: " +  
                                           initialCapacity);  
    if (initialCapacity > MAXIMUM_CAPACITY)  
        initialCapacity = MAXIMUM_CAPACITY;  
    if (loadFactor <= 0 || Float.isNaN(loadFactor))  
        throw new IllegalArgumentException("Illegal load factor: " +  
                                           loadFactor);  
    // Find a power of 2 >= initialCapacity  
    int capacity = 1;  
    while (capacity < initialCapacity)  
        capacity <<= 1;  
    this.loadFactor = loadFactor;  
    threshold = (int)(capacity * loadFactor);  
    table = new Entry[capacity];  
    init();  
}

我們已經(jīng)知道LinkedHashMap的Entry元素繼承HashMap的Entry，提供了雙向鏈表的功能。在上述HashMap的構(gòu)造器中，最后會調(diào)用init()方法，進(jìn)行相關(guān)的初始化，這個方法在HashMap的實現(xiàn)中并無意義，只是提供給子類實現(xiàn)相關(guān)的初始化調(diào)用。

LinkedHashMap重寫了init()方法，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后，進(jìn)一步實現(xiàn)了對其元素Entry的初始化操作。

void init() {  
    header = new Entry<K,V>(-1, null, null, null);  
    header.before = header.after = header;  
}

存儲

LinkedHashMap并未重寫父類HashMap的put方法，而是重寫了父類HashMap的put方法調(diào)用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向鏈接列表的實現(xiàn)。

void addEntry(int hash, K key, V value, int bucketIndex) {  
    // 調(diào)用create方法，將新元素以雙向鏈表的的形式加入到映射中。  
    createEntry(hash, key, value, bucketIndex);  
    // 刪除最近最少使用元素的策略定義  
    Entry<K,V> eldest = header.after;  
    if (removeEldestEntry(eldest)) {  
        removeEntryForKey(eldest.key);  
    } else {  
        if (size >= threshold)  
            resize(2 * table.length);  
    }  
}

void createEntry(int hash, K key, V value, int bucketIndex) {  
    HashMap.Entry<K,V> old = table[bucketIndex];  
    Entry<K,V> e = new Entry<K,V>(hash, key, value, old);  
    table[bucketIndex] = e;  
    // 調(diào)用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。  
    e.addBefore(header);  
    size++;  
}

private void addBefore(Entry<K,V> existingEntry) {  
    after  = existingEntry;  
    before = existingEntry.before;  
    before.after = this;  
    after.before = this;  
}

讀取

LinkedHashMap重寫了父類HashMap的get方法，實際在調(diào)用父類getEntry()方法取得查找的元素后，再判斷當(dāng)排序模式accessOrder為true時，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭，并從原來的位置刪除。由于的鏈表的增加、刪除操作是常量級的，故并不會帶來性能的損失。

public V get(Object key) {  
    // 調(diào)用父類HashMap的getEntry()方法，取得要查找的元素。  
    Entry<K,V> e = (Entry<K,V>)getEntry(key);  
    if (e == null)  
        return null;  
    // 記錄訪問順序。  
    e.recordAccess(this);  
    return e.value;  
}

void recordAccess(HashMap<K,V> m) {  
    LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;  
    // 如果定義了LinkedHashMap的迭代順序為訪問順序，  
    // 則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。  
    if (lm.accessOrder) {  
        lm.modCount++;  
        remove();  
        addBefore(lm.header);  
    }  
}

排序模式

LinkedHashMap定義了排序模式accessOrder，該屬性為boolean型變量，對于訪問順序，為true；對于插入順序，則為false。

private final boolean accessOrder;

一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序。看LinkedHashMap的構(gòu)造方法，如：

public LinkedHashMap(int initialCapacity, float loadFactor) {  
    super(initialCapacity, loadFactor);  
    accessOrder = false;  
}

這些構(gòu)造方法都會默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個LinkedHashMap，并打算按從近期訪問最少到近期訪問最多的順序（即訪問順序）來保存元素，那么請使用下面的構(gòu)造方法構(gòu)造LinkedHashMap：

public LinkedHashMap(int initialCapacity,  
         float loadFactor,  
                     boolean accessOrder) {  
    super(initialCapacity, loadFactor);  
    this.accessOrder = accessOrder;  
}

該哈希映射的迭代順序就是最后訪問其條目的順序，這種映射很適合構(gòu)建LRU緩存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法，在將新條目插入到映射后，put和 putAll將調(diào)用此方法。該方法可以提供在每次添加新條目時移除最舊條目的實現(xiàn)程序，默認(rèn)返回false，這樣，此映射的行為將類似于正常映射，即永遠(yuǎn)不能移除最舊的元素。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {  
    return false;  
}

此方法通常不以任何方式修改映射，相反允許映射在其返回值的指引下進(jìn)行自我修改。如果用此映射構(gòu)建LRU緩存，則非常方便，它允許映射通過刪除舊條目來減少內(nèi)存損耗。例如：重寫此方法，維持此映射只保存100個條目的穩(wěn)定狀態(tài)，在每次添加新條目時刪除最舊的條目。

private static final int MAX_ENTRIES = 100;  
protected boolean removeEldestEntry(Map.Entry eldest) {  
    return size() > MAX_ENTRIES;  
}

到此這篇關(guān)于Java的LinkedHashMap的實現(xiàn)原理詳解的文章就介紹到這了,更多相關(guān)Java的LinkedHashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章:

欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java的LinkedHashMap的實現(xiàn)原理詳解

目錄

1. LinkedHashMap概述

2. LinkedHashMap的實現(xiàn)

Entry元素

初始化

存儲

讀取

排序模式

相關(guān)文章

最新評論

大家感興趣的內(nèi)容

最近更新的內(nèi)容

常用在線小工具