一庸追、LinkedHashMap的屬性
二、LinkedHashMap的構(gòu)造方法
三涝缝、LinkedHashMap的重要函數(shù)
1. afterNodeAccess函數(shù)
2. afterNodeInsertion函數(shù)
3. afterNodeRemoval函數(shù)
4. transferLinks函數(shù)
5. linkNodeLast函數(shù)
6. 其他方法
四扑庞、LinkedHashMap的迭代器
1. 基礎(chǔ)迭代器--LinkedHashIterator
2. 鍵迭代器--LinkedKeyIterator
3. 值迭代器--LinkedValueIterator
4. 結(jié)點(diǎn)迭代器--LinkedEntryIterator
LinkedHashMap<K,V>繼承HashMap<K,V>類，實(shí)現(xiàn)了 Map<K,V>接口拒逮。
LinkedHashMap是HashMap的子類罐氨，與HashMap有著同樣的存儲(chǔ)結(jié)構(gòu)，但它加入了一個(gè)雙向鏈表的頭結(jié)點(diǎn)滩援，將所有put到LinkedHashmap的節(jié)點(diǎn)一一串成了一個(gè)雙向循環(huán)鏈表栅隐，因此它保留了節(jié)點(diǎn)插入的順序，可以使節(jié)點(diǎn)的輸出順序與輸入順序相同玩徊。
LinkedHashMap可以用來(lái)實(shí)現(xiàn)LRU算法（這會(huì)在下面的源碼中進(jìn)行分析）租悄。
LinkedHashMap同樣是非線程安全的，只在單線程環(huán)境下使用恩袱。
1. LinkedHashMap的屬性
/**
* 靜態(tài)內(nèi)部類Entry表示雙向鏈表泣棋，繼承自HashMap的Node，在其基礎(chǔ)上加上了before和after兩個(gè)指針
* 雙向循環(huán)鏈表的頭結(jié)點(diǎn)畔塔，整個(gè)LinkedHashMap中只有一個(gè)header
* 它將哈希表中所有的Entry貫穿起來(lái)潭辈，header中不保存key-value對(duì)纪吮，只保存前后節(jié)點(diǎn)的引用
*/
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;
鏈表頭結(jié)點(diǎn) - transient LinkedHashMap.Entry<K,V> tail;
鏈表尾結(jié)點(diǎn) - final boolean accessOrder;
雙向鏈表中元素排序規(guī)則的標(biāo)志位；
false：表示按插入順序排序萎胰；true：表示按訪問(wèn)順序排序
2. LinkedHashMap的構(gòu)造方法
2.1 LinkedHashMap(int, float)型構(gòu)造函數(shù)
/**
* 總是會(huì)在構(gòu)造函數(shù)的第一行調(diào)用父類構(gòu)造函數(shù)碾盟，使用super關(guān)鍵字，
* accessOrder默認(rèn)為false技竟，access為true表示之后訪問(wèn)順序按照元素的訪問(wèn)順序進(jìn)行
* 即不按照之前的插入順序了，access為false表示按照插入順序訪問(wèn)熙尉。
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
2.2 LinkedHashMap(int)型構(gòu)造函數(shù)
/**
* 加載因子取默認(rèn)的0.75f
*/ public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
2.3 LinkedHashMap()型構(gòu)造函數(shù)
/**
* 加載因子取默認(rèn)的0.75f检痰，容量取默認(rèn)的16
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
2.4 LinkedHashMap(Map<? extends K, ? extends V>)型構(gòu)造函數(shù)
/**
* putMapEntries是調(diào)用到父類HashMap的構(gòu)造函數(shù)
*/
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
2.5 LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)型構(gòu)造函數(shù)
/**
* 可以指定accessOrder的值，從而控制訪問(wèn)順序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
3. LinkedHashMap的重要函數(shù)
- afterNodeAccess椎椰、afterNodeInsertion慨飘、afterNodeRemoval這三個(gè)方法都是重寫父類HashMap的方法瓤的。
3.1 afterNodeAccess函數(shù)
/**
* 把當(dāng)前節(jié)點(diǎn)e放到雙向鏈表尾部
*/
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
/* accessOrder就是我們前面說(shuō)的LRU控制圈膏，當(dāng)它為true本辐，同時(shí)e對(duì)象不是尾節(jié)點(diǎn)
（如果訪問(wèn)尾節(jié)點(diǎn)就不需要設(shè)置医增，該方法就是把節(jié)點(diǎn)放置到尾節(jié)點(diǎn)）
*/
if (accessOrder && (last = tail) != e) {
// 用a和b分別記錄該節(jié)點(diǎn)前面和后面的節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 釋放當(dāng)前節(jié)點(diǎn)與后節(jié)點(diǎn)的關(guān)系
p.after = null;
// 如果當(dāng)前節(jié)點(diǎn)的前節(jié)點(diǎn)是空
if (b == null)
// 那么頭節(jié)點(diǎn)就設(shè)置為a
head = a;
else
// 如果b不為null叶骨，那么b的后節(jié)點(diǎn)指向a
b.after = a;
// 如果a節(jié)點(diǎn)不為空
if (a != null)
// a的后節(jié)點(diǎn)指向b
a.before = b;
else
// 如果a為空忽刽，那么b就是尾節(jié)點(diǎn)
last = b;
// 如果尾節(jié)點(diǎn)為空
if (last == null)
// 那么p為頭節(jié)點(diǎn)
head = p;
else {
// 否則就把p放到雙向鏈表最尾處
p.before = last;
last.after = p;
}
// 設(shè)置尾節(jié)點(diǎn)為P
tail = p;
// LinkedHashMap對(duì)象操作次數(shù)+1
++modCount;
}
}
此函數(shù)在很多函數(shù)（如put）中都會(huì)被回調(diào)跪帝，LinkedHashMap重寫了HashMap中的此函數(shù)伞剑。若訪問(wèn)順序?yàn)閠rue黎泣，且訪問(wèn)的對(duì)象不是尾結(jié)點(diǎn)
訪問(wèn)結(jié)點(diǎn)3的前后狀態(tài)
從圖中可以看到抒倚，結(jié)點(diǎn)3鏈接到了尾結(jié)點(diǎn)后面
LinkedHashMap重寫了HashMap的get方法：
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder) // 如果啟用了LRU規(guī)則
afterNodeAccess(e); // 那么把該節(jié)點(diǎn)移到雙向鏈表最后面
return e.value;
}
- 注： LinkedHashMap壓根沒(méi)有重寫put方法含蓉，每次用LinkedHashMap的put方法的時(shí)候项郊，其實(shí)你調(diào)用的都是HashMap的put方法呆抑。但它也會(huì)執(zhí)行afterNodeAccess()方法鹊碍，因?yàn)檫@個(gè)方法HashMap就是存在的，但是沒(méi)有實(shí)現(xiàn)公罕，LinkedHashMap重寫了afterNodeAccess()這個(gè)方法楼眷。
3.2 afterNodeInsertion函數(shù)
/**
* 在哈希表中插入了一個(gè)新節(jié)點(diǎn)時(shí)調(diào)用的罐柳，它會(huì)把鏈表的頭節(jié)點(diǎn)刪除掉张吉，刪除的方式是通過(guò)調(diào)用HashMap的removeNode方法
*/
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);
}
}
3.3 afterNodeRemoval函數(shù)
/**
* 當(dāng)HashMap刪除一個(gè)鍵值對(duì)時(shí)調(diào)用的肮蛹，它會(huì)把在HashMap中刪除的那個(gè)鍵值對(duì)一并從鏈表中刪除伦忠，保證了哈希表和鏈表的一致性。
*/
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);
}
}
3.4 transferLinks函數(shù)
/**
* 用dst替換src
*/
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;
if (b == null)
head = dst;
else
b.after = dst;
if (a == null)
tail = dst;
else
a.before = dst;
}
使用結(jié)點(diǎn)7替換結(jié)點(diǎn)3
3.5 linkNodeLast函數(shù)
在看linkNodeLast函數(shù)之前先看看newNode和newTreeNode這兩個(gè)函數(shù)
3.5.1 newNode函數(shù)
/**
* 當(dāng)桶中結(jié)點(diǎn)類型為HashMap.Node類型時(shí)未桥，調(diào)用此函數(shù)
*/
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
// 生成Node結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<K,V>(hash, key, value, e);
// 將該結(jié)點(diǎn)插入雙鏈表末尾
linkNodeLast(p);
return p;
}
3.5.2 newTreeNode函數(shù)
/**
* 當(dāng)桶中結(jié)點(diǎn)類型為HashMap.TreeNode時(shí)冬耿，調(diào)用此函數(shù)
*/
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
// 生成TreeNode結(jié)點(diǎn)
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
// 將該結(jié)點(diǎn)插入雙鏈表末尾
linkNodeLast(p);
return p;
}
3.5.3 linkNodeLast函數(shù)
/**
* 把新加的節(jié)點(diǎn)放在鏈表的最后面
*/
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 將tail給臨時(shí)變量last
LinkedHashMap.Entry<K,V> last = tail;
// 把new的Entry給tail
tail = p;
// 若沒(méi)有l(wèi)ast亦镶，說(shuō)明p是第一個(gè)節(jié)點(diǎn)爱咬，head=p
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
3.6 其他方法
- internalWriteEntries方法
/**
* 該方法也是重寫父類HashMap的方法绊起，也是為了LinkedHashMap鍵和值被序列化的存儲(chǔ)順序
*/
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);
}
}
其他方法就不一一介紹的官方API中都有詳細(xì)的說(shuō)明虱歪。
4. LinkedHashMap的迭代器
4.1基礎(chǔ)迭代器--LinkedHashIterator
為抽象類，用于對(duì)LinkedHashMap進(jìn)行迭代
/**
* LinkedHashIterator是LinkedHashMap的迭代器师枣，為抽象類践美，用于對(duì)LinkedHashMap進(jìn)行迭代
*/
abstract class LinkedHashIterator {
// 下一個(gè)結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> next;
// 當(dāng)前結(jié)點(diǎn)
LinkedHashMap.Entry<K,V> current;
// 期望的修改次數(shù)
int expectedModCount;
LinkedHashIterator() {
// next賦值為頭結(jié)點(diǎn)
next = head;
// 賦值修改次數(shù)
expectedModCount = modCount;
// 當(dāng)前結(jié)點(diǎn)賦值為空
current = null;
}
// 是否存在下一個(gè)結(jié)點(diǎn)
public final boolean hasNext() {
return next != null;
}
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
// 檢查是否存在結(jié)構(gòu)性修改
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// 當(dāng)前結(jié)點(diǎn)是否為空
if (e == null)
throw new NoSuchElementException();
// 賦值當(dāng)前節(jié)點(diǎn)
current = e;
// 賦值下一個(gè)結(jié)點(diǎn)
next = e.after;
return e;
}
public final void remove() {
// 保存當(dāng)前結(jié)點(diǎn)
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
// 移除結(jié)點(diǎn)
removeNode(hash(key), key, null, false, false);
// 更新最新修改數(shù)
expectedModCount = modCount;
}
}
4.2 鍵迭代器--LinkedKeyIterator
繼承自LinkedHashIterator，實(shí)現(xiàn)了Iterator接口玫膀，對(duì)LinkedHashMap中的鍵進(jìn)行迭代
final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator<K> {
public final K next() { return nextNode().getKey(); }
}
4.3 值迭代器--LinkedValueIterator
繼承自LinkedHashIterator帖旨，實(shí)現(xiàn)了Iterator接口灵妨，對(duì)LinkedHashMap中的值進(jìn)行迭代
final class LinkedValueIterator extends LinkedHashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
4.4 結(jié)點(diǎn)迭代器--LinkedEntryIterator
繼承自LinkedHashIterator货抄，實(shí)現(xiàn)了Iterator接口朱转，對(duì)LinkedHashMap中的結(jié)點(diǎn)進(jìn)行迭代
final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
