大多企業(yè)級項目開(kāi)發(fā)都會(huì )選擇Java，這使得我們Java工程師們都是“全能型”人才，這使得項目經(jīng)驗成為了Java人面試的重頭戲之一。
LinkedHashMap內部維護了一個(gè)雙向鏈表，能保證元素按插入的順序訪(fǎng)問(wèn)，也能以訪(fǎng)問(wèn)順序訪(fǎng)問(wèn)，可以用來(lái)實(shí)現LRU緩存策略。
LinkedHashMap可以看成是LinkedList+HashMap。
LinkedHashMap繼承HashMap，擁有HashMap的所有特性，并且額外增加的按一定順序訪(fǎng)問(wèn)的特性。
我們知道HashMap使用（數組+單鏈表+紅黑樹(shù)）的存儲結構，那LinkedHashMap是怎么存儲的呢？
通過(guò)上面的繼承體系，我們知道它繼承了Map，所以它的內部也有這三種結構，但是它還額外添加了一種“雙向鏈表”的結構存儲所有元素的順序。
添加刪除元素的時(shí)候需要同時(shí)維護在HashMap中的存儲，也要維護在LinkedList中的存儲，所以性能上來(lái)說(shuō)會(huì )比HashMap稍慢。
屬性
/** * 雙向鏈表頭節點(diǎn) */transient LinkedHashMap.Entry<K,V> head;/** * 雙向鏈表尾節點(diǎn) */transient LinkedHashMap.Entry<K,V> tail;/** * 是否按訪(fǎng)問(wèn)順序排序 */final boolean accessOrder;123456789101112131415復制代碼類(lèi)型：[java]
（1）head：雙向鏈表的頭節點(diǎn)，舊數據存在頭節點(diǎn)。
（2）tail：雙向鏈表的尾節點(diǎn)，新數據存在尾節點(diǎn)。
（3）accessOrder：是否需要按訪(fǎng)問(wèn)順序排序，如果為false則按插入順序存儲元素，如果是true則按訪(fǎng)問(wèn)順序存儲元素。
內部類(lèi)
// 位于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);
}
}// 位于HashMap中static class Node<K, V> implements Map.Entry<K, V> { final int hash; final K key;
V value;
Node<K, V> next;
}12345678910111213141516復制代碼類(lèi)型：[java]存儲節點(diǎn)，繼承自HashMap的Node類(lèi)，next用于單鏈表存儲于桶中，before和after用于雙向鏈表存儲所有元素。
構造方法
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<? extends K, ? extends V> m) { super();
accessOrder = false;
putMapEntries(m, false);
}public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;
}12345678910111213141516171819202122232425262728復制代碼類(lèi)型：[java]前四個(gè)構造方法accessOrder都等于false，說(shuō)明雙向鏈表是按插入順序存儲元素。
最后一個(gè)構造方法accessOrder從構造方法參數傳入，如果傳入true，則就實(shí)現了按訪(fǎng)問(wèn)順序存儲元素，這也是實(shí)現LRU緩存策略的關(guān)鍵。
afterNodeInsertion(booleanevict)方法
在節點(diǎn)插入之后做些什么，在HashMap中的putVal()方法中被調用，可以看到HashMap中這個(gè)方法的實(shí)現為空。
// evict 驅逐的意思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;
}12345678910111213復制代碼類(lèi)型：[java]（1）如果evict為true，且頭節點(diǎn)不為空，且確定移除最老的元素，那么就調用HashMap.removeNode()把頭節點(diǎn)移除（這里的頭節點(diǎn)是雙向鏈表的頭節點(diǎn)，而不是某個(gè)桶中的第一個(gè)元素）；
（2）HashMap.removeNode()從HashMap中把這個(gè)節點(diǎn)移除之后，會(huì )調用afterNodeRemoval()方法；
（3）afterNodeRemoval()方法在LinkedHashMap中也有實(shí)現，用來(lái)在移除元素后修改雙向鏈表，見(jiàn)下文；
（4）默認removeEldestEntry()方法返回false，也就是不刪除元素。
afterNodeAccess(Node<K,V>e)方法
在節點(diǎn)訪(fǎng)問(wèn)之后被調用，主要在put()已經(jīng)存在的元素或get()時(shí)被調用，如果accessOrder為true，調用這個(gè)方法把訪(fǎng)問(wèn)到的節點(diǎn)移動(dòng)到雙向鏈表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last; // 如果accessOrder為true，并且訪(fǎng)問(wèn)的節點(diǎn)不是尾節點(diǎn)
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // 把p節點(diǎn)從雙向鏈表中移除
p.after = null; if (b == null)
head = a; else
b.after = a; if (a != null)
a.before = b; else
last = b; // 把p節點(diǎn)放到雙向鏈表的末尾
if (last == null)
head = p; else {
p.before = last;
last.after = p;
} // 尾節點(diǎn)等于p
tail = p;
++modCount;
}
}12345678910111213141516171819202122232425262728293031復制代碼類(lèi)型：[java]（1）如果accessOrder為true，并且訪(fǎng)問(wèn)的節點(diǎn)不是尾節點(diǎn)；
（2）從雙向鏈表中移除訪(fǎng)問(wèn)的節點(diǎn)；
（3）把訪(fǎng)問(wèn)的節點(diǎn)加到雙向鏈表的末尾；（末尾為最新訪(fǎng)問(wèn)的元素）
afterNodeRemoval(Node<K,V>e)方法
在節點(diǎn)被刪除之后調用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; // 把節點(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;
}123456789101112131415復制代碼類(lèi)型：[java]經(jīng)典的把節點(diǎn)從雙向鏈表中刪除的方法。
get(Objectkey)方法
獲取元素。
public V get(Object key) {
Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder)
afterNodeAccess(e); return e.value;
}123456789復制代碼類(lèi)型：[java]如果查找到了元素，且accessOrder為true，則調用afterNodeAccess()方法把訪(fǎng)問(wèn)的節點(diǎn)移到雙向鏈表的末尾。
（1）LinkedHashMap繼承自HashMap，具有HashMap的所有特性；
（2）LinkedHashMap內部維護了一個(gè)雙向鏈表存儲所有的元素；
（3）如果accessOrder為false，則可以按插入元素的順序遍歷元素；
（4）如果accessOrder為true，則可以按訪(fǎng)問(wèn)元素的順序遍歷元素；
（5）LinkedHashMap的實(shí)現非常精妙，很多方法都是在HashMap中留的鉤子（Hook），直接實(shí)現這些Hook就可以實(shí)現對應的功能了，并不需要再重寫(xiě)put()等方法；
（6）默認的LinkedHashMap并不會(huì )移除舊元素，如果需要移除舊元素，則需要重寫(xiě)removeEldestEntry()方法設定移除策略；
（7）LinkedHashMap可以用來(lái)實(shí)現LRU緩存淘汰策略；
LinkedHashMap如何實(shí)現LRU緩存淘汰策略呢？
首先，我們先來(lái)看看LRU是個(gè)什么鬼。LRU，LeastRecentlyUsed，最近最少使用，也就是優(yōu)先淘汰最近最少使用的元素。
如果使用LinkedHashMap，我們把accessOrder設置為true是不是就差不多能實(shí)現這個(gè)策略了呢？答案是肯定的。請看下面的代碼：
package com.cn.test;import java.util.LinkedHashMap;import java.util.Map;public class Test { public static void main(String[] args) { // 創(chuàng )建一個(gè)只有5個(gè)元素的緩存
LRU<Integer, Integer> 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)); // 輸出: {3=3, 5=5, 6=6, 7=7, 4=4}
// 可以看到最舊的元素被刪除了
// 且最近訪(fǎng)問(wèn)的4被移到了后面
System.out.println(lru);
}
}class LRU<K, V> extends LinkedHashMap<K, V> { // 保存緩存的容量
private int capacity; public LRU(int capacity, float loadFactor) { super(capacity, loadFactor, true); this.capacity = capacity;
} /**
* 重寫(xiě)removeEldestEntry()方法設置何時(shí)移除舊元素
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { // 當元素個(gè)數大于了緩存的容量, 就移除元素
return size() > this.capacity;
}
}12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152復制代碼類(lèi)型：[java]
聯(lián)系客服
