溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章為大家展示了Java中LinkedHashMap 的底層原理是什么，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
默認情況下，LinkedHashMap的迭代順序是按照插入節點的順序。也可以通過改變accessOrder參數的值，使得其遍歷順序按照訪問順序輸出。
這里我們只討論LinkedHashMap和HashMap的不同之處，LinkedHashMap的其他操作和特性具體請參考HashMap
我們先來看下兩者的區別：
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在每次插入數據，訪問、修改數據時都會調整鏈表的節點順序。以決定迭代時輸出的順序。
下面我們來看LinkedHashMap具體是怎么實現的：
LinkedHashMap繼承了HashMap，內部靜態類Entry繼承了HashMap的Entry，但是LinkedHashMap.Entry多了兩個字段：before和after，before表示在本節點之前添加到LinkedHashMap的那個節點，after表示在本節點之后添加到LinkedHashMap的那個節點，這里的之前和之后指時間上的先后順序。
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);
}
}同時類里有兩個成員變量head和tail,分別指向內部雙向鏈表的表頭、表尾。
//雙向鏈表的頭結點 transient LinkedHashMap.Entry<K,V> head; //雙向鏈表的尾節點 transient LinkedHashMap.Entry<K,V> tail;
將LinkedHashMap的accessOrder字段設置為true后，每次訪問哈希表中的節點都將該節點移到鏈表的末尾，表示該節點是最新訪問的節點。即循環雙向鏈表的頭部存放的是最久訪問的節點或最先插入的節點，尾部為最近訪問的或最近插入的節點。
由于增加了一個accessOrder屬性，LinkedHashMap相對HashMap來說增加了一個構造方法用來控制迭代順序。
final boolean accessOrder;
public LinkedHashMap() {
super();
accessOrder = false;
}
//指定初始化時的容量，
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
//指定初始化時的容量，和擴容的加載因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
//指定初始化時的容量，和擴容的加載因子，以及迭代輸出節點的順序
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//利用另一個Map 來構建
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
//該方法上文分析過，批量插入一個map中的所有數據到 本集合中。
putMapEntries(m, false);
}LinkedHashMap在添加元素的時候，依舊使用的是HashMap中的put方法。不同的是LinkedHashMap重寫了newNode()方法在每次構建新節點時，通過linkNodeLast(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并沒有重寫HashMap的remove()方法，但是他重寫了afterNodeRemoval()方法，這個方法的作用是在刪除一個節點時，同步將該節點從雙向鏈表中刪除。該方法將會在remove中被回調。
//在刪除節點e時，同步將e從雙向鏈表上刪除
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//將待刪除節點 p 的前置后置節點都置空
p.before = p.after = null;
//如果前置節點是null，則說明現在的頭結點應該是后置節點a
if (b == null)
head = a;
else//否則將前置節點b的后置節點指向a
b.after = a;
//同理如果后置節點時null ，則尾節點應是b
if (a == null)
tail = b;
else//否則更新后置節點a的前置節點為b
a.before = b;
}刪除過程總的來說可以分為三步：
根據 hash 定位到桶位置
遍歷鏈表或調用紅黑樹相關的刪除方法
回調afterNodeRemoval，從 LinkedHashMap 維護的雙鏈表中移除要刪除的節點
// 清除節點時要將頭尾節點一起清除
public void clear() {
super.clear();
head = tail = null;
}LinkedHashMap重寫了get()和getOrDefault()方法
默認情況下，LinkedHashMap是按插入順序維護鏈表。不過如果我們在初始化 LinkedHashMap時，指定 accessOrder參數為 true，即可讓它按訪問順序維護鏈表。訪問順序的原理是，當我們調用get/getOrDefault/replace等方法時，會將這些方法訪問的節點移動到鏈表的尾部。
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) // 回調afterNodeAccess(Node<K,V> e)
afterNodeAccess(e); // 將節點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;//原尾節點
//如果accessOrder 是true ，且原尾節點不等于e
if (accessOrder && (last = tail) != e) {
//節點e強轉成雙向鏈表節點p
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//p現在是尾節點， 后置節點一定是null
p.after = null;
//如果p的前置節點是null，則p以前是頭結點，所以更新現在的頭結點是p的后置節點a
if (b == null)
head = a;
else//否則更新p的前直接點b的后置節點為 a
b.after = a;
//如果p的后置節點不是null，則更新后置節點a的前置節點為b
if (a != null)
a.before = b;
else//如果原本p的后置節點是null，則p就是尾節點。 此時 更新last的引用為 p的前置節點b
last = b;
if (last == null) //原本尾節點是null 則，鏈表中就一個節點
head = p;
else {//否則 更新 當前節點p的前置節點為 原尾節點last， last的后置節點是p
p.before = last;
last.after = p;
}
//尾節點的引用賦值成p
tail = p;
//修改modCount。
++modCount;
}
}
// 因為LinkedHashMap中維護了一個雙向鏈表所以相對于HashMap中的雙重循環遍歷這個方法要優化很多
LinkedHashMap
public boolean containsValue(Object value) {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) { // 通過雙向鏈表來遍歷
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還有一個比較神奇的存在。
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;
}上面的方法一般不會被執行，但是當我們基于 LinkedHashMap 實現緩存時，通過覆寫removeEldestEntry方法可以實現自定義策略的 LRU 緩存。比如我們可以根據節點數量判斷是否移除最近最少被訪問的節點，或者根據節點的存活時間判斷是否移除該節點等。
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 {
//下一個節點
LinkedHashMap.Entry<K,V> next;
//當前節點
LinkedHashMap.Entry<K,V> current;
int expectedModCount;
LinkedHashIterator() {
//初始化時，next 為 LinkedHashMap內部維護的雙向鏈表的扁頭
next = head;
//記錄當前modCount，以滿足fail-fast
expectedModCount = modCount;
//當前節點為null
current = null;
}
//判斷是否還有next
public final boolean hasNext() {
//就是判斷next是否為null，默認next是head 表頭
return next != null;
}
//nextNode() 就是迭代器里的next()方法 。
//該方法的實現可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開始循環輸出。
final LinkedHashMap.Entry<K,V> nextNode() {
//記錄要返回的e。
LinkedHashMap.Entry<K,V> e = next;
//判斷fail-fast
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//如果要返回的節點是null，異常
if (e == null)
throw new NoSuchElementException();
//更新當前節點為e
current = e;
//更新下一個節點是e的后置節點
next = e.after;
//返回e
return e;
}
//刪除方法 最終還是調用了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;
}
}該方法的實現可以看出，迭代LinkedHashMap，就是從內部維護的雙鏈表的表頭開始循環輸出。而雙鏈表節點的順序在LinkedHashMap的增、刪、改、查時都會更新。以滿足按照插入順序輸出，還是訪問順序輸出。
1.SpringMVC，Spring Web MVC是一種基于Java的實現了Web MVC設計模式的請求驅動類型的輕量級Web框架。2.Shiro，Apache Shiro是Java的一個安全框架。3.Mybatis，MyBatis 是支持普通 SQL查詢，存儲過程和高級映射的優秀持久層框架。4.Dubbo，Dubbo是一個分布式服務框架。5.Maven，Maven是個項目管理和構建自動化工具。6.RabbitMQ，RabbitMQ是用Erlang實現的一個高并發高可靠AMQP消息隊列服務器。7.Ehcache，EhCache 是一個純Java的進程內緩存框架。
上述內容就是Java中LinkedHashMap 的底層原理是什么，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
