Java LinkedHashMap 底層實(shí)現(xiàn)原理分析
在實(shí)現(xiàn)上，LinkedHashMap很多方法直接繼承自HashMap，僅為維護(hù)雙向鏈表覆寫了部分方法。所以，要看懂 LinkedHashMap 的源碼，需要先看懂 HashMap 的源碼。
默認(rèn)情況下，LinkedHashMap的迭代順序是按照插入節(jié)點(diǎn)的順序。也可以通過(guò)改變accessOrder參數(shù)的值，使得其遍歷順序按照訪問(wèn)順序輸出。
這里我們只討論LinkedHashMap和HashMap的不同之處，LinkedHashMap的其他操作和特性具體請(qǐng)參考HashMap
我們先來(lái)看下兩者的區(qū)別：
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;
public class Test04 {
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>();
map.put("ahdjkf", "1");
map.put("ifjdj", "2");
map.put("giafdja", "3");
map.put("agad", "4");
map.put("ahdjkge", "5");
map.put("iegnj", "6");
System.out.println("LinkedHashMap的迭代順序(accessOrder=false)：");
Iterator iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry entry = (Map.Entry) iterator.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
Map<String, String> map1 = new LinkedHashMap<String, String>(16,0.75f,true);
map1.put("ahdjkf", "1");
map1.put("ifjdj", "2");
map1.put("giafdja", "3");
map1.put("agad", "4");
map1.put("ahdjkge", "5");
map1.put("iegnj", "6");
map1.get("ahdjkf");
map1.get("ifjdj");
System.out.println("LinkedHashMap的迭代順序(accessOrder=true)：");
Iterator iterator1 = map1.entrySet().iterator();
while (iterator1.hasNext()) {
Map.Entry entry = (Map.Entry) iterator1.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
Map<String, String> map2 = new HashMap<>();
map2.put("ahdjkf", "1");
map2.put("ifjdj", "2");
map2.put("giafdja", "3");
map2.put("agad", "4");
map2.put("ahdjkge", "5");
map2.put("iegnj", "6");
System.out.println("HashMap的迭代順序：");
Iterator iterator2 = map2.entrySet().iterator();
while (iterator2.hasNext()) {
Map.Entry aMap = (Map.Entry) iterator2.next();
System.out.println(aMap.getKey() + "=" + aMap.getValue());
}
}
}
Output：
LinkedHashMap的迭代順序(accessOrder=false)：
ahdjkf=1
ifjdj=2
giafdja=3
agad=4
ahdjkge=5
iegnj=6
LinkedHashMap的迭代順序(accessOrder=true)：
giafdja=3
agad=4
ahdjkge=5
iegnj=6
ahdjkf=1
ifjdj=2
HashMap的迭代順序：
iegnj=6
giafdja=3
ifjdj=2
agad=4
ahdjkf=1
ahdjkge=5
可以看到 LinkedHashMap在每次插入數(shù)據(jù)，訪問(wèn)、修改數(shù)據(jù)時(shí)都會(huì)調(diào)整鏈表的節(jié)點(diǎn)順序。以決定迭代時(shí)輸出的順序。
下面我們來(lái)看LinkedHashMap具體是怎么實(shí)現(xiàn)的：
LinkedHashMap繼承了HashMap，內(nèi)部靜態(tài)類Entry繼承了HashMap的Entry，但是LinkedHashMap.Entry多了兩個(gè)字段：before和after，before表示在本節(jié)點(diǎn)之前添加到LinkedHashMap的那個(gè)節(jié)點(diǎn)，after表示在本節(jié)點(diǎn)之后添加到LinkedHashMap的那個(gè)節(jié)點(diǎn)，這里的之前和之后指時(shí)間上的先后順序。
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
同時(shí)類里有兩個(gè)成員變量head和tail,分別指向內(nèi)部雙向鏈表的表頭、表尾。
//雙向鏈表的頭結(jié)點(diǎn) transient LinkedHashMap.Entry<K,V> head; //雙向鏈表的尾節(jié)點(diǎn) transient LinkedHashMap.Entry<K,V> tail;
將LinkedHashMap的accessOrder字段設(shè)置為true后，每次訪問(wèn)哈希表中的節(jié)點(diǎn)都將該節(jié)點(diǎn)移到鏈表的末尾，表示該節(jié)點(diǎn)是最新訪問(wèn)的節(jié)點(diǎn)。即循環(huán)雙向鏈表的頭部存放的是最久訪問(wèn)的節(jié)點(diǎn)或最先插入的節(jié)點(diǎn)，尾部為最近訪問(wèn)的或最近插入的節(jié)點(diǎn)。
由于增加了一個(gè)accessOrder屬性，LinkedHashMap相對(duì)HashMap來(lái)說(shuō)增加了一個(gè)構(gòu)造方法用來(lái)控制迭代順序。
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化時(shí)的容量，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化時(shí)的容量，和擴(kuò)容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定初始化時(shí)的容量，和擴(kuò)容的加載因子，以及迭代輸出節(jié)點(diǎn)的順序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//利用另一個(gè)Map 來(lái)構(gòu)建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
//該方法上文分析過(guò)，批量插入一個(gè)map中的所有數(shù)據(jù)到 本集合中。
putMapEntries(m, false);
}
添加元素
LinkedHashMap在添加元素的時(shí)候，依舊使用的是HashMap中的put方法。不同的是LinkedHashMap重寫了newNode()方法在每次構(gòu)建新節(jié)點(diǎn)時(shí)，通過(guò)linkNodeLast(p);將新節(jié)點(diǎn)鏈接在內(nèi)部雙向鏈表的尾部。
//將新增的節(jié)點(diǎn)，連接在鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
//如果集合之前是空的
if (last == null)
head = p;
else {//將新節(jié)點(diǎn)連接在鏈表的尾部
p.before = last;
last.after = p;
}
}
刪除元素
LinkedHashMap并沒(méi)有重寫HashMap的remove()方法，但是他重寫了afterNodeRemoval()方法，這個(gè)方法的作用是在刪除一個(gè)節(jié)點(diǎn)時(shí)，同步將該節(jié)點(diǎn)從雙向鏈表中刪除。該方法將會(huì)在remove中被回調(diào)。
//在刪除節(jié)點(diǎn)e時(shí)，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//將待刪除節(jié)點(diǎn) p 的前置后置節(jié)點(diǎn)都置空
p.before = p.after = null;
//如果前置節(jié)點(diǎn)是null，則說(shuō)明現(xiàn)在的頭結(jié)點(diǎn)應(yīng)該是后置節(jié)點(diǎn)a
if (b == null)
head = a;
else//否則將前置節(jié)點(diǎn)b的后置節(jié)點(diǎn)指向a
b.after = a;
//同理如果后置節(jié)點(diǎn)時(shí)null ，則尾節(jié)點(diǎn)應(yīng)是b
if (a == null)
tail = b;
else//否則更新后置節(jié)點(diǎn)a的前置節(jié)點(diǎn)為b
a.before = b;
}
刪除過(guò)程總的來(lái)說(shuō)可以分為三步：
- 根據(jù) hash 定位到桶位置
- 遍歷鏈表或調(diào)用紅黑樹(shù)相關(guān)的刪除方法
- 回調(diào)afterNodeRemoval，從 LinkedHashMap 維護(hù)的雙鏈表中移除要?jiǎng)h除的節(jié)點(diǎn)
更新元素
// 清除節(jié)點(diǎn)時(shí)要將頭尾節(jié)點(diǎn)一起清除
public void clear() {
super.clear();
head = tail = null;
}
查找元素
LinkedHashMap重寫了get()和getOrDefault()方法
默認(rèn)情況下，LinkedHashMap是按插入順序維護(hù)鏈表。不過(guò)如果我們?cè)诔跏蓟?LinkedHashMap時(shí)，指定 accessOrder參數(shù)為 true，即可讓它按訪問(wèn)順序維護(hù)鏈表。訪問(wèn)順序的原理是，當(dāng)我們調(diào)用get/getOrDefault/replace等方法時(shí)，會(huì)將這些方法訪問(wèn)的節(jié)點(diǎn)移動(dòng)到鏈表的尾部。
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) // 回調(diào)afterNodeAccess(Node<K,V> e)
afterNodeAccess(e); // 將節(jié)點(diǎn)e移至雙向鏈表的尾部（保證迭代順序）
return e.value;
}
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e); // 作用同上
return e.value;
}
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;//原尾節(jié)點(diǎn)
//如果accessOrder 是true ，且原尾節(jié)點(diǎn)不等于e
if (accessOrder && (last = tail) != e) {
//節(jié)點(diǎn)e強(qiáng)轉(zhuǎn)成雙向鏈表節(jié)點(diǎn)p
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p現(xiàn)在是尾節(jié)點(diǎn)， 后置節(jié)點(diǎn)一定是null
p.after = null;
//如果p的前置節(jié)點(diǎn)是null，則p以前是頭結(jié)點(diǎn)，所以更新現(xiàn)在的頭結(jié)點(diǎn)是p的后置節(jié)點(diǎn)a
if (b == null)
head = a;
else//否則更新p的前直接點(diǎn)b的后置節(jié)點(diǎn)為 a
b.after = a;
//如果p的后置節(jié)點(diǎn)不是null，則更新后置節(jié)點(diǎn)a的前置節(jié)點(diǎn)為b
if (a != null)
a.before = b;
else//如果原本p的后置節(jié)點(diǎn)是null，則p就是尾節(jié)點(diǎn)。 此時(shí) 更新last的引用為 p的前置節(jié)點(diǎn)b
last = b;
if (last == null) //原本尾節(jié)點(diǎn)是null 則，鏈表中就一個(gè)節(jié)點(diǎn)
head = p;
else {//否則 更新 當(dāng)前節(jié)點(diǎn)p的前置節(jié)點(diǎn)為 原尾節(jié)點(diǎn)last， last的后置節(jié)點(diǎn)是p
p.before = last;
last.after = p;
}
//尾節(jié)點(diǎn)的引用賦值成p
tail = p;
//修改modCount。
++modCount;
}
}
// 因?yàn)長(zhǎng)inkedHashMap中維護(hù)了一個(gè)雙向鏈表所以相對(duì)于HashMap中的雙重循環(huán)遍歷這個(gè)方法要優(yōu)化很多
LinkedHashMap
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { // 通過(guò)雙向鏈表來(lái)遍歷
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
HashMap
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
其他方法
LinkedHashMap還有一個(gè)比較神奇的存在。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 根據(jù)條件判斷是否移除最近最少被訪問(wèn)的節(jié)點(diǎn)
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 移除最近最少被訪問(wèn)條件之一，通過(guò)覆蓋此方法可實(shí)現(xiàn)不同策略的緩存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
上面的方法一般不會(huì)被執(zhí)行，但是當(dāng)我們基于 LinkedHashMap 實(shí)現(xiàn)緩存時(shí)，通過(guò)覆寫removeEldestEntry方法可以實(shí)現(xiàn)自定義策略的 LRU 緩存。比如我們可以根據(jù)節(jié)點(diǎn)數(shù)量判斷是否移除最近最少被訪問(wèn)的節(jié)點(diǎn)，或者根據(jù)節(jié)點(diǎn)的存活時(shí)間判斷是否移除該節(jié)點(diǎn)等。
迭代器
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
//返回LinkedEntrySet
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
}
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class LinkedHashIterator {
//下一個(gè)節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> next;
//當(dāng)前節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//初始化時(shí)，next 為 LinkedHashMap內(nèi)部維護(hù)的雙向鏈表的扁頭
next = head;
//記錄當(dāng)前modCount，以滿足fail-fast
expectedModCount = modCount;
//當(dāng)前節(jié)點(diǎn)為null
current = null;
}
//判斷是否還有next
public final boolean hasNext() {
//就是判斷next是否為null，默認(rèn)next是head 表頭
return next != null;
}
//nextNode() 就是迭代器里的next()方法 。
//該方法的實(shí)現(xiàn)可以看出，迭代LinkedHashMap，就是從內(nèi)部維護(hù)的雙鏈表的表頭開(kāi)始循環(huán)輸出。
final LinkedHashMap.Entry<K,V> nextNode() {
//記錄要返回的e。
LinkedHashMap.Entry<K,V> e = next;
//判斷fail-fast
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//如果要返回的節(jié)點(diǎn)是null，異常
if (e == null)
throw new NoSuchElementException();
//更新當(dāng)前節(jié)點(diǎn)為e
current = e;
//更新下一個(gè)節(jié)點(diǎn)是e的后置節(jié)點(diǎn)
next = e.after;
//返回e
return e;
}
//刪除方法 最終還是調(diào)用了HashMap的removeNode方法
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
該方法的實(shí)現(xiàn)可以看出，迭代LinkedHashMap，就是從內(nèi)部維護(hù)的雙鏈表的表頭開(kāi)始循環(huán)輸出。而雙鏈表節(jié)點(diǎn)的順序在LinkedHashMap的增、刪、改、查時(shí)都會(huì)更新。以滿足按照插入順序輸出，還是訪問(wèn)順序輸出。
總結(jié)
在日常開(kāi)發(fā)中LinkedHashMap 的使用頻率沒(méi)有HashMap高，但它也個(gè)重要的實(shí)現(xiàn)。
在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三個(gè)映射類基于不同的數(shù)據(jù)結(jié)構(gòu)，并實(shí)現(xiàn)了不同的功能。
HashMap 底層基于拉鏈?zhǔn)降纳⒘薪Y(jié)構(gòu)，并在 JDK 1.8 中引入紅黑樹(shù)優(yōu)化過(guò)長(zhǎng)鏈表的問(wèn)題?；谶@樣結(jié)構(gòu)，HashMap 可提供高效的增刪改查操作。
LinkedHashMap 在其之上，通過(guò)維護(hù)一條雙向鏈表，實(shí)現(xiàn)了散列數(shù)據(jù)結(jié)構(gòu)的有序遍歷。
TreeMap 底層基于紅黑樹(shù)實(shí)現(xiàn)，利用紅黑樹(shù)的性質(zhì)，實(shí)現(xiàn)了鍵值對(duì)排序功能。具體實(shí)現(xiàn)我們下次分析。
以上就是Java LinkedHashMap 底層實(shí)現(xiàn)原理分析的詳細(xì)內(nèi)容，更多關(guān)于Java LinkedHashMap 底層實(shí)現(xiàn)原理的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
詳解springboot項(xiàng)目帶Tomcat和不帶Tomcat的兩種打包方式
這篇文章主要介紹了詳解springboot項(xiàng)目帶Tomcat和不帶Tomcat的兩種打包方式，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
平時(shí)使用Ctrl+Alt+L可以格式化代碼,idea幫你整理空格,換行等,讓代碼看起來(lái)更整潔,今天通過(guò)本文給大家分享IDEA?Reformat?Code?格式化?的過(guò)程,感興趣的朋友一起看看吧2023-11-11
MybatisX-Generator自動(dòng)代碼生成插件教程
這篇文章主要介紹了MybatisX-Generator自動(dòng)代碼生成插件教程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-04-04
Java Poi 在Excel中輸出特殊符號(hào)的實(shí)現(xiàn)方法
這篇文章主要介紹了Java Poi 在Excel中輸出特殊符號(hào)的實(shí)現(xiàn)方法，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07
SpringBoot JPA出現(xiàn)錯(cuò)誤:No identifier specified&nb
這篇文章主要介紹了SpringBoot JPA出現(xiàn)錯(cuò)誤:No identifier specified for en解決方案，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
在非spring環(huán)境中調(diào)用service中的方法
非Spring環(huán)境指的是不使用Spring框架來(lái)管理和配置應(yīng)用程序的運(yùn)行時(shí)環(huán)境,本文將給大家介紹如何在非spring環(huán)境中調(diào)用service中的方法,文中有詳細(xì)實(shí)現(xiàn)步驟,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了JAVA 枚舉（enum）的相關(guān)資料，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
java實(shí)現(xiàn)乘地鐵方案的最優(yōu)選擇（票價(jià)，距離）
這篇文章主要介紹了java實(shí)現(xiàn)乘地鐵方案的最優(yōu)選擇（票價(jià)，距離）,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-07-07
Java虛擬機(jī)把描述類的數(shù)據(jù)從Class文件加載到內(nèi)存，并對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)、轉(zhuǎn)換解析和初始化，最終形成可以被虛擬機(jī)直接使用的Java類型，這個(gè)過(guò)程被稱作虛擬機(jī)的類加載機(jī)制。本文將詳解Java的類加載機(jī)制，需要的可以參考一下2022-05-05
MyBatisPlus的IService接口實(shí)現(xiàn)
MyBatisPlus是一個(gè)為MyBatis提供增強(qiáng)的工具,它通過(guò)IService接口簡(jiǎn)化了數(shù)據(jù)庫(kù)的CRUD操作,IService接口封裝了一系列常用的數(shù)據(jù)操作方法,本文就來(lái)介紹一下,感興趣的可以了解一下2024-10-10