移步數(shù)據(jù)結(jié)構(gòu)--容器匯總（java & Android）
分析 LinkedHashMap的源碼：
- LinkedHashMap 與 HashMap 的關(guān)系
- LinkedHashMap 雙向鏈表的構(gòu)建過程
- LinkedHashMap 刪除節(jié)點(diǎn)的過程
- LinkedHashMap 如何維持訪問順序
- LinkedHashMap - LRU (Least Recently Used) 最簡(jiǎn)單的構(gòu)建方式
一蔓肯、 LinkedHashMap 與 HashMap 的關(guān)系
LinkedHashMap 的體系圖:
image
- LinkedHashMap 直接繼承自HashMap ，這也就說明了上文中我們說到的 HashMap 一切重要的概念 LinkedHashMap 都是擁有的振乏，這就包括了蔗包，hash 算法定位 hash 桶位置，哈希表由數(shù)組和單鏈表構(gòu)成慧邮，并且當(dāng)單鏈表長(zhǎng)度超過 8 的時(shí)候轉(zhuǎn)化為紅黑樹调限，擴(kuò)容體系，這一切都跟 HashMap 一樣误澳。
- 除了這么多關(guān)鍵的相同點(diǎn)以外耻矮，LinkedHashMap 比 HashMap 更加強(qiáng)大，這體現(xiàn)在：
- LinkedHashMap 內(nèi)部維護(hù)了一個(gè)雙向鏈表忆谓，解決了 HashMap 不能隨時(shí)保持遍歷順序和插入順序一致的問題
- LinkedHashMap 元素的訪問順序也提供了相關(guān)支持裆装，也就是我們常說的 LRU（最近最少使用）原則。
二陪毡、 LinkedHashMap 雙向鏈表的構(gòu)建過程
image
- 假設(shè)圖片中紅黃箭頭代表元素添加順序米母，藍(lán)箭頭代表單鏈表各個(gè)元素的存儲(chǔ)順序。head 表示雙向鏈表頭部毡琉，tail 代表雙向鏈表尾部
- HashMap 源碼的時(shí)候我們有一張示意圖铁瞒，說明了 HashMap 的存儲(chǔ)結(jié)構(gòu)為，數(shù)組 + 單鏈表 + 紅黑樹桅滋，從上邊的圖片我們也可以看出 LinkedHashMap 底層的存儲(chǔ)結(jié)構(gòu)并沒有發(fā)生變化慧耍。
- 唯一變化的是使用雙向鏈表（圖中紅黃箭頭部分）記錄了元素的添加順序，我們知道 HashMap 中的 Node 節(jié)點(diǎn)只有 next 指針丐谋，對(duì)于雙向鏈表而言只有 next 指針是不夠的芍碧，所以 LinkedHashMap 對(duì)于 Node 節(jié)點(diǎn)進(jì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);
}
}
- LinkedHashMap 基本存儲(chǔ)單元 Entry<K,V> 繼承自 HashMap.Node<K,V>,并在此基礎(chǔ)上添加了 before 和 after 這兩個(gè)指針變量。
- 這 before 變量在每次添加元素的時(shí)候?qū)?huì)鏈接上一次添加的元素号俐，而上一次添加的元素的 after 變量將指向該次添加的元素泌豆，來形成雙向鏈接。
- 值得注意的是 LinkedHashMap 并沒有覆寫任何關(guān)于 HashMap put 方法吏饿。所以調(diào)用 LinkedHashMap 的 put 方法實(shí)際上調(diào)用了父類 HashMap 的方法踪危。為了方便理解我們這里放一下 HashMap 的 putVal 方法蔬浙。
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 {// 發(fā)生 hash 碰撞了
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){....}
else {
//hash 值計(jì)算出的數(shù)組索引相同，但 key 并不同的時(shí)候 循環(huán)整個(gè)單鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍歷到尾部
// 創(chuàng)建新的節(jié)點(diǎn)贞远，拼接到鏈表尾部
p.next = newNode(hash, key, value, null);
....
break;
}
//如果遍歷過程中找到鏈表中有個(gè)節(jié)點(diǎn)的 key 與 當(dāng)前要插入元素的 key 相同畴博，
//此時(shí) e 所指的節(jié)點(diǎn)為需要替換 Value 的節(jié)點(diǎn)，并結(jié)束循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//移動(dòng)指針
p = e;
}
}
//如果循環(huán)完后 e!=null 代表需要替換e所指節(jié)點(diǎn) Value
if (e != null) {
V oldValue = e.value//保存原來的 Value 作為返回值
// onlyIfAbsent 一般為 false 所以替換原來的 Value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//該方法在 LinkedHashMap 中的實(shí)現(xiàn)稍后說明
return oldValue;
}
}
//操作數(shù)增加
++modCount;
//如果 size 大于擴(kuò)容閾值則表示需要擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可以看出每次添加新節(jié)點(diǎn)的時(shí)候?qū)嶋H上是調(diào)用 newNode 方法生成了一個(gè)新的節(jié)點(diǎn)蓝仲，放到指定 hash 桶中,但是很明顯俱病，HashMap 中 newNode 方法無法完成上述所講的雙向鏈表節(jié)點(diǎn)的間的關(guān)系，所以 LinkedHashMap 復(fù)寫了該方法：
// HashMap newNode 中實(shí)現(xiàn)
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// LinkedHashMap newNode 的實(shí)現(xiàn)
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);
// 將 Entry 接在雙向鏈表的尾部
linkNodeLast(p);
return p;
}
可以看出雙向鏈表的操作一定在 linkNodeLast方法中實(shí)現(xiàn)：
/**
* 該引用始終指向雙向鏈表的頭部
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 該引用始終指向雙向鏈表的尾部
*/
transient LinkedHashMap.Entry<K,V> tail;
// newNode 中新節(jié)點(diǎn)袱结，放到雙向鏈表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 添加元素之前雙向鏈表尾部節(jié)點(diǎn)
LinkedHashMap.Entry<K,V> last = tail;
// tail 指向新添加的節(jié)點(diǎn)
tail = p;
//如果之前 tail 指向 null 那么集合為空新添加的節(jié)點(diǎn) head = tail = p
if (last == null)
head = p;
else {
// 否則將新節(jié)點(diǎn)的 before 引用指向之前當(dāng)前鏈表尾部
p.before = last;
// 當(dāng)前鏈表尾部節(jié)點(diǎn)的 after 指向新節(jié)點(diǎn)
last.after = p;
}
}
image
LinkedHashMap 鏈表創(chuàng)建步驟亮隙，可用上圖幾個(gè)步驟來描述，藍(lán)色部分是 HashMap 的方法擎勘，而橙色部分為 LinkedHashMap 獨(dú)有的方法咱揍。
- 當(dāng)我們創(chuàng)建一個(gè)新節(jié)點(diǎn)之后，通過linkNodeLast方法棚饵，將新的節(jié)點(diǎn)與之前雙向鏈表的最后一個(gè)節(jié)點(diǎn)（tail）建立關(guān)系煤裙，在這部操作中我們?nèi)圆恢肋@個(gè)節(jié)點(diǎn)究竟儲(chǔ)存在哈希表表的何處，但是無論他被放到什么地方噪漾，節(jié)點(diǎn)之間的關(guān)系都會(huì)加入雙向鏈表硼砰。如上述圖中節(jié)點(diǎn) 3 和節(jié)點(diǎn) 4 那樣彼此擁有指向?qū)Ψ降囊茫@么做就能確保了雙向鏈表的元素之間的關(guān)系即為添加元素的順序欣硼。
三题翰、LinkedHashMap 刪除節(jié)點(diǎn)的操作
如插入操作一樣，LinkedHashMap 沒有重寫的 remove 方法诈胜，使用的仍然是 HashMap 中的代碼豹障，我們先來回憶一下 HashMap 中的 remove 方法：
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// HashMap 中實(shí)現(xiàn)
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
//判斷哈希表是否為空，長(zhǎng)度是否大于0 對(duì)應(yīng)的位置上是否有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
// node 用來存放要移除的節(jié)點(diǎn)焦匈， e 表示下個(gè)節(jié)點(diǎn) k 血公，v 每個(gè)節(jié)點(diǎn)的鍵值
Node<K,V> node = null, e; K k; V v;
//如果第一個(gè)節(jié)點(diǎn)就是我們要找的直接賦值給 node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
// 遍歷紅黑樹找到對(duì)應(yīng)的節(jié)點(diǎn)
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
//遍歷對(duì)應(yīng)的鏈表找到對(duì)應(yīng)的節(jié)點(diǎn)
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
// 如果找到了節(jié)點(diǎn)
// !matchValue 是否不刪除節(jié)點(diǎn)
// (v = node.value) == value ||
(value != null && value.equals(v))) 節(jié)點(diǎn)值是否相同，
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//刪除節(jié)點(diǎn)
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);// 注意這個(gè)方法 在 Hash表的刪除操作完成調(diào)用該方法
return node;
}
}
return null;
}
LinkedHashMap 通過調(diào)用父類的 HashMap 的 remove 方法將 Hash 表的中節(jié)點(diǎn)的刪除操作完成即：
- 獲取對(duì)應(yīng) key 的哈希值 hash(key)缓熟，定位對(duì)應(yīng)的哈希桶的位置
- 遍歷對(duì)應(yīng)的哈希桶中的單鏈表或者紅黑樹找到對(duì)應(yīng) key 相同的節(jié)點(diǎn)累魔，在最后刪除，并返回原來的節(jié)點(diǎn)够滑。
對(duì)于 afterNodeRemoval（node） HashMap 中是空實(shí)現(xiàn)垦写，而該方法，正是 LinkedHashMap 刪除對(duì)應(yīng)節(jié)點(diǎn)在雙向鏈表中的關(guān)系的操作：
// 從雙向鏈表中刪除對(duì)應(yīng)的節(jié)點(diǎn) e 為已經(jīng)刪除的節(jié)點(diǎn)
void afterNodeRemoval(Node<K,V> e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 將 p 節(jié)點(diǎn)的前后指針引用置為 null 便于內(nèi)存釋放
p.before = p.after = null;
// p.before 為 null彰触，表明 p 是頭節(jié)點(diǎn)
if (b == null)
head = a;
else//否則將 p 的前驅(qū)節(jié)點(diǎn)連接到 p 的后驅(qū)節(jié)點(diǎn)
b.after = a;
// a 為 null梯投，表明 p 是尾節(jié)點(diǎn)
if (a == null)
tail = b;
else //否則將 a 的前驅(qū)節(jié)點(diǎn)連接到 b
a.before = b;
}
因此 LinkedHashMap 節(jié)點(diǎn)刪除方式如下圖步驟一樣：
image
四、 LinkedHashMap 維護(hù)節(jié)點(diǎn)訪問順序
LinkedHashMap 與 HashMap 添加和刪除元素的不同，可以看出除了維護(hù) Hash表中元素的關(guān)系以外分蓖，LinkedHashMap 還在添加和刪除元素的時(shí)候維護(hù)著一個(gè)雙向鏈表吮龄。那么這個(gè)雙向鏈表究竟有何用呢？我們來看下邊這個(gè)例子咆疗，我們對(duì)比一下在相同元素添加順序的時(shí)候，遍歷 Map 得到的結(jié)果：
//Map<String, Integer> map = new HashMap<>();
Map<String, Integer> map = new LinkedHashMap<>();
// 使用三個(gè)參數(shù)的構(gòu)造法方法來指定 accessOrder 參數(shù)的值
//Map<String, Integer> map = new LinkedHashMap<>(10,0.75f,true);
map.put("老大", 1);
map.put("老二", 2);
map.put("老三", 3);
map.put("老四", 4);
Set<Map.Entry<String, Integer>> entrySet = map.entrySet();
Iterator iter1 = entrySet.iterator();
while (iter1.hasNext()) {
Map.Entry entry = (Map.Entry) iter1.next();
System.out.print("key: " + entry.getKey() + " ");
System.out.println("value: " + entry.getValue());
}
System.out.println("老三的值為：" + map.get("老三"));
System.out.println("老大的值為：" + map.put("老大",1000));
Iterator iter2 = entrySet.iterator();
while (iter2.hasNext()) {
// 遍歷時(shí)母债，需先獲取entry午磁，再分別獲取key、value
Map.Entry entry = (Map.Entry) iter2.next();
System.out.print("key: " + entry.getKey() + " ");
System.out.println("value: " + entry.getValue());
}
/*** HashMap 遍歷結(jié)果*/
key: 老二 value: 2
key: 老四 value: 4
key: 老三 value: 3
key: 老大 value: 1
老三的值為：3
老大的值為：1
key: 老二 value: 2
key: 老四 value: 4
key: 老三 value: 3
key: 老大 value: 1000
/*** LinkedHashMap 遍歷結(jié)果*/
key: 老大 value: 1
key: 老二 value: 2
key: 老三 value: 3
key: 老四 value: 4
老三的值為：3
老大的值為：1
key: 老大 value: 1000
key: 老二 value: 2
key: 老三 value: 3
key: 老四 value: 4
由上述方法結(jié)果可以看出：
- HashMap 的遍歷結(jié)果是跟添加順序并無關(guān)系
- LinkedHashMap 的遍歷結(jié)果就是添加順序
這就是雙向鏈表的作用毡们。雙向鏈表能做的不僅僅是這些迅皇，在介紹雙向鏈表維護(hù)訪問順序前我們看來看一個(gè)重要的參數(shù):
final boolean accessOrder;// 是否維護(hù)雙向鏈表中的元素訪問順序
該方法隨 LinkedHashMap 構(gòu)造參數(shù)初始化，accessOrder 默認(rèn)值為 false衙熔，我們可以通過三個(gè)參數(shù)構(gòu)造方法指定該參數(shù)的值登颓，參數(shù)定義為 final 說明外部不能改變。
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
//可以指定 LinkedHashMap 雙向鏈表維護(hù)節(jié)點(diǎn)訪問順序的構(gòu)造參數(shù)
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
//第一次遍歷
key: 老大 value: 1
key: 老二 value: 2
key: 老三 value: 3
key: 老四 value: 4
老三的值為：3
老大的值為：1
//第二次遍歷
key: 老二 value: 2
key: 老四 value: 4
key: 老三 value: 3
key: 老大 value: 1000
- 可以看出當(dāng)我們使用 access 為 true 后红氯，我們?cè)L問元素的順序?qū)?huì)在下次遍歷的時(shí)候體現(xiàn)框咙，最后訪問的元素將最后獲得。
- 其實(shí)這一切在 HashMap 源碼中也早有伏筆, 還記得我們在每次 putVal/get/repalce 最后都有一個(gè) void afterNodeAccess(Node<K,V> e) 方法痢甘，該方法在 HashMap 中是空實(shí)現(xiàn)喇嘱，但是在 LinkedHasMap 中該后置方法，將作為維護(hù)節(jié)點(diǎn)訪問順序的重要方法
//將被訪問節(jié)點(diǎn)移動(dòng)到鏈表最后
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;
//訪問節(jié)點(diǎn)的后驅(qū)置為 null
p.after = null;
//如訪問節(jié)點(diǎn)的前驅(qū)為 null 則說明 p = head
if (b == null)
head = a;
else
b.after = a;
//如果 p 不為尾節(jié)點(diǎn) 那么將 a 的前驅(qū)設(shè)置為 b
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;// 將 p 接在雙向鏈表的最后
++modCount;
}
}
我們以下圖舉例看下整個(gè) afterNodeAccess 過程是是怎么樣的塞栅，比如我們?cè)摯尾僮髟L問的是 13 這個(gè)節(jié)點(diǎn)者铜，而 14 是其后驅(qū)，11 是其前驅(qū)放椰，且 tail = 14 作烟。在通過 get 訪問 13 節(jié)點(diǎn)后， 13變成了 tail 節(jié)點(diǎn)砾医，而14變成了其前驅(qū)節(jié)點(diǎn)拿撩，相應(yīng)的 14的前驅(qū)變成 11 ，11的后驅(qū)變成了14藻烤， 14的后驅(qū)變成了13.
image
- 由此我們得知绷雏，LinkedHashMap 通過afterNodeAccess 這個(gè)后置操作，可以在 accessOrde = true 的時(shí)候怖亭，使雙向鏈表維護(hù)哈希表中元素的訪問順序涎显。
// HashIterator nextNode 方法
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();
//遍歷 table 尋找下個(gè)存有元素的 hash桶
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
// LinkedHashIterator nextNode 方法
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;
//直接指向了當(dāng)前節(jié)點(diǎn)的 after 后驅(qū)節(jié)點(diǎn)
next = e.after;
return e;
}
更為明顯的我們可以查看兩者的 containsValue 方法：
//LinkedHashMap 中 containsValue 的實(shí)現(xiàn)
public boolean containsValue(Object value) {
// 直接遍歷雙向鏈表去尋找對(duì)應(yīng)的節(jié)點(diǎn)
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;
}
return false;
}
//HashMap 中 containsValue 的實(shí)現(xiàn)
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//遍歷 哈希桶索引
for (int i = 0; i < tab.length; ++i)
//遍歷哈希桶中鏈表或者紅黑樹
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
五、 Java 中最簡(jiǎn)單的 LRU 構(gòu)建方式
- LRU 是 Least Recently Used 的簡(jiǎn)稱兴猩，即近期最少使用
- 相信做 Android 的同學(xué)一定知道 LruCache 這個(gè)東西, Glide 的三級(jí)緩存中內(nèi)存緩存中也使用了這個(gè) LruCache 類期吓。
LRU 算法實(shí)現(xiàn)的關(guān)鍵就像它名字一樣，當(dāng)達(dá)到預(yù)定閾值的時(shí)候，這個(gè)閾值可能是內(nèi)存不足讨勤，或者容量達(dá)到最大箭跳，找到最近最少使用的存儲(chǔ)元素進(jìn)行移除，保證新添加的元素能夠保存到集合中潭千。
- 下面我們來講解下谱姓，Java 中 LRU 算法的最簡(jiǎn)單的實(shí)現(xiàn)。
- 我們還記得在每次調(diào)用 HashMap 的 putVal 方法添加完元素后還有個(gè)后置操作刨晴，void afterNodeInsertion(boolean evict) { } 就是這個(gè)方法屉来。
LinkedHashMap 重寫了此方法：
// HashMap 中 putVal 方法實(shí)現(xiàn) evict 傳遞的 true，表示表處于創(chuàng)建模式狈癞。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) { .... }
//evict 由上述說明大部分情況下都傳 true 表示表處于創(chuàng)建模式
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
//由于 evict = true 那么當(dāng)鏈表不為空的時(shí)候 且 removeEldestEntry(first) 返回 true 的時(shí)候進(jìn)入if 內(nèi)部
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);//移除雙向鏈表中處于 head 的節(jié)點(diǎn)
}
}
//LinkedHashMap 默認(rèn)返回 false 則不刪除節(jié)點(diǎn)茄靠。 返回 true 雙向鏈表中處于 head 的節(jié)點(diǎn)
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
- 由上述源碼可以看出，如果如果 removeEldestEntry(Map.Entry<K,V> eldest) 方法返回值為 true 的時(shí)候蝶桶，當(dāng)我們添加一個(gè)新的元素之后慨绳，afterNodeInsertion這個(gè)后置操作，將會(huì)刪除雙向鏈表最初的節(jié)點(diǎn)真竖，也就是 head 節(jié)點(diǎn)脐雪。
- 那么我們就可以從 removeEldestEntry 方法入手來構(gòu)建我們的 LruCache 。
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_NODE_NUM = 2<<4;
private int limit;
public LruCache() {
this(MAX_NODE_NUM);
}
public LruCache(int limit) {
super(limit, 0.75f, true);
this.limit = limit;
}
public V putValue(K key, V val) {
return put(key, val);
}
public V getValue(K key) {
return get(key);
}
/**
* 判斷存儲(chǔ)元素個(gè)數(shù)是否預(yù)定閾值
* @return 超限返回 true恢共，否則返回 false
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit;
}
}
- 我們構(gòu)建了一個(gè) LruCache 類喂江， 他繼承自 LinkedHashMap 在構(gòu)建的時(shí)候，調(diào)用了 LinkedHashMap 的三個(gè)參數(shù)的構(gòu)造方法且 accessOrder 傳入 true旁振，并覆寫了 removeEldestEntry 方法获询，當(dāng) Map 中的節(jié)點(diǎn)個(gè)數(shù)超過我們預(yù)定的閾值時(shí)候在 putValue 將會(huì)執(zhí)行 afterNodeInsertion 刪除最近沒有訪問的元素。
- 測(cè)試一下
//構(gòu)建一個(gè)閾值為 3 的 LruCache 類
LruCache<String,Integer> lruCache = new LruCache<>(3);
lruCache.putValue("老大", 1);
lruCache.putValue("老二", 2);
lruCache.putValue("老三", 3);
lruCache.getValue("老大");
//超過指定 閾值 3 再次添加元素的 將會(huì)刪除最近最少訪問的節(jié)點(diǎn)
lruCache.putValue("老四", 4);
System.out.println("lruCache = " + lruCache);
運(yùn)行結(jié)果當(dāng)然是刪除 key 為 "老二" 的節(jié)點(diǎn)：
lruCache = {老三=3, 老大=1, 老四=4}
六拐袜、 總結(jié)
本文并沒有從以往的增刪改查四種操作上去分析 LinkedHashMap 的源碼吉嚣，而是通過 LinkedHashMap 中不同于 HashMap 的幾大特點(diǎn)來展開分析。
- LinkedHashMap 擁有與 HashMap 相同的底層哈希表結(jié)構(gòu)蹬铺，即數(shù)組 + 單鏈表 + 紅黑樹尝哆，也擁有相同的擴(kuò)容機(jī)制。
- LinkedHashMap 相比 HashMap 的拉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)甜攀，內(nèi)部額外通過 Entry 維護(hù)了一個(gè)雙向鏈表秋泄。
- HashMap 元素的遍歷順序不一定與元素的插入順序相同，而 LinkedHashMap 則通過遍歷雙向鏈表來獲取元素规阀，所以遍歷順序在一定條件下等于插入順序恒序。
- LinkedHashMap 可以通過構(gòu)造參數(shù) accessOrder 來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置。
LinkedHashMap 可以通過構(gòu)造參數(shù) accessOrder 來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置谁撼。
備注：
- 每次添加新節(jié)點(diǎn)的時(shí)候?qū)嶋H上是調(diào)用 newNode 方法生成了一個(gè)新的節(jié)點(diǎn)歧胁，LinkedHashMap 復(fù)寫了該方法，雙向鏈表的操作一定在linkNodeLast方法中實(shí)現(xiàn)：將新的節(jié)點(diǎn)與之前雙向鏈表的最后一個(gè)節(jié)點(diǎn)（tail）建立關(guān)系，彼此擁有指向?qū)Ψ降囊煤拔。@么做就能確保了雙向鏈表的元素之間的關(guān)系即為添加元素的順序屠缭。
- LinkedHashMap 刪除節(jié)點(diǎn)的操作，對(duì)于 afterNodeRemoval（node） HashMap 中是空實(shí)現(xiàn)崭参，而該方法呵曹，正是 LinkedHashMap 刪除對(duì)應(yīng)節(jié)點(diǎn)在雙向鏈表中的關(guān)系的操作
- LinkedHashMap 與 HashMap 添加和刪除元素的不同，可以看出除了維護(hù) Hash表中元素的關(guān)系以外何暮，LinkedHashMap 還在添加和刪除元素的時(shí)候維護(hù)著一個(gè)雙向鏈表逢并。
- 該方法隨 LinkedHashMap 構(gòu)造參數(shù)初始化，accessOrder 默認(rèn)值為 false郭卫。--LinkedHashMap 通過afterNodeAccess 這個(gè)后置操作，可以在 accessOrde = true 的時(shí)候背稼，使雙向鏈表維護(hù)哈希表中元素的訪問順序贰军。
- LinkedHashMap 的迭代器，由于有雙向鏈表的存在蟹肘，它相比 HashMap 遍歷節(jié)點(diǎn)的方式更為高效--直接指向了當(dāng)前節(jié)點(diǎn)的 after 后驅(qū)節(jié)點(diǎn)
