本文主要從如下幾點學(xué)習(xí)LinkedHashMap
- LinkedHashMap是啥
- 代碼實操
- 原理分析
- 圖的形式展示雙向列表
LinkedHashMap是啥
繼承 HashMap實現(xiàn)了Map接口的散列表伐厌，HashMap本身是數(shù)組加單向鏈表
數(shù)據(jù)結(jié)構(gòu)：HashMap+雙向鏈表英上；HashMap的數(shù)據(jù)結(jié)構(gòu)是（數(shù)組+單向鏈表+（紅黑樹））
是根據(jù)插入或者訪問順序?qū)崿F(xiàn)有序輸出的HashMap趴酣，線程不安全的，允許key為null钻趋，value為null
代碼實操
-
put 张惹、get旺坠、forEach
LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>(); linkedMap.put(1, "index1"); linkedMap.put(3, "index3"); linkedMap.put(5, "index5"); linkedMap.put(4, "index4"); System.out.println("key == 3" + linkedMap.get(3)); linkedMap.forEach((k, v) -> { System.out.println("k == " + k + ", v == " + v); }); // 運行結(jié)果 key == 3 index3 k == 1, v == index1 k == 3, v == index3 k == 5, v == index5 k == 4, v == index4 // 構(gòu)造函數(shù) 打開按訪問順序排列 LinkedHashMap<Integer, String> linkedMap = new LinkedHashMap<>(5,0.75f,true); linkedMap.put(1, "index1"); linkedMap.put(3, "index3"); linkedMap.put(5, "index5"); linkedMap.put(4, "index4"); System.out.println("key == 3" + linkedMap.get(3)); linkedMap.forEach((k, v) -> { System.out.println("k == " + k + ", v == " + v); }); // 運行結(jié)果為 key == 3 index3 k == 1, v == index1 k == 5, v == index5 k == 4, v == index4 k == 3, v == index3
原理分析
幾個全局變量的解釋
transient LinkedHashMapEntry<K,V> head;
- 是雙向列表的頭節(jié)點堂淡，指向雙向列表的頭節(jié)點。
transient LinkedHashMapEntry<K,V> tail;
- 是雙向列表的尾節(jié)點逊谋，指向雙向列表的尾節(jié)點擂达。
final boolean accessOrder;
- accessOrder默認(rèn)在LinkedHashMap的構(gòu)造函數(shù)中賦值為false
- 如果為false，那么在迭代輸出節(jié)點的時候胶滋，會按照插入的順序進(jìn)行輸出
- 如果為true（使用了這個 new LinkedHashMap<>(5,0.75f,true) 構(gòu)造函數(shù)創(chuàng)建LinkedHashMap）板鬓，在迭代的時候，會按照節(jié)點的訪問順序輸出節(jié)點镀钓，最近使用的放在雙向列表的尾部穗熬。
- 為true的話镀迂，可以符合LRU算法的特性丁溅。
LinkedHashMapEntry的介紹
繼承至HashMap.Node，具有了單向鏈表的功能探遵。
-
比HashMap的Node多了 befor和after這兩個變量窟赏，這兩個變量是用來維護(hù)LinkedHashMap的雙向列表妓柜。
static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> { LinkedHashMapEntry<K,V> before, after; LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } }
LinkedHashMap的構(gòu)造函數(shù)介紹
-
構(gòu)造函數(shù)如下
//常規(guī)用法 public LinkedHashMap() { super(); accessOrder = false; } //指定了初始化時數(shù)組的容量 public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } //指定了初始化時容量和加載因子 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } //指定了容量、加載因子和迭代輸出時的順序 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } // 采用一個Map來構(gòu)造 public LinkedHashMap(Map<? extends K, ? extends V> m) { super(); accessOrder = false; //批量插入 putMapEntries(m, false); }
putI()方法的源碼的分析
LinkedHashMap中沒有重寫put方法涯穷，但是在HashMap進(jìn)行put操作的時候棍掐，有如下兩點判斷
- 當(dāng)key計算出來的位置，沒有數(shù)據(jù)存在拷况，會調(diào)用newNode()方法作煌。
- 該方法，在LinkedHashMap被重寫了
- 當(dāng)LinkedHashMap調(diào)用put時赚瘦，此時用到了多態(tài)粟誓，會調(diào)用LinkedHashMap中的newNode()方法
- 當(dāng)key計算出來的位置，有數(shù)據(jù)存在起意；
- 當(dāng)key完全相同鹰服，進(jìn)行數(shù)據(jù)的賦值，然后進(jìn)行數(shù)據(jù)的替換揽咕。
- 在數(shù)據(jù)進(jìn)行替換的時候悲酷，調(diào)用了afterNodeAccess(e)方法
- 該方法在LinkedHashMap有進(jìn)行重寫。
- 當(dāng)key所在的位置的數(shù)據(jù)結(jié)構(gòu)時紅黑樹亲善，調(diào)用了putTreeVal()方法设易，插入節(jié)點
- 當(dāng)key所在位置是一個單向鏈表；
- 會在內(nèi)部循環(huán)蛹头，如果key當(dāng)前所在位置時存在數(shù)據(jù)的亡嫌，那么就會判斷p.next是否為null
- 為null，就會調(diào)用newNode()創(chuàng)建一個新的節(jié)點插入進(jìn)去掘而。
- 當(dāng)key完全相同鹰服，進(jìn)行數(shù)據(jù)的賦值，然后進(jìn)行數(shù)據(jù)的替換揽咕。
還有一個方法挟冠，afterNodeInsertion(evict)
- 該方法在LinkedHashMap也進(jìn)行了重寫
- evict默認(rèn)時true
newNode()方法內(nèi)部調(diào)用了linkNodeLast(p);方法。
-
代碼分析如下
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { //構(gòu)造帶雙向鏈表屬性的LinkedHashMapEntry的對象 LinkedHashMapEntry<K,V> p = new LinkedHashMapEntry<K,V>(hash, key, value, e); //雙向列表的維護(hù) linkNodeLast(p); return p; } private void linkNodeLast(LinkedHashMapEntry<K,V> p) { //首先獲取當(dāng)前鏈表的最后一個元素 LinkedHashMapEntry<K,V> last = tail; //當(dāng)前插入的元素定義為最后一個元素 tail = p; //如果之前的最后一個元素是null袍睡，說明之前的鏈表就是空的知染，所以當(dāng)前的元素是第一個元素 if (last == null) head = p; else { //如果之前的鏈表不是null //put前的最后一個元素，設(shè)置為當(dāng)前put元素的前一個 p.before = last; //當(dāng)前put元素設(shè)置為put前最后一個元素的下一個斑胜。 last.after = p; //這樣就形成了一個雙向列表 } }
afterNodeAccess(e)方法分析
-
代碼分析如下
// 會將當(dāng)前訪問dao的字點e控淡，移動到雙向鏈表的尾部 void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMapEntry<K,V> last; //當(dāng)accessOrder為true，并且鏈表的尾部節(jié)點和 要替換的數(shù)據(jù)（舊數(shù)據(jù)）不相等 if (accessOrder && (last = tail) != e) { LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e, //將舊數(shù)據(jù)中前一個節(jié)點的before變量賦給b b = p.before, //將舊數(shù)據(jù)中后一個節(jié)點的after變量賦給a a = p.after; // p.after = null; // 當(dāng)b為null止潘，說明p的前置節(jié)點為null掺炭，p之前時頭節(jié)點 if (b == null) //p的后置節(jié)點設(shè)置為鏈表頭部 head = a; else //不為null ，將p的后置節(jié)點a更新為 p的前置節(jié)點的后置節(jié)點 b.after = a; if (a != null) //當(dāng) a不為null凭戴，將p的前置節(jié)點更新為p的后置節(jié)點 a.before = b; else //如果原本p的后置節(jié)點為null涧狮，說明p就是鏈表的尾部節(jié)點，那么將p的前置節(jié)點數(shù)據(jù)b設(shè)置為鏈表的尾部數(shù)據(jù) last = b; // 當(dāng)鏈表尾部為null，就將當(dāng)前的p設(shè)置鏈表的頭部數(shù)據(jù) // 可以這么理解者冤，當(dāng)現(xiàn)在的key與原有的key發(fā)生了hash碰撞肤视，但是原有的key對應(yīng)的value時null if (last == null) head = p; else { //更新當(dāng)前節(jié)點p的前置節(jié)點為原尾節(jié)點last，last的后置節(jié)點為p p.before = last; last.after = p; } //尾節(jié)點的引用賦值為p tail = p; //改變modCount ++modCount; } }
afterNodeInsertion方法分析
-
代碼分析如下
void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMapEntry<K,V> first; // removeEldestEntry 默認(rèn)是返回false的 所以if內(nèi)的代碼不會去執(zhí)行 if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //移除鏈表頭部的元素 removeNode(hash(key), key, null, false, true); } }
get()方法的源碼分析
LinkedHashMap重寫了HashMap的get方法
-
代碼如下
public V get(Object key) { Node<K,V> e; //首先根據(jù)key的hashCode值查找當(dāng)前為對應(yīng)的節(jié)點涉枫，如果不存就返回null if ((e = getNode(hash(key), key)) == null) return null; //當(dāng)accessOrder為true的時候邢滑，將當(dāng)前查到的節(jié)點e，移動到鏈表的尾部 if (accessOrder) afterNodeAccess(e); //返回查詢到節(jié)點的中的value return e.value; }
LinkedHashMap的刪除操作
LinkedHashMap沒有重寫remove方法愿汰，
我們知道remove方法內(nèi)部調(diào)用了removeNode()方法困后，removeNode方法內(nèi)部調(diào)用了afterNodeRemoval()
LinkedHashMap內(nèi)對afterNodeRemoval()方法進(jìn)行重寫
-
代碼如下
//刪除節(jié)點e的時候，將節(jié)點e在雙向列表上的前置和后置的節(jié)點引用都置空衬廷，然后更新前后節(jié)點（這里的前后節(jié)點對應(yīng)e的前后節(jié)點）的指向操灿。 void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e; b = p.before; a = p.after; //將待刪除節(jié)點P的前置和后置節(jié)點都置空 p.before = p.after = null; //如果前置節(jié)點null，那么將后置節(jié)點設(shè)置為頭部節(jié)點 if (b == null) head = a; else // 前置節(jié)點的后置節(jié)點 更新為 當(dāng)前p的后置節(jié)點所指向的節(jié)點 b.after = a; //當(dāng)后置節(jié)點為null泵督，將前置節(jié)點設(shè)置為尾部節(jié)點 if (a == null) tail = b; else //將后置節(jié)點 與 前置節(jié)點的后置節(jié)點進(jìn)行關(guān)聯(lián) a.before = b; }
LinkedHashMap的containsValue()
-
代碼如下
public boolean containsValue(Object value) { //從頭部節(jié)點開始趾盐，利用雙向列表的特點，每次拿到節(jié)點的后置節(jié)點 進(jìn)行循環(huán)判斷 //匹配到就返回true小腊，匹配不到就返回false for (LinkedHashMapEntry<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
-
代碼如下
//HashMap采用了嵌套for循環(huá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; }
圖的形式展示雙向列表
上面講的又是節(jié)點，又是前置節(jié)點秩冈，又是后置節(jié)點
然后什么accessOrder == true的時候本缠，又要移動節(jié)點，又要更新前置和后置的引用
下面就以一張圖表示一下入问。
LinkedHashMap_put_get_操作示意圖.png
