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;
}
}
