徹底理解HashMap及LinkedHashMap

下面基于JDK 1.8的源碼來(lái)學(xué)習(xí)HashMap及LinkedHashMap的數(shù)據(jù)結(jié)構(gòu)、原理。不同JDK版本之間也許會(huì)有些許差異，但不影響原理學(xué)習(xí)，JDK8相比以前對(duì)HashMap的修改比較大。

1、HashMap概述

Map是 Key-Value鍵值對(duì)映射的抽象接口，該映射不包括重復(fù)的鍵，即一個(gè)鍵對(duì)應(yīng)一個(gè)值。HashMap是Java Collection Framework的重要成員，也是Map族(如下圖所示)中我們最為常用的一種。簡(jiǎn)單地說(shuō)，HashMap是基于哈希表的Map接口的實(shí)現(xiàn)，以Key-Value的形式存在，即存儲(chǔ)的對(duì)象是 Node (同時(shí)包含了Key和Value) 。在HashMap中，其會(huì)根據(jù)hash算法來(lái)計(jì)算key-value的存儲(chǔ)位置并進(jìn)行快速存取。特別地，HashMap最多只允許一條Node的key為Null，但允許多條Node的value為Null。此外，HashMap是Map 的一個(gè)非同步的實(shí)現(xiàn)。

以下是HashMap的類繼承圖

必須指出的是，雖然容器號(hào)稱存儲(chǔ)的是 Java 對(duì)象，但實(shí)際上并不會(huì)真正將 Java 對(duì)象放入容器中，只是在容器中保留這些對(duì)象的引用。也就是說(shuō)，Java 容器實(shí)際上包含的是引用變量，而這些引用變量指向了我們要實(shí)際保存的 Java 對(duì)象。

1.1、HashMap定義及構(gòu)造函數(shù)

JDK中的定義為

public?class?HashMap<K,V>?extends?AbstractMap<K,V>?implements?Map<K,V>,?Cloneable,?Serializable?{
????//...
}

HashMap 一共提供了四個(gè)構(gòu)造函數(shù)，其中 默認(rèn)無(wú)參的構(gòu)造函數(shù) 和 參數(shù)為Map的構(gòu)造函數(shù) 為 Java Collection Framework 規(guī)范的推薦實(shí)現(xiàn)，其余兩個(gè)構(gòu)造函數(shù)則是 HashMap 專門提供的。

public?HashMap(int?initialCapacity)?{
????this(initialCapacity,?DEFAULT_LOAD_FACTOR);
}
//僅僅將負(fù)載因子初始化為默認(rèn)值
public?HashMap()?{
????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?
????//?all?other?fields?defaulted
}

HashMap(int initialCapacity, float loadFactor)構(gòu)造函數(shù)意在構(gòu)造一個(gè)指定初始容量和指定負(fù)載因子的空HashMap，其源碼如下：

public?HashMap(int?initialCapacity,?float?loadFactor)?{
????if?(initialCapacity?0)
????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+
???????????????????????????????????????????initialCapacity);
????//容量最大為2的30次方
????if?(initialCapacity?>?MAXIMUM_CAPACITY)
????????initialCapacity?=?MAXIMUM_CAPACITY;
????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))
????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+
???????????????????????????????????????????loadFactor);
????this.loadFactor?=?loadFactor;
????//這里調(diào)用函數(shù)計(jì)算觸發(fā)擴(kuò)容的閾值，threshold/loadFactor就是容量
????this.threshold?=?tableSizeFor(initialCapacity);
}

以上構(gòu)造函數(shù)的最后一行就是jdk8的修改，實(shí)際上在jdk7之前的版本，這個(gè)構(gòu)造方法最后一行就是：

table?=?new?Entry[capacity];

但是jdk8的最后一行并沒有立刻new出一個(gè)數(shù)組，而是調(diào)用了tableSizeFor方法，將結(jié)果賦值給了threshold變量。tableSizeFor方法源碼如下，從注釋就可以看出來(lái)，其目的是要獲得大于cap的最小的2的冪。比如cap=10，則返回16。

/**
?*?Returns?a?power?of?two?size?for?the?given?target?capacity.
?*/
?static?final?int?tableSizeFor(int?cap)?{
????int?n?=?cap?-?1;
????n?|=?n?>>>?1;
????n?|=?n?>>>?2;
????n?|=?n?>>>?4;
????n?|=?n?>>>?8;
????n?|=?n?>>>?16;
????return?(n?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;
?}

1.2、HashMap的數(shù)據(jù)結(jié)構(gòu)

我們知道，在Java中最常用的兩種結(jié)構(gòu)是數(shù)組和鏈表，幾乎所有的數(shù)據(jù)結(jié)構(gòu)都可以利用這兩種來(lái)組合實(shí)現(xiàn)，HashMap就是這種應(yīng)用的一個(gè)典型。實(shí)際上，經(jīng)典的HashMap就是一個(gè)鏈表數(shù)組，只是jdk1.8再次對(duì)經(jīng)典hashMap的數(shù)據(jù)結(jié)構(gòu)作了小幅調(diào)整，如下是當(dāng)前HaspMap的數(shù)據(jù)結(jié)構(gòu)：

在JDK1.6和JDK1.7中，HashMap采用數(shù)組+鏈表實(shí)現(xiàn)，即使用鏈表處理沖突，同一hash值的key-value鍵值對(duì)都存儲(chǔ)在一個(gè)鏈表里。但是當(dāng)數(shù)組中一個(gè)位置上的元素較多，即hash值相等的元素較多時(shí)，通過(guò)key值依次查找的效率較低。而在JDK1.8中，HashMap采用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)，當(dāng)鏈表長(zhǎng)度超過(guò)閾值8時(shí)，并且數(shù)組總?cè)萘砍^(guò)64時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時(shí)間。從鏈表轉(zhuǎn)換為紅黑樹后新加入鍵值對(duì)的效率降低，但查詢、刪除的效率都變高了。而當(dāng)發(fā)生擴(kuò)容或remove鍵值對(duì)導(dǎo)致原有的紅黑樹內(nèi)節(jié)點(diǎn)數(shù)量小于6時(shí)，則又將紅黑樹轉(zhuǎn)換成鏈表。

每一個(gè)HashMap都有一個(gè)Node類型的table數(shù)組，其中Node類型的定義如下：

static?class?Node<K,V>?implements?Map.Entry<K,V>?{
????final?int?hash;?????????//?聲明?hash?值為?final?的
????final?K?key;????????????//?聲明?key?為?final?的
????V?value;????????????????//?鍵值對(duì)的值
????Node?next;?????????//?指向下一個(gè)節(jié)點(diǎn)的引用

????Node(int?hash,?K?key,?V?value,?Node?next)?{
????????this.hash?=?hash;
????????this.key?=?key;
????????this.value?=?value;
????????this.next?=?next;
????}
}

Node為HashMap的內(nèi)部類，實(shí)現(xiàn)了Map.Entry接口，其包含了鍵key、值value、下一個(gè)節(jié)點(diǎn)next，以及hash值四個(gè)屬性。事實(shí)上，Node是構(gòu)成哈希表的基石，是哈希表所存儲(chǔ)的元素的具體形式。值得注意的是，int類型的hash值及引用變量key都被聲明成final，即不可變。

1.3、HashMap的快速存取

在HashMap中，我們最常用的兩個(gè)操作就是：put(Key,Value)和get(Key)。我們都知道，HashMap中的Key是唯一的，那它是如何保證唯一性的呢？我們首先想到的是用equals比較，沒錯(cuò)，這樣是可以實(shí)現(xiàn)的，但隨著元素的增多，put和get的效率將越來(lái)越低，這里的時(shí)間復(fù)雜度是O(n)。也就是說(shuō)，假如HashMap有1000個(gè)元素，那么put時(shí)就需要比較1000次，這是相當(dāng)耗時(shí)的，遠(yuǎn)達(dá)不到HashMap快速存取的目的。

實(shí)際上，HashMap很少會(huì)用到equals方法，因?yàn)槠鋬?nèi)通過(guò)一個(gè)哈希表管理所有元素，利用哈希算法可以快速的存取元素。當(dāng)我們調(diào)用put方法存值時(shí)，HashMap首先會(huì)調(diào)用Key的hashCode方法，然后基于此值獲取Key的哈希碼，通過(guò)哈希碼快速找到某個(gè)位置，這個(gè)位置可以被稱之為bucketIndex。根據(jù)equals方法與hashCode的協(xié)定可以知道，如果兩個(gè)對(duì)象的hashCode不同，那么equals一定為 false；如果其hashCode相同，equals也不一定為true。所以，理論上，hashCode 可能存在碰撞的情況，當(dāng)碰撞發(fā)生時(shí)，這時(shí)會(huì)取出bucketIndex桶內(nèi)已存儲(chǔ)的元素（如果該桶next引用不空，即有了鏈表也要遍歷鏈表），并通過(guò)hashCode()和equals()來(lái)逐個(gè)比較以判斷Key是否已存在。如果已存在，則使用新Value值替換舊Value值，并返回舊Value值；如果不存在，則存放新的鍵值對(duì)到鏈表中。因此，在HashMap中，equals()方法只有在哈希碼碰撞時(shí)才會(huì)被用到。

結(jié)合源碼來(lái)看HashMap的put操作：

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)?{
????Node[]?tab;?Node?p;?int?n,?i;
????//第一次put元素時(shí)，table數(shù)組為空，先調(diào)用resize生成一個(gè)指定容量的數(shù)組
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//hash值和n-1的與運(yùn)算結(jié)果為桶的位置，如果該位置空就直接放置一個(gè)Node
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????//如果計(jì)算出的bucket不空，即發(fā)生哈希沖突，就要進(jìn)一步判斷
????else?{
????????Node?e;?K?k;
????????//判斷當(dāng)前Node的key與要put的key是否相等
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????//判斷當(dāng)前Node是否是紅黑樹的節(jié)點(diǎn)
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????//以上都不是，說(shuō)明要new一個(gè)Node，加入到鏈表中
????????else?{
????????????for?(int?binCount?=?0;?;?++binCount)?{
?????????????//在鏈表尾部插入新節(jié)點(diǎn)，注意jdk1.8是在鏈表尾部插入新節(jié)點(diǎn)
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????//?如果當(dāng)前鏈表中的元素大于樹化的閾值，進(jìn)行鏈表轉(zhuǎn)樹的操作
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????//在鏈表中繼續(xù)判斷是否已經(jīng)存在完全相同的key
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????//走到這里，說(shuō)明本次put是更新一個(gè)已存在的鍵值對(duì)的value
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????//在hashMap中，afterNodeAccess方法體為空，交給子類去實(shí)現(xiàn)
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????++modCount;
????//如果當(dāng)前size超過(guò)臨界值，就擴(kuò)容。注意是先插入節(jié)點(diǎn)再擴(kuò)容
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實(shí)現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

通過(guò)上述源碼我們可以清楚了解到HashMap保存數(shù)據(jù)的過(guò)程。先計(jì)算key的hash值，然后根據(jù)hash值搜索在table數(shù)組中的索引位置，如果table數(shù)組在該位置處有元素，則查找是否存在相同的key，若存在則覆蓋原來(lái)key的value，否則將該元素保存在鏈表尾部，注意JDK1.7中采用的是頭插法，即每次都將沖突的鍵值對(duì)放置在鏈表頭，這樣最初的那個(gè)鍵值對(duì)最終就會(huì)成為鏈尾，而JDK1.8中使用的是尾插法。此外，若table在該處沒有元素，則直接保存。

對(duì)于hash函數(shù)，具體的來(lái)看下源碼

static?final?int?hash(Object?key)?{
????int?h;
????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);
}

以上可以看到key==null時(shí)，直接返回0，所以HashMap中鍵為NULL的鍵值對(duì)，一定在第一個(gè)桶中。

h >>> 16是用來(lái)取出h的高16位(>>>是無(wú)符號(hào)右移) 如下展示：

0000?0100?1011?0011??1101?1111?1110?0001

>>>?16?

0000?0000?0000?0000??0000?0100?1011?0011

通過(guò)之前putVal的源碼可以知道，HashMap是用(length - 1) & hash來(lái)計(jì)算數(shù)組下標(biāo)的。絕大多數(shù)情況下length一般都小于2^16即小于65536。所以hash & (length-1)；結(jié)果始終是hash的低16位與（length-1）進(jìn)行&運(yùn)算。要是能讓hash的高16位也參與運(yùn)算，會(huì)讓得到的下標(biāo)更加散列。

如何讓高16也參與運(yùn)算呢。方法就是讓hashCode()和自己的高16位進(jìn)行^運(yùn)算。由于與運(yùn)單和或運(yùn)單都會(huì)使得結(jié)果偏向0或者1，并不是均勻的概念，所以用異或。

結(jié)合源碼來(lái)看HashMap的get操作：

public?V?get(Object?key)?{
????Node?e;
????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;
}

final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?first,?e;?int?n;?K?k;
????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{
????????if?(first.hash?==?hash?&&?//?always?check?first?node
????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????return?first;
????????if?((e?=?first.next)?!=?null)?{
?????????//如果是紅黑樹，就調(diào)用樹的查找方法，否則遍歷鏈表直到找到
????????????if?(first?instanceof?TreeNode)
????????????????return?((TreeNode)first).getTreeNode(hash,?key);
????????????do?{
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}
????return?null;
}

在這里能夠根據(jù)key快速的取到value，除了和HashMap的數(shù)據(jù)結(jié)構(gòu)密不可分外，還和Node有莫大的關(guān)系。在前面就已經(jīng)提到過(guò)，HashMap在存儲(chǔ)過(guò)程中并沒有將key/value分開來(lái)存儲(chǔ)，而是當(dāng)做一個(gè)整體key-value來(lái)處理的，這個(gè)整體就是Node對(duì)象。

1.4 為什么HashMap的底層數(shù)組長(zhǎng)度總是2的n次方

當(dāng)?shù)讓訑?shù)組的length為2的n次方時(shí)， hash & (length - 1)就相當(dāng)于對(duì)length取模，其效率要比直接取模高得多，這是HashMap在效率上的一個(gè)優(yōu)化。

我們希望HashMap中的元素存放的越均勻越好。最理想的效果是，Node數(shù)組中每個(gè)位置都只有一個(gè)元素，這樣，查詢的時(shí)候效率最高，不需要遍歷單鏈表，也不需要通過(guò)equals去比較Key，而且空間利用率最大。

那如何計(jì)算才會(huì)分布最均勻呢？正如上一節(jié)提到的，HashMap采用了一個(gè)分兩步走的哈希策略：

使用hash()方法對(duì)Key的hashCode進(jìn)行重新計(jì)算，以防止質(zhì)量低下的hashCode()函數(shù)實(shí)現(xiàn)。由于HashMap的支撐數(shù)組長(zhǎng)度總是2的倍數(shù)，通過(guò)右移可以使低位的數(shù)據(jù)盡量的不同，從而使Key的hash值的分布盡量均勻；使用hash & (length - 1)方法進(jìn)行取余運(yùn)算，以使每個(gè)鍵值對(duì)的插入位置盡量分布均勻；由于length是2的整數(shù)冪，length-1的低位就全是1，高位全部是0。在與hash值進(jìn)行低位&運(yùn)算時(shí)，低位的值總是與原來(lái)hash值相同，高位&運(yùn)算時(shí)值為0。這就保證了不同的hash值發(fā)生碰撞的概率比較小，這樣就會(huì)使得數(shù)據(jù)在table數(shù)組中分布較均勻，查詢速度也較快。

1.5 HashMap的擴(kuò)容

隨著HashMap中元素的數(shù)量越來(lái)越多，發(fā)生碰撞的概率將越來(lái)越大，所產(chǎn)生的子鏈長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，這樣勢(shì)必會(huì)影響HashMap的存取速度。為了保證HashMap的效率，系統(tǒng)必須要在某個(gè)臨界點(diǎn)進(jìn)行擴(kuò)容處理，該臨界點(diǎn)就是HashMap中元素的數(shù)量在數(shù)值上等于threshold（table數(shù)組長(zhǎng)度*加載因子）。但是，不得不說(shuō)，擴(kuò)容是一個(gè)非常耗時(shí)的過(guò)程，因?yàn)樗枰匦掠?jì)算這些元素在新table數(shù)組中的位置并進(jìn)行復(fù)制處理。

首先回答一個(gè)問(wèn)題，在插入一個(gè)臨界節(jié)點(diǎn)時(shí)，HashMap是先擴(kuò)容后插入還是先插入后擴(kuò)容？這樣選取的優(yōu)勢(shì)是什么？

答案是：先插入后擴(kuò)容。通過(guò)查看putVal方法的源碼可以發(fā)現(xiàn)是先執(zhí)行完新節(jié)點(diǎn)的插入后，然后再做size是否大于threshold的判斷的。

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
??...
????//如果插入新結(jié)點(diǎn)后的size超過(guò)了臨界值，就擴(kuò)容，注意是先插入節(jié)點(diǎn)再擴(kuò)容
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實(shí)現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

為什么是先插入后擴(kuò)容？源碼已經(jīng)很清楚的表達(dá)了擴(kuò)容原因，調(diào)用put不一定是新增數(shù)據(jù)，還可能是覆蓋掉原來(lái)的數(shù)據(jù)，這里就存在一個(gè)key的比較問(wèn)題。以先擴(kuò)容為例，先比較是否是新增的數(shù)據(jù)，再判斷增加數(shù)據(jù)后是否要擴(kuò)容，這樣比較會(huì)浪費(fèi)時(shí)間，而先插入后擴(kuò)容，就有可能在中途直接通過(guò)return返回了（本次put是覆蓋操作，size不變不需要擴(kuò)容），這樣可以提高效率的。

JDK1.8相對(duì)于JDK1.7對(duì)HashMap的實(shí)現(xiàn)有較大改進(jìn)，做了很多優(yōu)化，鏈表轉(zhuǎn)紅黑樹是其中的一項(xiàng)，其實(shí)擴(kuò)容方法JDK1.8也有優(yōu)化，與JDK1.7有較大差別。

JDK1.8中resize方法源碼如下：

final?Node[]?resize()?{
????Node[]?oldTab?=?table;
????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;
????int?oldThr?=?threshold;
????int?newCap,?newThr?=?0;
????if?(oldCap?>?0)?{
?????//?原來(lái)的容量就已經(jīng)超過(guò)最大值就不再擴(kuò)容了，就只好隨你碰撞去吧
????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{
????????????threshold?=?Integer.MAX_VALUE;
????????????return?oldTab;
????????}
????????//?沒超過(guò)最大值，就擴(kuò)容為原來(lái)的2倍
????????else?if?((newCap?=?oldCap?<1)??????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)
????????????newThr?=?oldThr?<1;?//?double?threshold
????}
????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold
????????newCap?=?oldThr;
????else?{???????????????//?zero?initial?threshold?signifies?using?defaults
????????newCap?=?DEFAULT_INITIAL_CAPACITY;
????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);
????}
????//?計(jì)算新的resize上限，即新的threshold值
????if?(newThr?==?0)?{
????????float?ft?=?(float)newCap?*?loadFactor;
????????newThr?=?(newCap?float)MAXIMUM_CAPACITY??
??????????????????(int)ft?:?Integer.MAX_VALUE);
????}
????threshold?=?newThr;
????@SuppressWarnings({"rawtypes","unchecked"})
????????Node[]?newTab?=?(Node[])new?Node[newCap];
????table?=?newTab;
????if?(oldTab?!=?null)?{
?????//?把舊的bucket都移動(dòng)到新的buckets中
????????for?(int?j?=?0;?j?????????????Node?e;
????????????if?((e?=?oldTab[j])?!=?null)?{
????????????????oldTab[j]?=?null;
????????????????if?(e.next?==?null)
????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;
????????????????else?if?(e?instanceof?TreeNode)
????????????????????((TreeNode)e).split(this,?newTab,?j,?oldCap);
????????????????else?{?//?preserve?order
????????????????????Node?loHead?=?null,?loTail?=?null;
????????????????????Node?hiHead?=?null,?hiTail?=?null;
????????????????????Node?next;
????????????????????do?{
????????????????????????next?=?e.next;
????????????????????????//原來(lái)的桶索引值
????????????????????????if?((e.hash?&?oldCap)?==?0)?{
????????????????????????????if?(loTail?==?null)
????????????????????????????????loHead?=?e;
????????????????????????????else
????????????????????????????????loTail.next?=?e;
????????????????????????????loTail?=?e;
????????????????????????}
????????????????????????else?{
????????????????????????????if?(hiTail?==?null)
????????????????????????????????hiHead?=?e;
????????????????????????????else
????????????????????????????????hiTail.next?=?e;
????????????????????????????hiTail?=?e;
????????????????????????}
????????????????????}?while?((e?=?next)?!=?null);
????????????????????//?擴(kuò)容后，鍵值對(duì)在新table數(shù)組中的位置與舊數(shù)組中一樣
????????????????????if?(loTail?!=?null)?{
????????????????????????loTail.next?=?null;
????????????????????????newTab[j]?=?loHead;
????????????????????}
????????????????????//?擴(kuò)容后，鍵值對(duì)在新table數(shù)組中的位置與舊數(shù)組中不一樣
????????????????????//?新的位置=原來(lái)的位置?+?oldCap
????????????????????if?(hiTail?!=?null)?{
????????????????????????hiTail.next?=?null;
????????????????????????newTab[j?+?oldCap]?=?hiHead;
????????????????????}
????????????????}
????????????}
????????}
????}
????return?newTab;
}

必要的位置已經(jīng)加了注釋。最讓人疑惑的有兩個(gè)點(diǎn)：

為什么（e.hash & oldCap）== 0時(shí)就放入lo鏈表，否則就是hi鏈表; 為什么 j + oldCap就是鍵值對(duì)在新的table數(shù)組中的位置；其實(shí)這里包含著一些數(shù)學(xué)技巧。類似于上一小節(jié)為什么HashMap中數(shù)組的長(zhǎng)度總是取2的整數(shù)次冪。

查看源碼，我們發(fā)現(xiàn)擴(kuò)容時(shí)，使用的是2次冪的擴(kuò)展即長(zhǎng)度擴(kuò)為原來(lái)2倍，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置?？聪聢D可以明白這句話的意思，n為table的長(zhǎng)度，圖中上半部分表示擴(kuò)容前的key1和key2兩個(gè)Node的索引位置，圖中下半部分表示擴(kuò)容后key1和key2兩個(gè)Node新的索引位置。

元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1在高位多1bit，因此新的index就會(huì)發(fā)生這樣的變化：

因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新hash，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”，這個(gè)設(shè)計(jì)確實(shí)非常的巧妙，既省去了重新hash值的時(shí)間，而且同時(shí)，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，因此resize的過(guò)程，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的bucket了，這一塊就是JDK1.8新增的優(yōu)化點(diǎn)。

1.6 HashMap為什么引入紅黑樹而不是AVL樹

首先要說(shuō)明的是引入紅黑樹是了防止多次發(fā)生hash沖突時(shí)，鏈表長(zhǎng)度過(guò)長(zhǎng)，查找的時(shí)間復(fù)雜度會(huì)變成O(N)，同時(shí)同一位置再次發(fā)生hash沖突時(shí)采用尾插法插入的時(shí)間復(fù)雜度也會(huì)變成O(N)。用了紅黑樹可以把查找以及插入的時(shí)間復(fù)雜度都降低成O(logN)。

那么接下來(lái)問(wèn)題就變成了：有了二叉查找樹、平衡樹（AVL）為啥還需要紅黑樹？

二叉查找樹，也稱有序二叉樹（ordered binary tree），或已排序二叉樹（sorted binary tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹; 沒有鍵值相等的節(jié)點(diǎn)（no duplicate nodes） 因?yàn)橐豢糜蒒個(gè)結(jié)點(diǎn)隨機(jī)構(gòu)造的二叉查找樹的高度為logN，所以順理成章，二叉查找樹的一般操作的執(zhí)行時(shí)間為O(logN)。但二叉查找樹若退化成了一棵具有N個(gè)結(jié)點(diǎn)的線性鏈后，則這些操作最壞情況運(yùn)行時(shí)間為O(N)。可想而知，我們不能讓這種情況發(fā)生，為了解決這個(gè)問(wèn)題，于是我們引申出了平衡二叉樹，即AVL樹，它對(duì)二叉查找樹做了改進(jìn)，在我們每插入一個(gè)節(jié)點(diǎn)的時(shí)候，必須保證每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的左子樹和右子樹的樹高度差不超過(guò)1。如果超過(guò)了就對(duì)其進(jìn)行左旋或右旋，使之平衡。

雖然平衡樹解決了二叉查找樹退化為近似鏈表的缺點(diǎn)，能夠把查找時(shí)間控制在 O(logN)，不過(guò)卻不是最佳的，因?yàn)槠胶鈽湟竺總€(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1，這個(gè)要求實(shí)在是太嚴(yán)了，導(dǎo)致每次進(jìn)行插入/刪除節(jié)點(diǎn)的時(shí)候，幾乎都會(huì)破壞平衡樹的規(guī)則，進(jìn)而我們都需要通過(guò)左旋和右旋來(lái)進(jìn)行調(diào)整，使之再次成為一顆符合要求的平衡樹。

顯然，如果在那種插入、刪除很頻繁的場(chǎng)景中，平衡樹需要頻繁著進(jìn)行調(diào)整，這會(huì)使平衡樹的性能大打折扣，為了解決這個(gè)問(wèn)題，于是有了紅黑樹。紅黑樹是不符合AVL樹的平衡條件的，即每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度最多差1的二叉查找樹，但是提出了為節(jié)點(diǎn)增加顏色，紅黑樹是用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低，任何不平衡都會(huì)在三次旋轉(zhuǎn)之內(nèi)解決，相較于AVL樹為了維持平衡的開銷要小得多。

AVL樹是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多，所以紅黑樹的插入效率相對(duì)于AVL樹更高。單單在查找方面比較效率的話，由于AVL高度平衡，因此AVL樹的查找效率比紅黑樹更高。

對(duì)主要的幾種平衡樹作個(gè)比較，發(fā)現(xiàn)紅黑樹有著良好的穩(wěn)定性和完整的功能，性能表現(xiàn)也很不錯(cuò)，綜合實(shí)力強(qiáng)，在諸如STL的場(chǎng)景中需要穩(wěn)定表現(xiàn)。實(shí)際應(yīng)用中，若搜索的頻率遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL，如果發(fā)生搜索和插入刪除操作的頻率差不多，應(yīng)該選擇紅黑樹。

1.7 HashMap的線程不安全

所有人都知道HashMap是線程不安全的，我們應(yīng)該使用ConcurrentHashMap。但是為什么HashMap是線程不安全的呢？

首先需要強(qiáng)調(diào)一點(diǎn)，HashMap的線程不安全體現(xiàn)在會(huì)造成死循環(huán)、數(shù)據(jù)丟失、數(shù)據(jù)覆蓋這些問(wèn)題。其中死循環(huán)和數(shù)據(jù)丟失是在JDK1.7中出現(xiàn)的問(wèn)題，在JDK1.8中已經(jīng)得到解決，然而1.8中仍會(huì)有數(shù)據(jù)覆蓋的問(wèn)題，即在并發(fā)執(zhí)行HashMap的put操作時(shí)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。

首先擴(kuò)容會(huì)造成HashMap的線程不安全，根源就在JDK1.7的transfer函數(shù)中。transfer方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里。JDK1.7中HashMap的transfer函數(shù)源碼如下：

void?transfer(Entry[]?newTable)?{
?//src引用了舊的Entry數(shù)組
?Entry[]?src?=?table;?
?int?newCapacity?=?newTable.length;
?//遍歷舊的Entry數(shù)組
?for?(int?j?=?0;?j???//取得舊Entry數(shù)組的每個(gè)元素
??Entry?e?=?src[j];?
??if?(e?!=?null)?{
??src[j]?=?null;
??//釋放舊Entry數(shù)組的對(duì)象引用（for循環(huán)后，舊的Entry數(shù)組不再引用任何對(duì)象）
??do?{
???Entry?next?=?e.next;
???int?i?=?indexFor(e.hash,?newCapacity);?
???//重新計(jì)算每個(gè)元素在數(shù)組中的位置
???e.next?=?newTable[i];?//標(biāo)記[1]
???newTable[i]?=?e;?//將元素放在數(shù)組上
???e?=?next;?
???//訪問(wèn)下一個(gè)Entry鏈上的元素
???}?while?(e?!=?null);
??}
?}
}

這段代碼是HashMap的擴(kuò)容操作，重新定位每個(gè)桶的下標(biāo)，并采用頭插法將元素遷移到新數(shù)組中。頭插法會(huì)將鏈表的順序翻轉(zhuǎn)，這也是在多線程環(huán)境下會(huì)形成死循環(huán)的關(guān)鍵點(diǎn)。擴(kuò)容造成死循環(huán)和數(shù)據(jù)丟失的詳細(xì)過(guò)程這里不再贅述，可以搜索很多分析這個(gè)過(guò)程的文章。

JDK1.8的源碼中已經(jīng)沒有transfer函數(shù)，因?yàn)镴DK1.8直接在resize函數(shù)中完成了數(shù)據(jù)遷移。此外JDK1.8在進(jìn)行元素插入時(shí)使用的是尾插法。為什么多線程環(huán)境下JDK1.8的HashMap會(huì)出現(xiàn)數(shù)據(jù)覆蓋的情況呢，我們來(lái)看一下JDK1.8中的putVal源碼：

final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,
???????????????boolean?evict)?{
????Node[]?tab;?Node?p;?int?n,?i;
????//第一次put元素時(shí)，table數(shù)組為空，先調(diào)用resize生成一個(gè)指定容量的數(shù)組
????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)
????????n?=?(tab?=?resize()).length;
????//hash值和n-1的與運(yùn)算結(jié)果為桶的位置，如果該位置空就直接放置一個(gè)Node
????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)
????????tab[i]?=?newNode(hash,?key,?value,?null);
????//如果計(jì)算出的bucket不空，即發(fā)生哈希沖突，就要進(jìn)一下判斷
????else?{
????????Node?e;?K?k;
????????//判斷當(dāng)前Node的key與要put的key是否相等
????????if?(p.hash?==?hash?&&
????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????e?=?p;
????????//判斷當(dāng)前Node是否是紅黑樹的節(jié)點(diǎn)
????????else?if?(p?instanceof?TreeNode)
????????????e?=?((TreeNode)p).putTreeVal(this,?tab,?hash,?key,?value);
????????//以上都不是，說(shuō)明要new一個(gè)Node，加入到鏈表中
????????else?{
????????????for?(int?binCount?=?0;?;?++binCount)?{
?????????????//進(jìn)入這個(gè)if說(shuō)明是到達(dá)鏈表尾部
????????????????if?((e?=?p.next)?==?null)?{
????????????????????p.next?=?newNode(hash,?key,?value,?null);
????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st
????????????????????????treeifyBin(tab,?hash);
????????????????????break;
????????????????}
????????????????//在鏈表中繼續(xù)判斷是否已經(jīng)存在完全相同的key
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????break;
????????????????p?=?e;
????????????}
????????}
????????//走到這里，說(shuō)明本次put是更新一個(gè)已存在的鍵值對(duì)的value
????????if?(e?!=?null)?{?//?existing?mapping?for?key
????????????V?oldValue?=?e.value;
????????????if?(!onlyIfAbsent?||?oldValue?==?null)
????????????????e.value?=?value;
????????????//在hashMap中，afterNodeAccess方法體為空，交給子類去實(shí)現(xiàn)
????????????afterNodeAccess(e);
????????????return?oldValue;
????????}
????}
????//下面兩個(gè)自增操作都不是原子的
????++modCount;
????if?(++size?>?threshold)
????????resize();
????//在hashMap中，afterNodeInsertion方法體為空，交給子類去實(shí)現(xiàn)
????afterNodeInsertion(evict);
????return?null;
}

其中if((p = tab[i = (n - 1) & hash]) == null)是判斷是否出現(xiàn)hash碰撞，假設(shè)兩個(gè)線程A、B都在進(jìn)行put操作，并且hash函數(shù)計(jì)算出的插入下標(biāo)是相同的，當(dāng)線程A執(zhí)行完這行代碼后由于時(shí)間片耗盡導(dǎo)致被掛起，而線程B得到時(shí)間片后在該下標(biāo)處插入了元素，完成了正常的插入，然后線程A獲得時(shí)間片，由于之前已經(jīng)進(jìn)行了hash碰撞的判斷，所以此時(shí)不會(huì)再進(jìn)行判斷，而是直接進(jìn)行插入，這就導(dǎo)致了線程B插入的數(shù)據(jù)被線程A覆蓋了，從而線程不安全。

除此之外，還有就是代碼的末尾部分有個(gè)++size，我們這樣想，還是線程A、B，這兩個(gè)線程同時(shí)進(jìn)行put操作時(shí)，假設(shè)當(dāng)前HashMap的size大小為10，當(dāng)線程A執(zhí)行到size自增這行代碼時(shí)，從主內(nèi)存中獲得size的值為10后準(zhǔn)備進(jìn)行+1操作，但是由于時(shí)間片耗盡只好讓出CPU，線程B拿到CPU還是從主內(nèi)存中拿到size的值10進(jìn)行+1操作，完成了put操作并將size=11寫回主內(nèi)存，由于size不是volatile修改的變量，然后線程A再次拿到CPU后不會(huì)再?gòu)闹鲀?nèi)存中加載一次size的值，而是使用自己工作內(nèi)存中的副本，繼續(xù)執(zhí)行加1，當(dāng)執(zhí)行完put操作后，還是將size=11寫回主內(nèi)存，此時(shí)，線程A、B都執(zhí)行了一次put操作，但是size的值只增加了1，所有說(shuō)還是由于數(shù)據(jù)覆蓋又導(dǎo)致了線程不安全。

2、LinkedHashMap概述

HashMap是Java Collection Framework的重要成員，也是Map族中我們最為常用的一種。不過(guò)遺憾的是，HashMap是無(wú)序的，也就是說(shuō)，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序。HashMap的這一缺點(diǎn)往往會(huì)造成諸多不便，因?yàn)樵谟行﹫?chǎng)景中，我們確需要用到一個(gè)可以保持插入順序的Map。慶幸的是，JDK為我們解決了這個(gè)問(wèn)題，它為HashMap提供了一個(gè)子類 —— LinkedHashMap。雖然LinkedHashMap增加了時(shí)間和空間上的開銷，但是它通過(guò)維護(hù)一個(gè)額外的雙向鏈表保證了迭代順序==。特別地，==該迭代順序可以是插入順序，也可以是訪問(wèn)順序。因此，根據(jù)鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap和保持訪問(wèn)順序的LinkedHashMap，其中LinkedHashMap的默認(rèn)實(shí)現(xiàn)是按插入順序排序的。

更直觀地，下圖很好地還原了LinkedHashMap的原貌：HashMap和雙向鏈表的密切配合和分工合作造就了LinkedHashMap。特別需要注意的是，next用于維護(hù)HashMap各個(gè)桶中的Entry鏈，before、after用于維護(hù)LinkedHashMap的雙向鏈表，雖然它們的作用對(duì)象都是Entry，但是各自分離，是兩碼事兒。

特別地，由于LinkedHashMap是HashMap的子類，所以LinkedHashMap自然會(huì)擁有HashMap的所有特性。比如，LinkedHashMap也最多只允許一條Entry的鍵為Null(多條會(huì)覆蓋)，但允許多條Entry的值為Null。此外，LinkedHashMap 也是 Map 的一個(gè)非同步的實(shí)現(xiàn)。此外，LinkedHashMap還可以用來(lái)實(shí)現(xiàn)LRU (Least recently used, 最近最少使用)算法。

2.1、LinkedHashMap定義及構(gòu)造函數(shù)

本質(zhì)上，HashMap和雙向鏈表合二為一即是LinkedHashMap。JDK1.8中LinkedHashMap的定義源碼如下：

public?class?LinkedHashMap<K,V>
????extends?HashMap<K,V>
????implements?Map<K,V>
{
?/**
??*?HashMap.Node?subclass?for?normal?LinkedHashMap?entries.
??*/
?static?class?Entry<K,V>?extends?HashMap.Node<K,V>?{
??//再加兩個(gè)引用，分別指向前一個(gè)插入的Entry與后一個(gè)插入的Entry
?????Entry?before,?after;
?????Entry(int?hash,?K?key,?V?value,?Node?next)?{
?????????super(hash,?key,?value,?next);
?????}
?}
?
?/**
??*?The?head?(eldest)?of?the?doubly?linked?list.
??*?頭節(jié)點(diǎn)引用
??*/
?transient?LinkedHashMap.Entry?head;
?
?/**
??*?The?tail?(youngest)?of?the?doubly?linked?list.
??*?尾節(jié)點(diǎn)引用
??*/
?transient?LinkedHashMap.Entry?tail;
?
?/**
??*?The?iteration?ordering?method?for?this?linked?hash?map:?true
??*?for?access-order,?false?for?insertion-order.
??*?true表示按照訪問(wèn)順序迭代，false時(shí)表示按照插入順序?
??*?@serial
??*/
?final?boolean?accessOrder;
?
?...?
}

LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了Entry。LinkedHashMap中的Entry繼承了HashMap.Node，但增加了兩個(gè)指針before 和 after，它們分別用于維護(hù)雙向鏈接列表。特別需要注意的是，next用于維護(hù)HashMap各個(gè)Node的連接順序，before、after用于維護(hù)Entry插入的先后順序。

LinkedHashMap的5大構(gòu)造函數(shù)都是在HashMap的構(gòu)造函數(shù)的基礎(chǔ)上實(shí)現(xiàn)的，分別如下：

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?m)?{
????super();
????accessOrder?=?false;
????putMapEntries(m,?false);
}

public?LinkedHashMap(int?initialCapacity,
?????????????????????float?loadFactor,
?????????????????????boolean?accessOrder)?{
????super(initialCapacity,?loadFactor);
????this.accessOrder?=?accessOrder;
}

2.2、LinkedHashMap的快速存取

在HashMap中最常用的兩個(gè)操作就是：put(Key,Value) 和 get(Key)。同樣地，在 LinkedHashMap 中最常用的也是這兩個(gè)操作。對(duì)于put(Key,Value)方法而言，LinkedHashMap完全繼承了HashMap的 put(Key,Value) 方法，只是對(duì)putVal(hash,key, value, onlyIfAbsent,evict)方法所調(diào)用的afterNodeAccess方法和afterNodeInsertion方法進(jìn)行了重寫；對(duì)于get(Key)方法，LinkedHashMap則直接對(duì)它進(jìn)行了重寫。下面我們結(jié)合JDK源碼看 LinkedHashMap 的存取實(shí)現(xiàn)。

HashMap的putVal源碼，上一節(jié)中已經(jīng)分析過(guò)，直接來(lái)看LinkedHashMap對(duì)afterNodeAccess和afterNodeInsertion方法的實(shí)現(xiàn)：

void?afterNodeInsertion(boolean?evict)?{?//?possibly?remove?eldest
????LinkedHashMap.Entry?first;
????if?(evict?&&?(first?=?head)?!=?null?&&?removeEldestEntry(first))?{
????????K?key?=?first.key;
????????removeNode(hash(key),?key,?null,?false,?true);
????}
}

/**
?*?如果map應(yīng)該刪除最老的節(jié)點(diǎn)，返回true
?*?這個(gè)方法在被put和putAll方法被調(diào)用，當(dāng)向map中插入一個(gè)新的entry時(shí)被執(zhí)行。這個(gè)方法提供了當(dāng)一個(gè)新的entry被添加到linkedHashMap中，刪除最老節(jié)點(diǎn)的機(jī)會(huì)。
?*?
?*?這個(gè)方法是很有用的，可以通過(guò)刪除最老節(jié)點(diǎn)來(lái)減少內(nèi)存消耗，避免溢出。
?*?
?*?簡(jiǎn)單的例子：這個(gè)方法的重寫將map的最大值設(shè)為100，到100時(shí)，每次增一個(gè)entry，就刪除一次最老節(jié)點(diǎn)。
?*?
?*?????private?static?final?int?MAX_ENTRIES?=?100;
?*
?*?????protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
?*????????return?size()?>?MAX_ENTRIES;
?*?????}
?*
?*?這個(gè)方法一般不會(huì)直接修改map，而是通過(guò)返回true或者false來(lái)控制是否修改map。
?*
??*
?*?@param????eldest?最老的節(jié)點(diǎn)（即頭節(jié)點(diǎn)）
?*?@return???如果map應(yīng)該刪除頭節(jié)點(diǎn)就返回true，否則返回false
?*/
?protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????return?false;
?}

以上afterNodeInsertion方法由于removeEldestEntry方法默認(rèn)一直返回的false而無(wú)執(zhí)行意義。也就意味著如果想要讓它有意義必須重寫removeEldestEntry方法。

void?afterNodeAccess(Node?e)?{?//?move?node?to?last
????LinkedHashMap.Entry?last;
????if?(accessOrder?&&?(last?=?tail)?!=?e)?{
????????LinkedHashMap.Entry?p?=
????????????(LinkedHashMap.Entry)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;
????}
}

可見僅有accessOrder為true時(shí)，且訪問(wèn)節(jié)點(diǎn)不等于尾節(jié)點(diǎn)時(shí)，該方法才有意義。通過(guò)before/after重定向，將新訪問(wèn)節(jié)點(diǎn)鏈接為鏈表尾節(jié)點(diǎn)。

LinkedHashMap的get操作：

public?V?get(Object?key)?{
????Node?e;
????if?((e?=?getNode(hash(key),?key))?==?null)
????????return?null;
????//當(dāng)accessOrder為true時(shí)，才會(huì)出現(xiàn)個(gè)性化邏輯
????if?(accessOrder)
????????afterNodeAccess(e);
????return?e.value;
}


//以下是HashMap中的getNode方法
final?Node?getNode(int?hash,?Object?key)?{
????Node[]?tab;?Node?first,?e;?int?n;?K?k;
????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&
????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{
????????if?(first.hash?==?hash?&&?//?always?check?first?node
????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????return?first;
????????if?((e?=?first.next)?!=?null)?{
????????????if?(first?instanceof?TreeNode)
????????????????return?((TreeNode)first).getTreeNode(hash,?key);
????????????do?{
????????????????if?(e.hash?==?hash?&&
????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))
????????????????????return?e;
????????????}?while?((e?=?e.next)?!=?null);
????????}
????}
????return?null;
}

在LinkedHashMap的get方法中，通過(guò)HashMap中的getNode方法獲取Node對(duì)象。注意這里的afterNodeAccess方法，如果鏈表中元素的排序規(guī)則是按照插入的先后順序排序的話，該方法什么也不做；如果鏈表中元素的排序規(guī)則是按照訪問(wèn)的先后順序排序的話，則將e移到鏈表的末尾處。

2.3、LinkedHashMap與LRU算法

到此為止，我們已經(jīng)分析完了LinkedHashMap的存取實(shí)現(xiàn)，這與HashMap大體相同。LinkedHashMap區(qū)別于HashMap最大的一個(gè)不同點(diǎn)是，前者是有序的，而后者是無(wú)序的。為此，LinkedHashMap增加了兩個(gè)屬性用于保證順序，分別是雙向鏈表頭結(jié)點(diǎn)header和標(biāo)志位accessOrder。我們知道，header是LinkedHashMap所維護(hù)的雙向鏈表的頭結(jié)點(diǎn)，而accessOrder用于決定具體的迭代順序。

我們知道，當(dāng)accessOrder標(biāo)志位為true時(shí)，表示雙向鏈表中的元素按照訪問(wèn)的先后順序排列，可以看到，雖然Entry插入鏈表的順序依然是按照其put到LinkedHashMap中的順序，但put和get方法均有判斷accessOrder的值。如果accessOrder為true，put時(shí)將新插入的元素放入到雙向鏈表的尾部，get時(shí)將當(dāng)前訪問(wèn)的Entry移到雙向鏈表的尾部。當(dāng)標(biāo)志位accessOrder的值為false時(shí)，表示雙向鏈表中的元素按照Entry插入LinkedHashMap到中的先后順序排序，即每次put到LinkedHashMap中的Entry都放在雙向鏈表的尾部，這樣遍歷雙向鏈表時(shí)，Entry的輸出順序便和插入的順序一致，這也是默認(rèn)的雙向鏈表的存儲(chǔ)順序。

測(cè)試代碼

@Test
public?void?testLinkedHashMap()?{
????Map?map?=?new?HashMap<>(128);
????System.out.println("------HashMap------");
????map.put("first",?"a");
????map.put("second",?"b");
????map.put("third",?"c");
????map.put("fourth",?"d");
????map.put("fifth",?"e");
????map.put("sixth",?"f");
????map.forEach((key,value)?->?{
????????System.out.println("key="?+?key?+?",value="?+?value);
????});

????map.clear();
????System.out.println("------LinkedHashMap------");
????map?=?new?LinkedHashMap<>(128);
????map.put("first",?"a");
????map.put("second",?"b");
????map.put("third",?"c");
????map.put("fourth",?"d");
????map.put("fifth",?"e");
????map.put("sixth",?"f");
????
????map.forEach((key,value)?->?{
????????System.out.println("key="?+?key?+?",value="?+?value);
????});
}

運(yùn)行結(jié)果如下，HashMap不保證有序而LinkedHashMap默認(rèn)按迭代順序和插入的順序一致。

前面介紹的LinkedHashMap的五種構(gòu)造方法，前四個(gè)構(gòu)造方法都將accessOrder設(shè)為false，說(shuō)明默認(rèn)是按照插入順序排序的；而第五個(gè)構(gòu)造方法可以自定義傳入的accessOrder的值。當(dāng)我們要用LinkedHashMap實(shí)現(xiàn)LRU算法時(shí)，就需要調(diào)用該構(gòu)造方法并將accessOrder置為true。

使用LinkedHashMap實(shí)現(xiàn)LRU的必要前提是將accessOrder標(biāo)志位設(shè)為true以便開啟按訪問(wèn)順序排序的模式。我們可以看到，無(wú)論是put方法還是get方法，都會(huì)導(dǎo)致目標(biāo)Entry成為最近訪問(wèn)的Entry，因此就把該Entry加入到了雙向鏈表的末尾。這樣，我們便把最近使用的Entry放入到了雙向鏈表的后面。多次操作后，雙向鏈表前面的Entry便是最近沒有使用的，這樣當(dāng)節(jié)點(diǎn)個(gè)數(shù)滿的時(shí)候，刪除最前面的Entry即可，因?yàn)樗褪亲罱钌偈褂玫腅ntry。

public?class?SomeTest?{
????@Test
????public?void?testLru()?{
????????LRU?lru?=?new?LRU<>(8);
????????String?s?=?"abcdefghijkl";
????????for?(int?i?=?0;?i?????????????lru.put(s.charAt(i),?i?+?1);
????????}
????????System.out.println("LRU的大?。?"?+?lru.size());
????????System.out.println(lru);
????????System.out.println("LRU的中key為h的value值：?"?+?lru.get('h'));
????????System.out.println(lru);
????????lru.put('z',?26);
????????System.out.println(lru);
????}

????public?static?class?LRU<K,?V>?extends?LinkedHashMap<K,?V>?{
????
????????private?int?cacheSize;
????
????????public?LRU(int?cacheSize)?{
????????????super(cacheSize,?0.75f,?true);
????????????this.cacheSize?=?cacheSize;
????????}
????
????????/**
?????????*?重寫LinkedHashMap中的removeEldestEntry方法，當(dāng)LRU中元素多余cacheSize個(gè)時(shí)，刪除最老的節(jié)點(diǎn)（即最不經(jīng)常使用的元素）
?????????*?@param?eldest
?????????*?@return
?????????*/
????????protected?boolean?removeEldestEntry(Map.Entry?eldest)?{
????????????return?size()?>?getCacheSize();
????????}
????
????????public?int?getCacheSize()?{
????????????return?cacheSize;
????????}
????
????}
}

運(yùn)行結(jié)果：

LRU的大?。? {e=5, f=6, g=7, h=8, i=9, j=10, k=11, l=12} LRU的中key為h的value值：8 {e=5, f=6, g=7, i=9, j=10, k=11, l=12, h=8} {f=6, g=7, i=9, j=10, k=11, l=12, h=8, z=26}

1.?超硬核，Nacos實(shí)現(xiàn)原理詳細(xì)講解
2.?SpringBoot + Mybatis-puls + ClickHouse增刪改查入門教程
3.?扔掉 Postman ? Apifox 值得一試！
4.?Postman最被低估的功能，自動(dòng)化接口測(cè)試效率簡(jiǎn)直無(wú)敵！
最近面試BAT，整理一份面試資料《Java面試BATJ通關(guān)手冊(cè)》，覆蓋了Java核心技術(shù)、JVM、Java并發(fā)、SSM、微服務(wù)、數(shù)據(jù)庫(kù)、數(shù)據(jù)結(jié)構(gòu)等等。
獲取方式：點(diǎn)“在看”，關(guān)注公眾號(hào)并回復(fù)?Java?領(lǐng)取，更多內(nèi)容陸續(xù)奉上。
文章有幫助的話，在看，轉(zhuǎn)發(fā)吧。
謝謝支持喲 (*^__^*）