Java集合框架10-LinkedHashMap詳解
LinkedHashMap繼承了HashMap，是Map接口的哈希表和鏈接列表實現。哈希表的功能通過繼承HashMap實現了。LinkedHashMap還維護着一個雙重鏈接鏈表。此鏈表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
數據結構
說明：LinkedHashMap會將元素串起來，形成一個雙鏈表結構。可以看到，其結構在HashMap結構上增加了鏈表結構。數據結構爲（數組 + 單鏈表 + 紅黑樹 + 雙鏈表），圖中的標號是結點插入的順序。
頂部註釋
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation.)
大意爲LinkedHashMap是Map的哈希表和鏈接列表的實現，具有可預知的迭代順序。LinkedHashMap和HashMap的不同之處在於它包含一個貫穿於所有entry的雙重鏈接列表。雙重鏈接列表定義了迭代順序，默認是插入順序。值得注意的是，如果一個key被重插入，插入順序不受影響。
源碼分析
類的繼承關係
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
從中我們可以瞭解到：
- LinkedHashMap<K,V>：HashMap是以key-value形式存儲數據的
- extends HashMap<K,V>：繼承了HashMap，哈希表部分的功能和HashMap相似。
- implements Map<K,V>：實現了Map。HashMap已經繼承了Map接口，爲什麼LinkedHashMap還要實現Map接口呢？仔細看過Java容器其他源碼的朋友會發現，不僅僅LinkedHashMap這樣做，其他實現類也經常這樣做。網上的一些看法是這樣做可以直觀地表達出LinkedHashMap實現了Map。如果大家有其他看法，歡迎留言。
類的屬性
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// LinkedHashMap的Entry繼承了HashMap的Node
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);
}
}
// 版本序列號
private static final long serialVersionUID = 3801124242820219131L;
// 雙向循環鏈表的頭結點
transient LinkedHashMap.Entry<K,V> head;
// 雙向循環鏈表的尾結點
transient LinkedHashMap.Entry<K,V> tail;
// 訪問順序。true代表按訪問順序迭代，false代表按插入順序迭代
final boolean accessOrder;
}
私有方法
linkNodeLast( LinkedHashMap.Entry<K,V> p)
/**
* 將指定entry插入到雙向鏈表末尾
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
//尾指針執行p
tail = p;
//如果舊的尾節點指向null，意味着雙向循環鏈表爲空，這時頭尾指針都要指向p
if (last == null)
head = p;
else {//否則將p插入到舊尾節點的後面
p.before = last;
last.after = p;
}
}
transferLinks( LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst)
// 將src替換爲dst
private void transferLinks(LinkedHashMap.Entry<K,V> src,
LinkedHashMap.Entry<K,V> dst) {
LinkedHashMap.Entry<K,V> b = dst.before = src.before;
LinkedHashMap.Entry<K,V> a = dst.after = src.after;
//如果src的前指針指向null，說明src爲頭節點，這時將dst替換爲頭節點即可
if (b == null)
head = dst;
else//否則，將dst的前指針指向的節點的後指針指向dst
b.after = dst;
//如果src的後指針指向null，說明src爲尾節點，這時將dst替換爲尾節點即可
if (a == null)
tail = dst;
else//否則，將dst的後指針指向的節點的前指針指向dst
a.before = dst;
}
重寫HashMap的方法
reinitialize()
//將linkedHashMap重置到初始化的默認狀態
void reinitialize() {
//重置哈希表
super.reinitialize();
//重置雙向循環鏈表
head = tail = null;
}
newNode( int hash, K key, V value, Node<K,V> e)
/**
* 創建一個普通entry，將entry插入到雙向循環鏈表的末尾,最後返回entry
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//創建一個entry
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
//將entry插入到雙向循環鏈表的末尾
linkNodeLast(p);
//返回entry
return p;
}
replacementNode( Node<K,V> p, Node<K,V> next)
/**
* 替換普通節點
*/
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
LinkedHashMap.Entry<K,V> t =
new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
newTreeNode( int hash, K key, V value, Node<K,V> next)
/**
* 創建一個樹的entry，將entry插入到雙向循環鏈表的末尾,最後返回entry
*/
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;
}
replacementTreeNode( Node<K,V> p, Node<K,V> next)
/**
* 替換樹節點
*/
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p;
TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next);
transferLinks(q, t);
return t;
}
afterNodeRemoval( Node<K,V> e)
/**
* 保證linkedHashMap刪除操作後哈希表與雙向循環鏈表的一致性
*/
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;
}
這個方法是用來在LinkedHashMap的哈希表中刪除一個鍵值對後同時將鍵值對從雙向循環鏈表中刪除，保證哈希表和雙向循環鏈表的一致性。
HashMap的源碼裏有這麼三個空方法：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
這三個方法表示在訪問、插入、刪除某個節點之後，進行一些處理，它們在LinkedHashMap都有重寫。LinkedHashMap正是通過重寫這三個方法來保證鏈表的插入、刪除的有序性。
afterNodeInsertion( boolean 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);
}
}
從代碼中可以看出，如果evict && (first = head) != null && removeEldestEntry(first)條件爲true，將刪除頭節點。看下removeEldestEntry方法的實現，發現永遠返回false。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
這意味着afterNodeInsertion這個方法什麼都做不了。那這個方法有什麼用？
如果重寫removeEldestEntry方法，就能定義是否刪除的規則，afterNodeInsertion就有用了。對removeEldestEntry方法的詳細解釋請往下看。
afterNodeAccess( Node<K,V> e)
/**
* 若迭代順序爲true，且指定參數節點e不是尾結點，把指定參數節點e移到末尾
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//若迭代順序爲true，且指定參數節點e不是尾結點
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;
}
}
internalWriteEntries( java.io.ObjectOutputStream s)
/**
* 寫入鍵值對到ObjectOutputStream中
*/
void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
s.writeObject(e.key);
s.writeObject(e.value);
}
}
構造方法
LinkedHashMap有五種構造方法：
- LinkedHashMap( int initialCapacity, float loadFactor)。使用指定的初始化容量initial capacity 和負載因子load factor構造一個空LinkedHashMap。
- LinkedHashMap( int initialCapacity)。使用指定的初始化容量initial capacity和默認負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空LinkedHashMap。
- LinkedHashMap()。使用指定的初始化容量（16）和默認負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空HashMap。
- LinkedHashMap(Map<? extends K, ? extends V> m)。使用指定Map m構造新的LinkedHashMap。使用指定的初始化容量（16）和默認負載因子DEFAULT_LOAD_FACTOR（0.75）。
- LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)。使用指定的初始化容量initial capacity 和負載因子load factor和迭代順序accessOrder構造一個空LinkedHashMap。
LinkedHashMap( int initialCapacity, float loadFactor)
/**
* 使用指定的初始化容量initial capacity 和負載因子load factor構造一個空LinkedHashMap
*
* @param initialCapacity 初始化容量
* @param loadFactor 負載因子
* @throws IllegalArgumentException 如果指定的初始化容量爲負數或者加載因子爲非正數。
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
//默認迭代順序爲插入順序
accessOrder = false;
}
LinkedHashMap( int initialCapacity)
/**
* 使用指定的初始化容量initial capacity和默認負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空LinkedHashMap
*
* @param initialCapacity 初始化容量
* @throws IllegalArgumentException 如果指定的初始化容量爲負數
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
//默認迭代順序爲插入順序
accessOrder = false;
}
LinkedHashMap()
/**
* 使用指定的初始化容量（16）和默認負載因子DEFAULT_LOAD_FACTOR（0.75）構造一個空HashMap
*/
public LinkedHashMap() {
super();
//默認迭代順序爲插入順序
accessOrder = false;
}
LinkedHashMap( Map<? extends K, ? extends V> m)
/**
* 使用指定Map m構造新的LinkedHashMap。使用指定的初始化容量（16）和默認負載因子DEFAULT_LOAD_FACTOR（0.75）
* @param m 指定的map
* @throws NullPointerException 如果指定的map是null
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
//默認迭代順序爲插入順序
accessOrder = false;
putMapEntries(m, false);
}
LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder)
/**
* 使用指定的初始化容量initial capacity 和負載因子load factor和迭代順序accessOrder構造一個空LinkedHashMap
*
* @param initialCapacity 初始化容量
* @param loadFactor 負載因子
* @param accessOrder 迭代順序
*
* @throws IllegalArgumentException 如果指定的初始化容量爲負數或者加載因子爲非正數。
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
//默認迭代順序爲插入順序
this.accessOrder = accessOrder;
}
常用方法
containsValue( Object value)
/**
* 如果linkedHashMap中的鍵值對有一對或多對的value爲參數value，返回true
*
* @param value 參數value
* @return 如果linkedHashMap中的鍵值對有一對或多對的value爲參數value，返回true
*/
public boolean containsValue(Object value) {
//遍歷雙向循環鏈表，如果有一對或多對的鍵值對value爲參數value，返回true
for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
//否則返回false
return false;
}
get( Object key)
/**
* 返回指定的key對應的entry的value，如果entry爲null或者value爲null，則返回null
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
//如果key對應的entry爲null，返回null
if ((e = getNode(hash(key), key)) == null)
return null;
//如果迭代順序爲按訪問順序迭代
if (accessOrder)
//將e插入雙向鏈表末尾
afterNodeAccess(e);
//返回value
return e.value;
}
getOrDefault( Object key, V defaultValue)
/**
* 通過key映射到對應entry，如果沒映射到則返回默認值defaultValue
*
* @return key映射到對應的entry，如果沒映射到則返回默認值defaultValue
*/
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
//如果key對應的entry爲null，返回defaultValue
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
//如果迭代順序爲按訪問順序迭代
if (accessOrder)
//將e插入雙向鏈表末尾
afterNodeAccess(e);
//返回value
return e.value;
}
clear()
/**
* 清空linkedHashMap。
*/
public void clear() {
//清空哈希表
super.clear();
//清空雙向循環鏈表
head = tail = null;
}
removeEldestEntry( Map.Entry<K,V> eldest)
/**
* 如果map應該刪除頭節點，返回true
*
* 這個方法在被put和putAll方法被調用，當向map中插入一個新的entry時被執行。
*
* 這個方法提供了當一個新的entry被添加到linkedHashMap中，刪除頭節點的機會。
*
* 這個方法是很有用的，可以通過刪除頭節點來減少內存消耗，避免溢出。
*
* 簡單的例子：這個方法的重寫將map的最大值設爲100，到100時，每次增一個entry，就刪除一次頭節點。
*
* private static final int MAX_ENTRIES = 100;
*
* protected boolean removeEldestEntry(Map.Entry eldest) {
* return size() > MAX_ENTRIES;//當map大小大於100時，返回true。意爲允許刪除頭節點
* }
*
* 這個方法一般不會直接修改map，而是通過返回true或者false來控制是否修改map。
*
* 這個方法僅僅返回false，這樣頭節點就永遠都不會被刪除了。
*
* @param eldest 頭節點
* @return 如果map應該刪除頭節點就返回true，否則返回false
*/
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
keySet()
/**
* 返回linkedHashMap中所有key的視圖。
* 改變linkedHashMap會影響到set，反之亦然。
* 如果當迭代器迭代set時，linkedHashMap被修改(除非是迭代器自己的remove()方法)，迭代器的結果是不確定的。
* set支持元素的刪除，通過Iterator.remove、Set.remove、removeAll、retainAll、clear操作刪除hashMap中對應的鍵值對。不支持add和addAll方法。
*
* @return 返回linkedHashMap中所有key的set視圖
*/
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new LinkedKeySet();
keySet = ks;
}
return ks;
}
final class LinkedKeySet extends AbstractSet<K> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<K> iterator() {
return new LinkedKeyIterator();
}
public final boolean contains(Object o) { return containsKey(o); }
public final boolean remove(Object key) {
return removeNode(hash(key), key, null, false, true) != null;
}
public final Spliterator<K> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED |
Spliterator.DISTINCT);
}
public final void forEach(Consumer<? super K> 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.key);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
values()
/**
* 返回linkedHashMap中所有value的collection視圖
* 改變linkedHashMap會改變collection，反之亦然。
* 如果當迭代器迭代collection時，linkedHashMap被修改（除非是迭代器自己的remove()方法），迭代器的結果是不確定的。
* collection支持元素的刪除，通過Iterator.remove、Collection.remove、removeAll、retainAll、clear操作刪除linkedHashMap中對應的鍵值對。不支持add和addAll方法。
*
* @return 返回linkedHashMap中所有key的collection視圖
*/
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new LinkedValues();
values = vs;
}
return vs;
}
final class LinkedValues extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { LinkedHashMap.this.clear(); }
public final Iterator<V> iterator() {
return new LinkedValueIterator();
}
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return Spliterators.spliterator(this, Spliterator.SIZED |
Spliterator.ORDERED);
}
public final void forEach(Consumer<? super 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.value);
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
entrySet()
/**
* 返回hashMap中所有鍵值對的set視圖
* 改變hashMap會影響到set，反之亦然。
* 如果當迭代器迭代set時，hashMap被修改(除非是迭代器自己的remove()方法)，迭代器的結果是不確定的。
* set支持元素的刪除，通過Iterator.remove、Set.remove、removeAll、retainAll、clear操作刪除hashMap中對應的鍵值對。不支持add和addAll方法。
*
* @return 返回hashMap中所有鍵值對的set視圖
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}
LinkedHashMap到這裏就看完了，LinkedHashMap和HashMap確實很相似，HashMap的特性LinkedHashMap都有，LinkedHashMap中的操作基本上都是爲了維護具有訪問順序的雙向循環鏈表。
總結
HashMap與LinkedHashMap比較
不同點
| 不同點 | HashMap | LinkedHashMap |
| 數據結構 | 數組+鏈表+紅黑樹 | 數組+鏈表+紅黑樹+雙向循環鏈表 |
| 是否有序 | 無序 | 有序 |
相同點
- 都是基於哈希表的實現。
- 存儲的是鍵值對映射。
- 都繼承了AbstractMap，實現了Map、Cloneable、Serializable。
- 它們的構造函數都一樣。
- 默認的容量大小是16，默認的加載因子是0.75。
- 都允許key和value爲null。
- 都是線程不安全的。