1、簡介
LinkedHashMap
屬于
Map
的一種，而
Map
是一種無序的
key-value
集合，但總有例外的情況，
LinkedHashMap
便是屬于例外的其中一個，其最大的特點是可以保持插入元素的順序。同時，可以編寫一個類繼承
LinkedHashMap
，實作其中特定的方法，完成一個具有LRU特性的Map集合
繼承結構圖：
可以看到，
LinkedHashMap
繼承了
HashMap
。它的内部有一個
Entry
連結清單結構，可以保持插入節點的順序，同時
Entry
繼承
HashMap
中的
Node
類（關于HashMap，可以看這一篇HashMap1.8），維護着
Node
節點的相關特性。
其内部存儲關系可從上圖了解，其中紅色箭頭代表
LinkedHashMap
維護的插入順序，黑色箭頭代表
HashMap
原本的内部連結清單關系
2、底層結構
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> {
//在HashMap的Node節點基礎之上，使用Entry，并添加了before和after節點，來保持插入順序
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);
}
}
//頭結點
transient LinkedHashMap.Entry<K,V> head;
//尾結點
transient LinkedHashMap.Entry<K,V> tail;
//lru開關，預設是fasle，設定為true可以實作lru
final boolean accessOrder;
}
主要是
Entry
這個資料結構，在
Node
的節點基礎之上，增加了新的連結清單節點，維護插入關系
3、構造函數
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//若是想實作lru，必須子類調用此構造函數
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
4、添加元素
LinkedHashMap
添加元素使用的是
HashMap
中的put方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
...//省略
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
...//省略
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
這裡有兩個方法需要注意，
newNode
和
afterNodeInsertion
。
LinkedHashMap
中重寫了這兩個方法
afterNodeInsertion
是實作LRU特性的方法之一
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//建立Entry節點
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
//添加節點到連結清單尾部
linkNodeLast(p);
return 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;
}
}
newNode
方法把新建立的節點添加到連結清單尾部，連結清單中尾部節點表示目前連結清單最新的節點
//evict預設為true
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//evict要為true，頭結點不能為null，removeEldestEntry要傳回true（預設為false）
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//删除節點
removeNode(hash(key), key, null, false, true);
}
}
//子類可以重寫該方法，實作LRU特性
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
5、查詢元素
public V get(Object key) {
Node<K,V> e;
//調用HashMap中的get方法擷取元素
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//實作LRU特性的方法之一
afterNodeAccess(e);
return e.value;
}
LinkedHashMap
重寫了
HashMap
中的get方法，實際還是調用
HashMap
中的方法擷取元素。
afterNodeAccess
是實作LRU特性方法之一，需要
accessOrder
為true才行，隻有在構造方法中才能指定其為true，預設是false
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
上述代碼主要幹了一件事，将目前通路的元素，加入到
LinkedHashMap
的連結清單尾部，而沒有通路的資料，會逐漸移動到連結清單的頭部
6、LRU demo
根據上面的分析，
LinkedHashMap
查詢時（accessOrder參數為true）會将查詢到的元素移動到連結清單的尾部，或者插入節點時，将節點插傳入連結表尾部，表明是目前最活躍的節點。連結清單的頭結點，自然就是最不活躍的節點。而重寫
removeEldestEntry
方法，就可以實作LRU特性
public class demo {
public static void main(String[] args) {
LinkedHashMap<String, String> lru = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > 3;
}
};
lru.put("1", "1");
lru.put("2", "2");
lru.put("3", "3");
lru.put("4", "4");
System.err.println(lru);
lru.get("2");
System.err.println(lru);
}
}
輸出為
{2=2, 3=3, 4=4}
{3=3, 4=4, 2=2}
可以看出，最早加入的"1"并不在集合中，并且調用key=“2”，其移動到了連結清單尾部