Java的LinkedHashMap的實(shí)現(xiàn)原理詳解
1. LinkedHashMap概述
LinkedHashMap是Map接口的哈希表和鏈接列表實(shí)現(xiàn)，具有可預(yù)知的迭代順序。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
LinkedHashMap實(shí)現(xiàn)與HashMap的不同之處在于，后者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問鏈接的哈希映射，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射，則它必須保持外部同步。
2. LinkedHashMap的實(shí)現(xiàn)
對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。
其基本操作與父類HashMap相似，它通過重寫父類相關(guān)的方法，來實(shí)現(xiàn)自己的鏈接列表特性。
下面我們來分析LinkedHashMap的源代碼：
Entry元素
LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數(shù)組中保存的元素Entry，該Entry除了保存當(dāng)前對象的引用外，還保存了其上一個(gè)元素before和下一個(gè)元素after的引用，從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表?？丛创a：
/**
* 雙向鏈表的表頭元素。
*/
private transient Entry<K,V> header;
/**
* LinkedHashMap的Entry元素。
* 繼承HashMap的Entry元素，又保存了其上一個(gè)元素before和下一個(gè)元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
} 初始化
通過源代碼可以看出，在LinkedHashMap的構(gòu)造方法中，實(shí)際調(diào)用了父類HashMap的相關(guān)構(gòu)造方法來構(gòu)造一個(gè)底層存放的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)造器 中，最后會(huì)調(diào)用init()方法，進(jìn)行相關(guān)的初始化，這個(gè)方法在HashMap的實(shí)現(xiàn)中并無意義，只是提供給子類實(shí)現(xiàn)相關(guān)的初始化調(diào)用。
LinkedHashMap重寫了init()方法，在調(diào)用父類的構(gòu)造方法完成構(gòu)造后，進(jìn)一步實(shí)現(xiàn)了對其元素Entry的初始化操作。
void init() {
header = new Entry<K,V>(-1, null, null, null);
header.before = header.after = header;
} 存儲(chǔ)
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)，提供了自己特有的雙向鏈接列表的實(shí)現(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方法，實(shí)際在調(diào)用父類getEntry()方法取得查找的元素后，再判斷當(dāng)排序模式accessOrder為true時(shí)，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭，并從原來的位置刪除。由于的鏈表的增加、刪除操作是常量級的，故并不會(huì)帶來性能的損失。
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的迭代順序?yàn)樵L問順序，
// 則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
} 排序模式
LinkedHashMap定義了排序模式accessOrder，該屬性為boolean型變量，對于訪問順序，為true；對于插入順序，則為false。
private final boolean accessOrder;
一般情況下，不必指定排序模式，其迭代順序即為默認(rèn)為插入順序?？碙inkedHashMap的構(gòu)造方法，如：
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
} 這些構(gòu)造方法都會(huì)默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個(gè)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)用此方法。該方法可以提供在每次添加新條目時(shí)移除最舊條目的實(shí)現(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個(gè)條目的穩(wěn)定狀態(tài)，在每次添加新條目時(shí)刪除最舊的條目。
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
} 到此這篇關(guān)于Java的LinkedHashMap的實(shí)現(xiàn)原理詳解的文章就介紹到這了,更多相關(guān)Java的LinkedHashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
SpringBoot實(shí)現(xiàn)AOP切面的三種方式
Spring,SpringBoot框架憑借多種高效機(jī)制,顯著增強(qiáng)了代碼的功能性,并實(shí)現(xiàn)了切面編程（AOP）的精髓,其核心亮點(diǎn)之一,是運(yùn)用動(dòng)態(tài)代理技術(shù),無需觸動(dòng)源代碼即可在Bean的運(yùn)行時(shí)為其動(dòng)態(tài)織入額外功能,本文給大家介紹了SpringBoot通過3種方式實(shí)現(xiàn)AOP切面,需要的朋友可以參考下2024-08-08
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)排隊(duì)論的原理，對排隊(duì)論感興趣的小伙伴們可以參考一下2016-02-02
Java修改eclipse中web項(xiàng)目的server部署路徑問題
這篇文章主要介紹了Java修改eclipse中web項(xiàng)目的server部署路徑,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-11-11
這篇文章主要介紹了Spring中的JavaConfig知識，包括事務(wù)注解驅(qū)動(dòng)，properties配置文件加載方法，本文給大家介紹的非常詳細(xì),需要的朋友可以參考下2021-09-09
這篇文章主要介紹了Java如何讀取配置文件并賦值靜態(tài)變量,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-10-10
Java中比較器Comparable和Comparator超詳細(xì)解析
Java中在進(jìn)行數(shù)據(jù)排序時(shí),Comparable和Comparator必不可少會(huì)遇得到,這篇文章主要給大家介紹了關(guān)于Java中比較器Comparable和Comparator的相關(guān)資料,需要的朋友可以參考下2025-06-06
Java字符串駝峰與下?lián)Q線格式轉(zhuǎn)換如何實(shí)現(xiàn)
這篇文章主要介紹了Java字符串駝峰與下?lián)Q線格式轉(zhuǎn)換如何實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-11-11
idea顯示springboot多服務(wù)啟動(dòng)界面service操作
這篇文章主要介紹了idea顯示springboot多服務(wù)啟動(dòng)界面service操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
本文介紹了Spring Security的密碼編碼機(jī)制及其在Maven項(xiàng)目管理中的配置方式,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友參考下吧2025-10-10
這篇文章主要介紹了Java中觀察者模式與委托的對比,觀察者模式：定義了一種一對多的依賴關(guān)系，讓多個(gè)觀察者對象同時(shí)監(jiān)聽某一個(gè)主題對象，委托的實(shí)現(xiàn)簡單來講就是用反射來實(shí)現(xiàn)的，本文給大家介紹的非常詳細(xì)，需要的朋友可以參考下2022-05-05