摘要：源碼解析屬性雙向鏈表頭節(jié)點(diǎn)雙向鏈表尾節(jié)點(diǎn)是否按訪問順序排序雙向鏈表的頭節(jié)點(diǎn)，舊數(shù)據(jù)存在頭節(jié)點(diǎn)。雙向鏈表的尾節(jié)點(diǎn)，新數(shù)據(jù)存在尾節(jié)點(diǎn)。內(nèi)部類位于中位于中存儲節(jié)點(diǎn)，繼承自的類，用于單鏈表存儲于桶中，和用于雙向鏈表存儲所有元素。
簡介
LinkedHashMap內(nèi)部維護(hù)了一個雙向鏈表，能保證元素按插入的順序訪問，也能以訪問順序訪問，可以用來實(shí)現(xiàn)LRU緩存策略。
LinkedHashMap可以看成是 LinkedList + HashMap。
繼承體系
LinkedHashMap繼承HashMap，擁有HashMap的所有特性，并且額外增加的按一定順序訪問的特性
存儲結(jié)構(gòu)
我們知道HashMap使用（數(shù)組 + 單鏈表 + 紅黑樹）的存儲結(jié)構(gòu)，通過上面的繼承體系，我們知道LinkedHashMap繼承了Map，所以它的內(nèi)部也有這三種結(jié)構(gòu)，但是它還額外添加了一種“雙向鏈表”的結(jié)構(gòu)存儲所有元素的順序。
添加刪除元素的時候需要同時維護(hù)在HashMap中的存儲，也要維護(hù)在LinkedList中的存儲，所以性能上來說會比HashMap稍慢。
源碼解析
屬性
/**
* 雙向鏈表頭節(jié)點(diǎn)
*/
transient LinkedHashMap.Entry head;
/**
* 雙向鏈表尾節(jié)點(diǎn)
*/
transient LinkedHashMap.Entry tail;
/**
* 是否按訪問順序排序
*/
final boolean accessOrder;
1.head
雙向鏈表的頭節(jié)點(diǎn)，舊數(shù)據(jù)存在頭節(jié)點(diǎn)。
2.tail
雙向鏈表的尾節(jié)點(diǎn)，新數(shù)據(jù)存在尾節(jié)點(diǎn)。
3.accessOrder
是否需要按訪問順序排序，如果為false則按插入順序存儲元素，如果是true則按訪問順序存儲元素。
內(nèi)部類
// 位于LinkedHashMap中
static class Entry extends HashMap.Node {
Entry before, after;
Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}
}
// 位于HashMap中
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
}
存儲節(jié)點(diǎn)，繼承自HashMap的Node類，next用于單鏈表存儲于桶中，before和after用于雙向鏈表存儲所有元素。
構(gòu)造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
前四個構(gòu)造方法accessOrder都等于false，說明雙向鏈表是按插入順序存儲元素。
最后一個構(gòu)造方法accessOrder從構(gòu)造方法參數(shù)傳入，如果傳入true，則就實(shí)現(xiàn)了按訪問順序存儲元素，這也是實(shí)現(xiàn)LRU緩存策略的關(guān)鍵。
afterNodeInsertion(boolean evict)方法
在節(jié)點(diǎn)插入之后做些什么，在HashMap中的putVal()方法中被調(diào)用，可以看到HashMap中這個方法的實(shí)現(xiàn)為空。
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry eldest) {
return false;
}
如果evict為true，且頭節(jié)點(diǎn)不為空，且確定移除最老的元素，那么就調(diào)用HashMap.removeNode()把頭節(jié)點(diǎn)移除（這里的頭節(jié)點(diǎn)是雙向鏈表的頭節(jié)點(diǎn)，而不是某個桶中的第一個元素）；
HashMap.removeNode()從HashMap中把這個節(jié)點(diǎn)移除之后，會調(diào)用afterNodeRemoval()方法；
afterNodeRemoval()方法在LinkedHashMap中也有實(shí)現(xiàn)，用來在移除元素后修改雙向鏈表，見下文；
默認(rèn)removeEldestEntry()方法返回false，也就是不刪除元素。
afterNodeAccess(Node e)方法
在節(jié)點(diǎn)訪問之后被調(diào)用，主要在put()已經(jīng)存在的元素或get()時被調(diào)用，如果accessOrder為true，調(diào)用這個方法把訪問到的節(jié)點(diǎn)移動到雙向鏈表的末尾。
void afterNodeAccess(Node e) { // move node to last
LinkedHashMap.Entry last;
// 如果accessOrder為true，并且訪問的節(jié)點(diǎn)不是尾節(jié)點(diǎn)
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
// 把p節(jié)點(diǎn)從雙向鏈表中移除
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
// 把p節(jié)點(diǎn)放到雙向鏈表的末尾
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
// 尾節(jié)點(diǎn)等于p
tail = p;
++modCount;
}
}
如果accessOrder為true，并且訪問的節(jié)點(diǎn)不是尾節(jié)點(diǎn)；
從雙向鏈表中移除訪問的節(jié)點(diǎn)；
把訪問的節(jié)點(diǎn)加到雙向鏈表的末尾；（末尾為最新訪問的元素）
afterNodeRemoval(Node e)方法
在節(jié)點(diǎn)被刪除之后調(diào)用的方法。
void afterNodeRemoval(Node e) { // unlink
LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;
// 把節(jié)點(diǎn)p從雙向鏈表中刪除。
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
經(jīng)典的把節(jié)點(diǎn)從雙向鏈表中刪除的方法。
get(Object key)方法
獲取元素。
public V get(Object key) {
Node e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
如果查找到了元素，且accessOrder為true，則調(diào)用afterNodeAccess()方法把訪問的節(jié)點(diǎn)移到雙向鏈表的末尾。
總結(jié)
LinkedHashMap繼承自HashMap，具有HashMap的所有特性；
LinkedHashMap內(nèi)部維護(hù)了一個雙向鏈表存儲所有的元素；
如果accessOrder為false，則可以按插入元素的順序遍歷元素；
如果accessOrder為true，則可以按訪問元素的順序遍歷元素；
LinkedHashMap的實(shí)現(xiàn)非常精妙，很多方法都是在HashMap中留的鉤子（Hook），直接實(shí)現(xiàn)這些Hook就可以實(shí)現(xiàn)對應(yīng)的功能了，并不需要再重寫put()等方法；
默認(rèn)的LinkedHashMap并不會移除舊元素，如果需要移除舊元素，則需要重寫removeEldestEntry()方法設(shè)定移除策略；
LinkedHashMap可以用來實(shí)現(xiàn)LRU緩存淘汰策略；
LinkedHashMap 實(shí)現(xiàn)LRU緩存淘汰策略
LRU，Least Recently Used，最近最少使用，也就是優(yōu)先淘汰最近最少使用的元素。
如果使用LinkedHashMap，我們把a(bǔ)ccessOrder設(shè)置為true就差不多能實(shí)現(xiàn)這個策略了:
package com.coolcoding.code;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUTest {
public static void main(String[] args) {
// 創(chuàng)建一個只有5個元素的緩存
LRU lru = new LRU<>(5, 0.75f);
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
lru.put(4, 4);
lru.put(5, 5);
lru.put(6, 6);
lru.put(7, 7);
System.out.println(lru.get(4));
lru.put(6, 666);
// 輸出: {3=3, 5=5, 7=7, 4=4, 6=666}
// 可以看到最舊的元素被刪除了
// 且最近訪問的4被移到了后面
System.out.println(lru);
}
}
class LRU extends LinkedHashMap {
// 保存緩存的容量
private int capacity;
public LRU(int capacity, float loadFactor) {
super(capacity, loadFactor, true);
this.capacity = capacity;
}
/**
* 重寫removeEldestEntry()方法設(shè)置何時移除舊元素
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
// 當(dāng)元素個數(shù)大于了緩存的容量, 就移除元素
return size() > this.capacity;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/76075.html
