0. LinkedHashMap是什么
從類的注釋中可以知道LinkedHashMap有以下特點：
- 使用
HashTable和鏈表實現(xiàn)的，遍歷順序可預(yù)測的，Map接口的實現(xiàn)。 - 所有節(jié)點使用雙向鏈表鏈接
- 遍歷順序可以在初始化時指定，可以為插入順序或者訪問順序(LRU算法)
1. 實現(xiàn)的本質(zhì)
- 繼承
HashMap - 所有節(jié)點通過雙向鏈表鏈接
LinkedHashMap的節(jié)點結(jié)構(gòu)
/**
* 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);
}
}
2. 主要api解析
2.1 構(gòu)造函數(shù)
類中有一個字段accessOrder指定了遍歷模式：
-
true訪問順序，可以實現(xiàn)LRU算法 -
false插入順序
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
final boolean accessOrder;
public LinkedHashMap(int initialCapacity, float loadFactor)
public LinkedHashMap(int initialCapacity)
public LinkedHashMap()
public LinkedHashMap(Map<? extends K, ? extends V> m)
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
其中構(gòu)造方法均調(diào)用了super()，即HashMap類的構(gòu)造方法，accessOrder默認(rèn)為false
2.2 put方法
在LinkedHashMap中并沒有重寫put方法，所以使用的仍然是HashMap的put方法，參考源碼閱讀 - HashMap中3.2 put方法小節(jié)。
但是在putVal方法中添加的新節(jié)點是通過newNode newTreeNode方法生成的，LinkedHashMap重寫了這兩個方法：
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
linkNodeLast(p);
return p;
}
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
linkNodeLast(p);
return p;
}
// link at the end of list
//將節(jié)點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;
}
}
在putVal方法的最后調(diào)用了afterNodeInsertion方法，該方法在HashMap中是空實現(xiàn)，但是LinkedHashMap中實現(xiàn)了該方法：
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);
}
}
其中removeEldestEntry方法默認(rèn)返回false，注釋中說明可以自己重寫該方法達(dá)到緩存目的并給出了一個緩存100個記錄的例子：
/**
* Returns <tt>true</tt> if this map should remove its eldest entry.
* This method is invoked by <tt>put</tt> and <tt>putAll</tt> after
* inserting a new entry into the map. It provides the implementor
* with the opportunity to remove the eldest entry each time a new one
* is added. This is useful if the map represents a cache: it allows
* the map to reduce memory consumption by deleting stale entries.
*
* <p>Sample use: this override will allow the map to grow up to 100
* entries and then delete the eldest entry each time a new entry is
* added, maintaining a steady state of 100 entries.
* <pre>
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;
* }
* </pre>
*
* <p>This method typically does not modify the map in any way,
* instead allowing the map to modify itself as directed by its
* return value. It <i>is</i> permitted for this method to modify
* the map directly, but if it does so, it <i>must</i> return
* <tt>false</tt> (indicating that the map should not attempt any
* further modification). The effects of returning <tt>true</tt>
* after modifying the map from within this method are unspecified.
*
* <p>This implementation merely returns <tt>false</tt> (so that this
* map acts like a normal map - the eldest element is never removed).
*
* @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 <tt>true</tt>. If the map was empty prior
* to the <tt>put</tt> or <tt>putAll</tt> 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 <tt>true</tt> if the eldest entry should be removed
* from the map; <tt>false</tt> if it should be retained.
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
2.3 get方法
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*/
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;
}
get完之后，如果accessOrder為true，則會調(diào)用afterNodeAccess方法，將節(jié)點放到雙向鏈表的尾端，即最新訪問放到最后：
//將節(jié)點放到雙向鏈表的尾端
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
//p:當(dāng)前節(jié)點
//b:前一節(jié)點
//a:后一節(jié)點
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
//處理前節(jié)點的after
if (b == null)
head = a;
else
b.after = a;
//處理后節(jié)點的before
if (a != null)
a.before = b;
else
last = b;
//處理當(dāng)前節(jié)點的before和after
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
2.4 remove方法
同樣參考源碼閱讀 - HashMap中3.4 remove方法小節(jié)。刪除完之后調(diào)用afterNodeRemoval方法如下，處理前后節(jié)點的before和after引用的指向問題：
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
2.5 遍歷
/**
* Returns a {@link Set} view of the mappings contained in this map.
* The set is backed by the map, so changes to the map are
* reflected in the set, and vice-versa. If the map is modified
* while an iteration over the set is in progress (except through
* the iterator's own <tt>remove</tt> operation, or through the
* <tt>setValue</tt> operation on a map entry returned by the
* iterator) the results of the iteration are undefined. The set
* supports element removal, which removes the corresponding
* mapping from the map, via the <tt>Iterator.remove</tt>,
* <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
* <tt>clear</tt> operations. It does not support the
* <tt>add</tt> or <tt>addAll</tt> operations.
* Its {@link Spliterator} typically provides faster sequential
* performance but much poorer parallel performance than that of
* {@code HashMap}.
*
* @return a set view of the mappings contained in this map
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
其中LinkedEntrySet也是LinkedHashMap的內(nèi)部類，調(diào)用iterator方法返回LinkedEntryIterator對象：
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
在遍歷的時候是通過鏈表來進(jìn)行遍歷：
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;
}
3. 參考
- LinkedHashMap源碼build 1.8.0_121-b13版本
- Map 綜述（二）：徹頭徹尾理解 LinkedHashMap
