LinkedHashMap 是什么参咙，能做什么，這里就不再展開講了。這篇博客 有相關介紹宠哄，并展示了 LinkedHashMap 的核心原理，但是我發(fā)現(xiàn)我的 jdk 里的源代碼和博主提供的源代碼示例不一致嗤攻，我的是 "12.0.1" 2019-04-16毛嫉，所以就寫了這篇文章，看看新版本的有哪些調整妇菱，以及為什么有這些調整承粤。
1. 類注釋
在類注釋中，總結一下大致有以下幾個要點：
- 與 HashMap 不同恶耽，LinkedHashMap 維護了一個雙向鏈表來定義迭代順序
- re-insert 一個已有的元素不會改變迭代順序
- 迭代順序默認按插入順序，但是也可以初始化為按訪問順序颜启，這樣就很適合用來實現(xiàn) LRU cache
- 在 LinkedHashMap 上迭代的時間復雜度是 O(size)偷俭，而在 HashMap 上迭代是 O(capacity). 其他操作基本上都是 O(1)，但因為維護雙向鏈表的原因缰盏，性能上稍微遜于 HashMap
- LinkedHashMap 的性能受 initial capacity 和 load factor 的影響涌萤，這兩個參數(shù)是從 HashMap 繼承下來的，所以 HashMap 也是口猜；但是因為迭代策略的不同负溪，initial capacity 的值很大，不會直接影響迭代性能
- 線程不安全济炎。因為繼承自 HashMap川抡，許多性質也一樣
- add/delete 會影響到迭代順序；插入順序下须尚，改變 pair 的 value 不會影響崖堤；訪問順序下，get 操作也會影響到迭代順序耐床。這個根據(jù)定義很好理解
- 迭代過程中如果被其他線程修改密幔，會以 fail-fast 的策略盡快拋出 ConcurrentModificationException，需要注意的是撩轰，這個也只是 best-effort 的行為胯甩，并不能保證在沖突的第一時間就拋出異常，所以捕獲異常后的 map 是不確定的
- 應該是 JDK8 新增的并行部分堪嫂，暫時沒看 The spliterators returned by the spliterator method of the collections returned by all of this class's collection view methods are <a href="Spliterator.html#binding">late-binding</a></em>,<em>fail-fast</em>, and additionally report {@link Spliterator#ORDERED}.
2. 繼承結構
LinkedHashMap 繼承自 HashMap偎箫，重用了部分屬性，重寫了部分方法皆串；自己額外定義的主要包括一些內部類镜廉、構造函數(shù)等。
3. 從一個 demo 開始
public class Test {
public static void main(String[] args) {
LinkedHashMap<String, String> map = new LinkedHashMap<>();
map.put("111", "111");
map.put("333", "333");
map.put("222", "222");
System.out.println(map);
HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("111", "111");
hashMap.put("333", "333");
hashMap.put("222", "222");
System.out.println(hashMap);
}
}
// output
{111=111, 333=333, 222=222}
{111=111, 222=222, 333=333}
println 方法對 object 類型的參數(shù)愚战，會調用 object 的 toString() 方法娇唯；map 系列的這個方法是定義在 AbstractMap 里面的齐遵，拿到 entrySet 的 iterator，再通過 iterator 的 next 方法來迭代塔插。
// AbstractMap.java
public String toString() {
Iterator<Entry<K,V>> i = entrySet().iterator();
//...
for (;;) {
Entry<K,V> e = i.next();
//...
}
}
// AbstractMap.java
public abstract Set<Entry<K,V>> entrySet();
而 LinkedHashMap 和 HashMap 的 entrySet() 方法也不相同梗摇，
// LinkedHashMap.java
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
// HashMap.java
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
所以主要是 LinkedEntrySet 和 EntrySet 導致的區(qū)別，下面列出了有區(qū)別的方法想许，可以發(fā)現(xiàn)實際上又是 Iterator 導致的區(qū)別
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (Node<K,V> e : tab) {
for (; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
final class LinkedEntrySet extends AbstractSet<Map.Entry<K,V>> {
public final Iterator<Map.Entry<K,V>> iterator() {
return new LinkedEntryIterator();
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
if (action == null)
throw new NullPointerException();
int mc = modCount;
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
action.accept(e);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
兩者的 iterator 的 next(）方法都是調用了
public final Map.Entry<K,V> next() { return nextNode(); }
首先注意伶授，nextNode() 返回的是初始化/上次計算 的 next 值，并計算出下一個值流纹。nextNode 在 LinkedHashMap 和 HashMap 中有者不同的實現(xiàn)糜烹，
先來看看 HashIterator
next 由 HashIterator 構造函數(shù)初始化，并在 nextNode 方法中更新漱凝。table 是 hash bucket疮蹦，一個數(shù)組。
首先是一個 fast-fail 地檢測是否被并發(fā) add/delete 了茸炒，（這個機制請參考其他博客愕乎，這里不再贅述），然后把指針在 table 上后移壁公，如果 next 不為空則直接返回感论；如果為空，則要跳過一個槽看下一個紊册，循環(huán)比肄；
所以，HashMap 的迭代復雜度是 O(capacity)囊陡，因為它需要檢查 table 上的每一個元素
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
}
再來看看 LinkedHashIterator
一樣的 fail-fast check薪前，但是神奇的地方出現(xiàn)了，next = e.after关斜，完事兒示括，完全不跟你多bb×⌒螅可以肯定垛膝，這個 after 指向的肯定是按 insert order/access order 的下一個元素。那么這個 after 又是哪里冒出來的呢丁稀？
abstract class LinkedHashIterator {
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
}
所以吼拥，問題的核心還是回到了 LinkedHashMap.Entry 上。
在 Collections 框架里线衫，Entry 應該是接口凿可，用于定義鍵值對；實體類應該是 XXXNode 才對。對于這一點枯跑，源代碼中的注釋也給出了說明：HashMap now uses trees for some of its nodes, class LinkedHashMap.Entry is now treated as intermediary node class that can also be converted to tree form. The name of this class, LinkedHashMap.Entry, is confusing in several ways in its current context, but cannot be changed. but cannot be changed Otherwise, even though it is not exported outside this package, some existing source code is known to have relied on a symbol resolution corner case rule in calls to removeEldestEntry that suppressed compilation errors due to ambiguous usages. So, we keep the name to preserve unmodified compilability.
也就是說惨驶，一開始沒有考慮到規(guī)范性的問題，而 HashMap 又用了 LinkedHashMap.Entry 來實現(xiàn) TreeNode敛助；即使這個靜態(tài)內部類沒有暴露出去粗卜，但是有的程序，是通過名字來解析這個類的纳击，如果改了名字會導致編譯都過不了续扔，所以為了兼容就不改了。
HashMap 中定義了 Node焕数，LinkedHashMap.Entry 繼承自 Node纱昧。多了兩個屬性變量，before 和 after堡赔。根據(jù)名字我們可以猜到识脆，這是一個雙向鏈表的元素。源代碼如下加匈，但是初始化一個 Entry 的時候并沒有設置 before 和 after 信息存璃，那么雙向鏈表的維護必定是在 Map 的操作過程中仑荐。
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
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);
}
}
經(jīng)過上述分析雕拼，我們已經(jīng)清楚 LinkedHashMap 的大致結構和原理。下面我們來具體看看這個雙向鏈表是怎么維護的粘招。
回到我們一開始的程序
public class Test {
public static void main(String[] args) {
LinkedHashMap<String, String> map = new LinkedHashMap<>();
map.put("111", "111");
map.put("333", "333");
map.put("222", "222");
System.out.println(map);
}
}
// output
{111=111, 333=333, 222=222}
檢查 LinkedHashMap 的構造函數(shù)啥寇，accessOrder 被設置為 false.
public LinkedHashMap() {
super();
accessOrder = false;
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 標識 LinkedHashMap 的迭代順序: {@code true}
* for access-order, {@code false} for insertion-order.
*/
final boolean accessOrder;
再看 put 方法，直接就進入了 HashMap 里面洒扎。奇怪了對吧辑甜？沒有重寫 put 方法。那是在哪里設置的 before/after 呢?
PS：putVal 方法比較復雜袍冷，是個核心算法磷醋，可以研究下。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods.
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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 ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
HashMap 的 putVal 方法調用了 newNode()胡诗，afterNodeAccess() 等邓线。在 HashMap 的源代碼中可以看見如下注釋：
/* ------------------------------------------------------------ */
// LinkedHashMap support
/*
* The following package-protected methods are designed to be
* overridden by LinkedHashMap, but not by any other subclass.
* Nearly all other internal methods are also package-protected
* but are declared final, so can be used by LinkedHashMap, view
* classes, and HashSet.
*/
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
...
而在 LinkedHashMap 中，這些方法都被重寫了
以 newNode 為例煌恢，初始化一個 entry 后骇陈，調用 linkNodeLast 來維護 before/after 指針。到這里瑰抵，我們終于知道為什么 LinkedHashMap 有順序了你雌。LinkedHashMap 也需要在其他方法里補上對 before/after 的操作，這里不再逐一分析二汛。
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}
// internal utilities
// link at the end of list
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;
}
}
還有一件事婿崭，那就是如何通過 accessOrder 來區(qū)分 insert order/access order的拨拓。默認是 insert order，不需要做額外的操作逛球；而 access order千元，則需要在每次訪問 entry 后，調整 entry 的位置颤绕。HashMap 的設計者暴露出了一個 afterNodeAccess 回調幸海，以 LinkedHashMap#get(K) 方法為例，如果是 access order奥务，會執(zhí)行 afterNodeAccess(e)
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;
}
在 LinkedHashMap.afterNodeAccess 中物独，會判斷是否是 accessOrder，是的話把這個 entry 放到雙向鏈表的最后氯葬。至于為什么是最后挡篓，正常人應該是如 LRU cache 一樣放到最前，別問帚称，問就是最后官研。
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 還提供了一個 removeEldestEntry 回調闯睹，默認為 false戏羽，子類可以重寫來實現(xiàn)當是否刪除最 eldest 的 entry。這個回調會在 put/putAll 方法時觸發(fā)楼吃，何為 eldest 呢始花？對于 insert order，eldest 就是 put/putAll 加入的（最后一個）元素孩锡；對于 access order酷宵，eldest 就是 head 指針指向的元素（對應前面的移到最后）。
/**
* @param eldest The least recently inserted entry in the map, or if
* this is an access-ordered map, the least recently accessed
* entry. This is the entry that will be removed it this
* method returns {@code true}. If the map was empty prior
* to the {@code put} or {@code putAll} invocation resulting
* in this invocation, this will be the entry that was just
* inserted; in other words, if the map contains a single
* entry, the eldest entry is also the newest.
* @return {@code true} if the eldest entry should be removed
* from the map; {@code false} if it should be retained.
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
這種回調設計還有好幾個躬窜，下面是一些定義在 HashMap 中的回調
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
下面再看一下 access order 的驗證 demo浇垦，因為 "333" 被 "最近訪問" 了，所以他被移到了鏈表的最后荣挨。
public static void main(String[] args) {
LinkedHashMap<String, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put("111", "111");
map.put("333", "333");
map.put("222", "222");
System.out.println(map);
map.get("333");
System.out.println(map);
}
// output
{111=111, 333=333, 222=222}
{111=111, 222=222, 333=333}
4. 如何實現(xiàn) LRU cache
這是 leetcode 上的一個實現(xiàn)男韧，思路很明顯了
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.8F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
public boolean removeEldestEntry(Map.Entry<Integer, Integer> entry) {
return size() > capacity;
}
}
