HashMap集合

1.散列

散列，又稱哈希（Hash），是一種數(shù)據(jù)處理方式。它通過特定的算法，將輸入（比如字符串、文件等）轉(zhuǎn)換成固定長(zhǎng)度的一串（通常是數(shù)字），并且這個(gè)過程是不可逆的。這個(gè)過程中的算法就稱為哈希函數(shù)，得到的結(jié)果就稱為哈希值。

散列的主要作用是為了檢索數(shù)據(jù)。通過散列，可以將大量的數(shù)據(jù)進(jìn)行壓縮，然后將壓縮后的散列值作為索引，存儲(chǔ)在散列表中。當(dāng)需要查找數(shù)據(jù)時(shí)，只需要用同樣的哈希函數(shù)處理要查找的數(shù)據(jù)，得到散列值，然后在散列表中查找對(duì)應(yīng)的數(shù)據(jù)，就可以大大提高檢索的速度。

同時(shí)，由于散列過程是不可逆的，所以也常常用于數(shù)據(jù)的安全性校驗(yàn)，如密碼的存儲(chǔ)和驗(yàn)證、數(shù)字簽名等。

示例：

一個(gè)簡(jiǎn)單的例子是電話簿。如果你想查找一個(gè)人的電話號(hào)碼，你可以按照字母順序一頁一頁地查找，這就像是在一個(gè)數(shù)組中查找數(shù)據(jù)。但這種方法效率很低，特別是當(dāng)電話簿的數(shù)據(jù)量很大時(shí)。

如果你使用哈希函數(shù)，將每個(gè)人的名字轉(zhuǎn)換為一個(gè)數(shù)字，然后按照這個(gè)數(shù)字存儲(chǔ)他們的電話號(hào)碼，這就像是創(chuàng)建了一個(gè)哈希表。比如，哈希函數(shù)可以是將名字中的每個(gè)字母轉(zhuǎn)換為其在字母表中的位置（A=1，B=2，C=3，等等），然后加起來。所以，"John"的哈希值就是10+15+8+14=47。

現(xiàn)在，如果你想查找John的電話號(hào)碼，你只需要計(jì)算出"John"的哈希值47，然后直接查找哈希表中47對(duì)應(yīng)的電話號(hào)碼，就可以快速找到結(jié)果，無需遍歷整個(gè)電話簿。

這就是散列的基本原理和用法。

2.hashMap結(jié)構(gòu)

在Java8 之前 HashMap 由 數(shù)組+鏈表 數(shù)據(jù)結(jié)構(gòu)組成，主要有以下不足之處：

1. 即使散列函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布
2. HashMap中有大量元素都存放在同一個(gè)桶下時(shí)，該桶下就會(huì)有一個(gè)長(zhǎng)長(zhǎng)的鏈表，降低了查詢的效率

針對(duì)以上情況，自從java8開始引入了紅黑樹來進(jìn)行優(yōu)化。新版的HashMap 由 數(shù)組+鏈表 +紅黑樹數(shù)據(jù)結(jié)構(gòu)組成，當(dāng)鏈表長(zhǎng)度大于閾值（或者紅黑樹的邊界值，默認(rèn)為 8）并且當(dāng)前數(shù)組的長(zhǎng)度大于64時(shí)，此時(shí)此索引位置上的所有數(shù)據(jù)改為使用紅黑樹存儲(chǔ)。

特點(diǎn)：

1. 存取無序的

2. 鍵和值位置都可以是null，但是鍵位置只能是一個(gè)null

3. 鍵位置是唯一的，底層的數(shù)據(jù)結(jié)構(gòu)控制鍵的

4. jdk1.8前數(shù)據(jù)結(jié)構(gòu)是：鏈表 + 數(shù)組 jdk1.8之后是 ： 鏈表 + 數(shù)組 + 紅黑樹

5. 閾值(邊界值) > 8 并且數(shù)組長(zhǎng)度大于64，才將鏈表轉(zhuǎn)換為紅黑樹，變?yōu)榧t黑樹的目的是為了高效的查詢。

3.繼承關(guān)系

HashMap繼承關(guān)系如下圖所示：

說明：

• Cloneable 空接口，表示可以克隆。 創(chuàng)建并返回HashMap對(duì)象的一個(gè)副本。
• Serializable 序列化接口。屬于標(biāo)記性接口。HashMap對(duì)象可以被序列化和反序列化。
• AbstractMap 父類提供了Map實(shí)現(xiàn)接口。以最大限度地減少實(shí)現(xiàn)此接口所需的工作。

補(bǔ)充：通過上述繼承關(guān)系我們發(fā)現(xiàn)一個(gè)很奇怪的現(xiàn)象， 就是HashMap已經(jīng)繼承了AbstractMap而AbstractMap類實(shí)現(xiàn)了Map接口，那為什么HashMap還要在實(shí)現(xiàn)Map接口呢？同樣在ArrayList中LinkedList中都是這種結(jié)構(gòu)。

據(jù) java 集合框架的創(chuàng)始人Josh Bloch描述，這樣的寫法是一個(gè)失誤。在java集合框架中，類似這樣的寫法很多，最開始寫java集合框架的時(shí)候，他認(rèn)為這樣寫，在某些地方可能是有價(jià)值的，直到他意識(shí)到錯(cuò)了。顯然的，JDK的維護(hù)者，后來不認(rèn)為這個(gè)小小的失誤值得去修改，所以就這樣存在下來了。

4.成員變量

1.序列化版本號(hào)

private static final long serialVersionUID = 362498820763181265L;

2.集合的初始化容量( 必須是二的n次冪 )

//默認(rèn)的初始容量是16 -- 1<<4相當(dāng)于1*2的4次方---1*16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;   

問題： 為什么必須是2的n次冪？如果輸入值不是2的冪比如10會(huì)怎么樣？

HashMap構(gòu)造方法還可以指定集合的初始化容量大小：

HashMap(int initialCapacity) 構(gòu)造一個(gè)帶指定初始容量和默認(rèn)加載因子 (0.75) 的空 HashMap。

當(dāng)向HashMap中添加一個(gè)元素的時(shí)候，需要根據(jù)key的hash值，去確定其在數(shù)組中的具體位置。 HashMap為了存取高效，要盡量較少碰撞，就是要盡量把數(shù)據(jù)分配均勻，每個(gè)鏈表長(zhǎng)度大致相同，這個(gè)實(shí)現(xiàn)就在把數(shù)據(jù)存到哪個(gè)鏈表中的算法。

這個(gè)算法實(shí)際就是取模，hash%length，計(jì)算機(jī)中直接求余效率不如位移運(yùn)算。所以源碼中做了優(yōu)化,使用 hash&(length-1)，而實(shí)際上hash%length等于hash&(length-1)的前提是length是2的n次冪。

為什么這樣能均勻分布減少碰撞呢？2的n次方實(shí)際就是1后面n個(gè)0，2的n次方-1 實(shí)際就是n個(gè)1；

舉例：

說明：按位與運(yùn)算：相同的二進(jìn)制數(shù)位上，都是1的時(shí)候，結(jié)果為1，否則為零。

例如長(zhǎng)度為8時(shí)候，3&(8-1)=3  2&(8-1)=2 ，不同位置上，不碰撞；
例如長(zhǎng)度length為8時(shí)候，8是2的3次冪。二進(jìn)制是：1000
length-1 二進(jìn)制運(yùn)算：1000
-	   1
---------------------111
如下所示：
hash&(length-1)
3   &(8    - 1)=3  00000011  3 hash
&   00000111  7 length-1
---------------------00000011-----》3 數(shù)組下標(biāo)hash&(length-1)
2 &  (8 -    1) = 2  00000010  2 hash
&   00000111  7 length-1
---------------------00000010-----》2  數(shù)組下標(biāo)
說明：上述計(jì)算結(jié)果是不同位置上，不碰撞；

例如長(zhǎng)度為9時(shí)候，3&(9-1)=0  2&(9-1)=0 ，都在0上，碰撞了；
例如長(zhǎng)度length為9時(shí)候，9不是2的n次冪。二進(jìn)制是：00001001
length-1 二進(jìn)制運(yùn)算：1001
-	   1
---------------------1000
如下所示：
hash&(length-1)
3   &(9    - 1)=0  00000011  3 hash
&   00001000  8 length-1 
---------------------00000000-----》0  數(shù)組下標(biāo)hash&(length-1)
2 &  (9 -    1) = 2  00000010 2 hash
&   00001000 8 length-1 
---------------------00000000-----》0  數(shù)組下標(biāo)
說明：上述計(jì)算結(jié)果都在0上，碰撞了；

注意： 當(dāng)然如果不考慮效率直接求余即可（就不需要要求長(zhǎng)度必須是2的n次方了）

小結(jié)：

? 1.由上面可以看出，當(dāng)我們根據(jù)key的hash確定其在數(shù)組的位置時(shí)，如果n為2的冪次方，可以保證數(shù)據(jù)的均勻插入，如果n不是2的冪次方，可能數(shù)組的一些位置永遠(yuǎn)不會(huì)插入數(shù)據(jù)，浪費(fèi)數(shù)組的空間，加大hash沖突。

? 2.另一方面，一般我們可能會(huì)想通過 % 求余來確定位置，這樣也可以，只不過性能不如 & 運(yùn)算。而且當(dāng)n是2的冪次方時(shí)：hash & (length - 1) == hash % length

? 3.因此，HashMap 容量為2次冪的原因，就是為了數(shù)據(jù)的的均勻分布，減少hash沖突，畢竟hash沖突越大，代表數(shù)組中一個(gè)鏈的長(zhǎng)度越大，這樣的話會(huì)降低hashmap的性能

? 4.如果創(chuàng)建HashMap對(duì)象時(shí)，輸入的數(shù)組長(zhǎng)度是10，不是2的冪，HashMap通過一通位移運(yùn)算和或運(yùn)算得到的肯定是2的冪次數(shù)，并且是離那個(gè)數(shù)最近的數(shù)字。

源代碼如下：

//創(chuàng)建HashMap集合的對(duì)象，指定數(shù)組長(zhǎng)度是10，不是2的冪
HashMap hashMap = new HashMap(10);
public HashMap(int initialCapacity) {//initialCapacity=10this(initialCapacity, DEFAULT_LOAD_FACTOR);}
public HashMap(int initialCapacity, float loadFactor) {//initialCapacity=10if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10
}/*** Returns a power of two size for the given target capacity.*/static final int tableSizeFor(int cap) {//int cap = 10int 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;}

說明：

由此可以看到，當(dāng)在實(shí)例化HashMap實(shí)例時(shí)，如果給定了initialCapacity(假設(shè)是10)，由于HashMap的capacity必須都是2的冪，因此這個(gè)方法用于找到大于等于initialCapacity(假設(shè)是10)的最小的2的冪（initialCapacity如果就是2的冪，則返回的還是這個(gè)數(shù)）。
下面分析這個(gè)算法：

1. 首先，為什么要對(duì)cap做減1操作。int n = cap - 1;
   這是為了防止，cap已經(jīng)是2的冪。如果cap已經(jīng)是2的冪， 又沒有執(zhí)行這個(gè)減1操作，則執(zhí)行完后面的幾條無符號(hào)右移操作之后，返回的capacity將是這個(gè)cap的2倍。如果不懂，要看完后面的幾個(gè)無符號(hào)右移之后再回來看看。
   下面看看這幾個(gè)無符號(hào)右移操作：
2. 如果n這時(shí)為0了（經(jīng)過了cap-1之后），則經(jīng)過后面的幾次無符號(hào)右移依然是0，最后返回的capacity是 1（最后有個(gè)n+1的操作）。
   這里只討論n不等于0的情況。
3. 注意：|（按位或運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，都是0的時(shí)候，結(jié)果為0，否則為1。

? 第一次右移 ：

int n = cap - 1;//cap=10  n=9
n |= n >>> 1;00000000 00000000 00000000 00001001 //9
|	00000000 00000000 00000000 00000100 //9右移之后變?yōu)?
-------------------------------------------------00000000 00000000 00000000 00001101 //按位異或之后是13

由于n不等于0，則n的二進(jìn)制表示中總會(huì)有一bit為1，這時(shí)考慮最高位的1。通過無符號(hào)右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進(jìn)制表示中與最高位的1緊鄰的右邊一位也為1，如：

00000000 00000000 00000000 00001101

第二次右移 ：

 n |= n >>> 2;//n通過第一次右移變?yōu)榱?#xff1a;n=1300000000 00000000 00000000 00001101  // 13
|00000000 00000000 00000000 00000011  //13右移之后變?yōu)?
-------------------------------------------------00000000 00000000 00000000 00001111 //按位異或之后是15

注意，這個(gè)n已經(jīng)經(jīng)過了n |= n >>> 1; 操作。假設(shè)此時(shí)n為00000000 00000000 00000000 00001101 ，則n無符號(hào)右移兩位，會(huì)將最高位兩個(gè)連續(xù)的1右移兩位，然后再與原來的n做或操作，這樣n的二進(jìn)制表示的高位中會(huì)有4個(gè)連續(xù)的1。如：

00000000 00000000 00000000 00001111 //按位異或之后是15

第三次右移 :

n |= n >>> 4;//n通過第一、二次右移變?yōu)榱?#xff1a;n=1500000000 00000000 00000000 00001111  // 15
|00000000 00000000 00000000 00000000  //15右移之后變?yōu)?
-------------------------------------------------00000000 00000000 00000000 00001111 //按位異或之后是15

這次把已經(jīng)有的高位中的連續(xù)的4個(gè)1，右移4位，再做或操作，這樣n的二進(jìn)制表示的高位中正常會(huì)有8個(gè)連續(xù)的1。如00001111 1111xxxxxx 。
以此類推
注意，容量最大也就是32bit的正數(shù)，因此最后n |= n >>> 16; ，最多也就32個(gè)1（但是這已經(jīng)是負(fù)數(shù)了。在執(zhí)行tableSizeFor之前，對(duì)initialCapacity做了判斷，如果大于MAXIMUM_CAPACITY(2 ^ 30)，則取MAXIMUM_CAPACITY。如果等于MAXIMUM_CAPACITY(2 ^ 30)，會(huì)執(zhí)行移位操作。所以這里面的移位操作之后，最大30個(gè)1，不會(huì)大于等于MAXIMUM_CAPACITY。30個(gè)1，加1之后得2 ^ 30） 。
請(qǐng)看下面的一個(gè)完整例子：

注意，得到的這個(gè)capacity卻被賦值給了threshold。

this.threshold = tableSizeFor(initialCapacity);//initialCapacity=10

3.默認(rèn)的負(fù)載因子，默認(rèn)值是0.75

static final float DEFAULT_LOAD_FACTOR = 0.75f;

4.集合最大容量

//集合最大容量的上限是：2的30次冪
static final int MAXIMUM_CAPACITY = 1 << 30;

5.當(dāng)鏈表的值超過8則會(huì)轉(zhuǎn)紅黑樹

 //當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)大于這個(gè)值時(shí)會(huì)轉(zhuǎn)成紅黑樹static final int TREEIFY_THRESHOLD = 8;

問題：為什么Map桶中節(jié)點(diǎn)個(gè)數(shù)超過8才轉(zhuǎn)為紅黑樹？

8這個(gè)閾值定義在HashMap中，針對(duì)這個(gè)成員變量，在源碼的注釋中只說明了8是bin（bin就是bucket(桶)）從鏈表轉(zhuǎn)成樹的閾值，但是并沒有說明為什么是8：

在HashMap中有一段注釋說明： 我們繼續(xù)往下看 :

Because TreeNodes are about twice the size of regular nodes, we use them only when bins contain enough nodes to warrant use (see TREEIFY_THRESHOLD). And when they become too small (due to removal or resizing) they are converted back to plain bins.  In usages with well-distributed user hashCodes, tree bins are rarely used.  Ideally, under random hashCodes, the frequency of nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a parameter of about 0.5 on average for the default resizing threshold of 0.75, although with a large variance because of resizing granularity. Ignoring variance, the expected occurrences of list size k are (exp(-0.5)*pow(0.5, k)/factorial(k)).
The first values are:
因?yàn)闃涔?jié)點(diǎn)的大小大約是普通節(jié)點(diǎn)的兩倍，所以我們只在箱子包含足夠的節(jié)點(diǎn)時(shí)才使用樹節(jié)點(diǎn)(參見TREEIFY_THRESHOLD)。當(dāng)它們變得太小(由于刪除或調(diào)整大小)時(shí)，就會(huì)被轉(zhuǎn)換回普通的桶。在使用分布良好的用戶hashcode時(shí)，很少使用樹箱。理想情況下，在隨機(jī)哈希碼下，箱子中節(jié)點(diǎn)的頻率服從泊松分布
(http://en.wikipedia.org/wiki/Poisson_distribution)，默認(rèn)調(diào)整閾值為0.75，平均參數(shù)約為0.5，盡管由于調(diào)整粒度的差異很大。忽略方差，列表大小k的預(yù)期出現(xiàn)次數(shù)是(exp(-0.5)*pow(0.5, k)/factorial(k))。
第一個(gè)值是:0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

TreeNodes占用空間是普通Nodes的兩倍，所以只有當(dāng)bin包含足夠多的節(jié)點(diǎn)時(shí)才會(huì)轉(zhuǎn)成TreeNodes，而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當(dāng)bin中節(jié)點(diǎn)數(shù)變少時(shí)，又會(huì)轉(zhuǎn)成普通的bin。并且我們查看源碼的時(shí)候發(fā)現(xiàn)，鏈表長(zhǎng)度達(dá)到8就轉(zhuǎn)成紅黑樹，當(dāng)長(zhǎng)度降到6就轉(zhuǎn)成普通bin。

這樣就解釋了為什么不是一開始就將其轉(zhuǎn)換為TreeNodes，而是需要一定節(jié)點(diǎn)數(shù)才轉(zhuǎn)為TreeNodes，說白了就是權(quán)衡，空間和時(shí)間的權(quán)衡。

這段內(nèi)容還說到：當(dāng)hashCode離散性很好的時(shí)候，樹型bin用到的概率非常小，因?yàn)閿?shù)據(jù)均勻分布在每個(gè)bin中，幾乎不會(huì)有bin中鏈表長(zhǎng)度會(huì)達(dá)到閾值。但是在隨機(jī)hashCode下，離散性可能會(huì)變差，然而JDK又不能阻止用戶實(shí)現(xiàn)這種不好的hash算法，因此就可能導(dǎo)致不均勻的數(shù)據(jù)分布。不過理想情況下隨機(jī)hashCode算法下所有bin中節(jié)點(diǎn)的分布頻率會(huì)遵循泊松分布，我們可以看到，一個(gè)bin中鏈表長(zhǎng)度達(dá)到8個(gè)元素的概率為0.00000006，幾乎是不可能事件。所以，之所以選擇8，不是隨便決定的，而是根據(jù)概率統(tǒng)計(jì)決定的。由此可見，發(fā)展將近30年的Java每一項(xiàng)改動(dòng)和優(yōu)化都是非常嚴(yán)謹(jǐn)和科學(xué)的。

也就是說：選擇8因?yàn)榉喜此煞植?#xff0c;超過8的時(shí)候，概率已經(jīng)非常小了，所以我們選擇8這個(gè)數(shù)字。

補(bǔ)充：

1）.

 Poisson分布(泊松分布)，是一種統(tǒng)計(jì)與概率學(xué)里常見到的離散[概率分布]。
泊松分布的概率函數(shù)為：

 泊松分布的參數(shù)λ是單位時(shí)間(或單位面積)內(nèi)隨機(jī)事件的平均發(fā)生次數(shù)。 泊松分布適合于描述單位時(shí)間內(nèi)隨機(jī)事件發(fā)生的次數(shù)。

2）.以下是一些資料上面翻看到的解釋：供大家參考：

紅黑樹的平均查找長(zhǎng)度是log(n)，如果長(zhǎng)度為8，平均查找長(zhǎng)度為log(8)=3，鏈表的平均查找長(zhǎng)度為n/2，當(dāng)長(zhǎng)度為8時(shí)，平均查找長(zhǎng)度為8/2=4，這才有轉(zhuǎn)換成樹的必要；鏈表長(zhǎng)度如果是小于等于6，6/2=3，而log(6)=2.6，雖然速度也很快的，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時(shí)間并不會(huì)太短。

6.當(dāng)鏈表的值小于6則會(huì)從紅黑樹轉(zhuǎn)回鏈表

 //當(dāng)桶(bucket)上的結(jié)點(diǎn)數(shù)小于這個(gè)值時(shí)樹轉(zhuǎn)鏈表static final int UNTREEIFY_THRESHOLD = 6;

7.當(dāng)Map里面的數(shù)量超過這個(gè)值時(shí)，表中的桶才能進(jìn)行樹形化 ，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，而不是樹形化 為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD (8)

//桶中結(jié)構(gòu)轉(zhuǎn)化為紅黑樹對(duì)應(yīng)的數(shù)組長(zhǎng)度最小的值 
static final int MIN_TREEIFY_CAPACITY = 64;

8、table用來初始化(必須是二的n次冪)(重點(diǎn))

//存儲(chǔ)元素的數(shù)組 
transient Node<K,V>[] table;

table在JDK1.8中我們了解到HashMap是由數(shù)組加鏈表加紅黑樹來組成的結(jié)構(gòu)其中table就是HashMap中的數(shù)組，jdk8之前數(shù)組類型是Entry<K,V>類型。從jdk1.8之后是Node<K,V>類型。只是換了個(gè)名字，都實(shí)現(xiàn)了一樣的接口：Map.Entry<K,V>。負(fù)責(zé)存儲(chǔ)鍵值對(duì)數(shù)據(jù)的。

9、用來存放緩存

//存放具體元素的集合
transient Set<Map.Entry<K,V>> entrySet;

10、 HashMap中存放元素的個(gè)數(shù)(重點(diǎn))

//存放元素的個(gè)數(shù)，注意這個(gè)不等于數(shù)組的長(zhǎng)度。transient int size;

size為HashMap中K-V的實(shí)時(shí)數(shù)量，不是數(shù)組table的長(zhǎng)度。

11、 用來記錄HashMap的修改次數(shù)

// 每次擴(kuò)容和更改map結(jié)構(gòu)的計(jì)數(shù)器transient int modCount;  

12、 用來調(diào)整大小下一個(gè)容量的值計(jì)算方式為(容量*負(fù)載因子)

// 臨界值 當(dāng)實(shí)際大小(容量*負(fù)載因子)超過臨界值時(shí)，會(huì)進(jìn)行擴(kuò)容
int threshold;

13、 哈希表的加載因子(重點(diǎn))

// 加載因子
final float loadFactor;

說明：

1.loadFactor加載因子，是用來衡量 HashMap 滿的程度，表示HashMap的疏密程度，影響hash操作到同一個(gè)數(shù)組位置的概率，計(jì)算HashMap的實(shí)時(shí)加載因子的方法為：size/capacity，而不是占用桶的數(shù)量去除以capacity。capacity 是桶的數(shù)量，也就是 table 的長(zhǎng)度length。

loadFactor太大導(dǎo)致查找元素效率低，太小導(dǎo)致數(shù)組的利用率低，存放的數(shù)據(jù)會(huì)很分散。loadFactor的默認(rèn)值為0.75f是官方給出的一個(gè)比較好的臨界值。

當(dāng)HashMap里面容納的元素已經(jīng)達(dá)到HashMap數(shù)組長(zhǎng)度的75%時(shí)，表示HashMap太擠了，需要擴(kuò)容，而擴(kuò)容這個(gè)過程涉及到 rehash、復(fù)制數(shù)據(jù)等操作，非常消耗性能。，所以開發(fā)中盡量減少擴(kuò)容的次數(shù)，可以通過創(chuàng)建HashMap集合對(duì)象時(shí)指定初始容量來盡量避免。

同時(shí)在HashMap的構(gòu)造器中可以定制loadFactor。

構(gòu)造方法：
HashMap(int initialCapacity, float loadFactor) 構(gòu)造一個(gè)帶指定初始容量和加載因子的空 HashMap。

2.為什么加載因子設(shè)置為0.75,初始化臨界值是12？

loadFactor越趨近于1，那么 數(shù)組中存放的數(shù)據(jù)(entry)也就越多，也就越密，也就是會(huì)讓鏈表的長(zhǎng)度增加，loadFactor越小，也就是趨近于0，數(shù)組中存放的數(shù)據(jù)(entry)也就越少，也就越稀疏。

如果希望鏈表盡可能少些。要提前擴(kuò)容，有的數(shù)組空間有可能一直沒有存儲(chǔ)數(shù)據(jù)。加載因子盡可能小一些。

舉例：

例如：加載因子是0.4。 那么16*0.4--->6 如果數(shù)組中滿6個(gè)空間就擴(kuò)容會(huì)造成數(shù)組利用率太低了。加載因子是0.9。 那么16*0.9---->14 那么這樣就會(huì)導(dǎo)致鏈表有點(diǎn)多了。導(dǎo)致查找元素效率低。

所以既兼顧數(shù)組利用率又考慮鏈表不要太多，經(jīng)過大量測(cè)試0.75是最佳方案。

• threshold計(jì)算公式：capacity(數(shù)組長(zhǎng)度默認(rèn)16) * loadFactor(負(fù)載因子默認(rèn)0.75)。這個(gè)值是當(dāng)前已占用數(shù)組長(zhǎng)度的最大值。當(dāng)Size>=threshold的時(shí)候，那么就要考慮對(duì)數(shù)組的resize(擴(kuò)容)，也就是說，這個(gè)的意思就是 衡量數(shù)組是否需要擴(kuò)增的一個(gè)標(biāo)準(zhǔn)。 擴(kuò)容后的 HashMap 容量是之前容量的兩倍.

5.構(gòu)造方法

HashMap 中重要的構(gòu)造方法，它們分別如下：

1、構(gòu)造一個(gè)空的 HashMap ，默認(rèn)初始容量（16）和默認(rèn)負(fù)載因子（0.75）。

public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // 將默認(rèn)的加載因子0.75賦值給loadFactor，并沒有創(chuàng)建數(shù)組
}

2、 構(gòu)造一個(gè)具有指定的初始容量和默認(rèn)負(fù)載因子（0.75） HashMap。

 // 指定“容量大小”的構(gòu)造函數(shù)public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}

3、 構(gòu)造一個(gè)具有指定的初始容量和負(fù)載因子的 HashMap。我們來分析一下。

/*指定“容量大小”和“加載因子”的構(gòu)造函數(shù)initialCapacity: 指定的容量loadFactor:指定的加載因子
*/
public HashMap(int initialCapacity, float loadFactor) {//判斷初始化容量initialCapacity是否小于0if (initialCapacity < 0)//如果小于0，則拋出非法的參數(shù)異常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);//判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪if (initialCapacity > MAXIMUM_CAPACITY)//如果超過MAXIMUM_CAPACITY，會(huì)將MAXIMUM_CAPACITY賦值給initialCapacityinitialCapacity = MAXIMUM_CAPACITY;//判斷負(fù)載因子loadFactor是否小于等于0或者是否是一個(gè)非數(shù)值if (loadFactor <= 0 || Float.isNaN(loadFactor))//如果滿足上述其中之一，則拋出非法的參數(shù)異常IllegalArgumentExceptionthrow new IllegalArgumentException("Illegal load factor: " +loadFactor);//將指定的加載因子賦值給HashMap成員變量的負(fù)載因子loadFactorthis.loadFactor = loadFactor;/*tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會(huì)變?yōu)楸戎?		定初始化容量大的最小的2的n次冪。這點(diǎn)上述已經(jīng)講解過。但是注意，在tableSizeFor方法體內(nèi)部將計(jì)算后的數(shù)據(jù)返回給調(diào)用這里了，并且直接賦值給threshold邊			界值了。有些人會(huì)覺得這里是一個(gè)bug,應(yīng)該這樣書寫：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;這樣才符合threshold的意思（當(dāng)HashMap的size到達(dá)threshold這個(gè)閾值時(shí)會(huì)擴(kuò)容）。但是，請(qǐng)注意，在jdk8以后的構(gòu)造方法中，并沒有對(duì)table這個(gè)成員變量進(jìn)行初始化，table的初始化被推			 遲到了put方法中，在put方法中會(huì)對(duì)threshold重新計(jì)算，put方法的具體實(shí)現(xiàn)我們下面會(huì)進(jìn)行講解*/this.threshold = tableSizeFor(initialCapacity);}
最后調(diào)用了tableSizeFor，來看一下方法實(shí)現(xiàn)：/*** Returns a power of two size for the given target capacity.返回比指定初始化容量大的最小的2的n次冪*/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;}

說明：

對(duì)于 this.threshold = tableSizeFor(initialCapacity); 疑問解答：

tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會(huì)變?yōu)楸戎付ǔ跏蓟萘看蟮淖钚〉?的n次冪。這點(diǎn)上述已經(jīng)講解過。
但是注意，在tableSizeFor方法體內(nèi)部將計(jì)算后的數(shù)據(jù)返回給調(diào)用這里了，并且直接賦值給threshold邊界值了。有些人會(huì)覺得這里是一個(gè)bug,應(yīng)該這樣書寫：
this.threshold = tableSizeFor(initialCapacity) * this.loadFactor;
這樣才符合threshold的意思（當(dāng)HashMap的size到達(dá)threshold這個(gè)閾值時(shí)會(huì)擴(kuò)容）。
但是，請(qǐng)注意，在jdk8以后的構(gòu)造方法中，并沒有對(duì)table這個(gè)成員變量進(jìn)行初始化，table的初始化被推遲到了put方法中，在put方法中會(huì)對(duì)threshold重新計(jì)算，put方法的具體實(shí)現(xiàn)我們下面會(huì)進(jìn)行講解

4、包含另一個(gè)“Map”的構(gòu)造函數(shù)

//構(gòu)造一個(gè)映射關(guān)系與指定 Map 相同的新 HashMap。
public HashMap(Map<? extends K, ? extends V> m) {//負(fù)載因子loadFactor變?yōu)槟J(rèn)的負(fù)載因子0.75this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}

最后調(diào)用了putMapEntries，來看一下方法實(shí)現(xiàn)：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {//獲取參數(shù)集合的長(zhǎng)度int s = m.size();if (s > 0){//判斷參數(shù)集合的長(zhǎng)度是否大于0，說明大于0if (table == null)  // 判斷table是否已經(jīng)初始化{ // pre-size// 未初始化，s為m的實(shí)際元素個(gè)數(shù)float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);// 計(jì)算得到的t大于閾值，則初始化閾值if (t > threshold)threshold = tableSizeFor(t);}// 已初始化，并且m元素個(gè)數(shù)大于閾值，進(jìn)行擴(kuò)容處理else if (s > threshold)resize();// 將m中的所有元素添加至HashMap中for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}
}

注意：

float ft = ((float)s / loadFactor) + 1.0F;這一行代碼中為什么要加1.0F ？

s/loadFactor的結(jié)果是小數(shù)，加1.0F與(int)ft相當(dāng)于是對(duì)小數(shù)做一個(gè)向上取整以盡可能的保證更大容量，更大的容量能夠減少resize的調(diào)用次數(shù)。所以 + 1.0F是為了獲取更大的容量。

例如：原來集合的元素個(gè)數(shù)是6個(gè)，那么6/0.75是8，是2的n次冪，那么新的數(shù)組大小就是8了。然后原來數(shù)組的數(shù)據(jù)就會(huì)存儲(chǔ)到長(zhǎng)度是8的新的數(shù)組中了，這樣會(huì)導(dǎo)致在存儲(chǔ)元素的時(shí)候，容量不夠，還得繼續(xù)擴(kuò)容，那么性能降低了，而如果+1呢，數(shù)組長(zhǎng)度直接變?yōu)?6了，這樣可以減少數(shù)組的擴(kuò)容。

6.成員方法

6.1增加方法

put方法是比較復(fù)雜的，實(shí)現(xiàn)步驟大致如下：

1）先通過hash值計(jì)算出key映射到哪個(gè)桶；

2）如果桶上沒有碰撞沖突，則直接插入；

3）如果出現(xiàn)碰撞沖突了，則需要處理沖突：

? a:如果該桶使用紅黑樹處理沖突，則調(diào)用紅黑樹的方法插入數(shù)據(jù)；

? b:否則采用傳統(tǒng)的鏈?zhǔn)椒椒ú迦搿Ｈ绻湹拈L(zhǎng)度達(dá)到臨界值，則把鏈轉(zhuǎn)變?yōu)榧t黑樹；

4）如果桶中存在重復(fù)的鍵，則為該鍵替換新值value；

5）如果size大于閾值threshold，則進(jìn)行擴(kuò)容；

具體的方法如下：

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}

說明：

? 1）HashMap只提供了put用于添加元素，putVal方法只是給put方法調(diào)用的一個(gè)方法，并沒有提供給用戶使用。 所以我們重點(diǎn)看putVal方法。

2）我們可以看到在putVal()方法中key在這里執(zhí)行了一下hash()方法,來看一下Hash方法是如何實(shí)現(xiàn)的。 

 static final int hash(Object key) {int h;/*1）如果key等于null：可以看到當(dāng)key等于null的時(shí)候也是有哈希值的，返回的是0.2）如果key不等于null：首先計(jì)算出key的hashCode賦值給h,然后與h無符號(hào)右移16位后的二進(jìn)制進(jìn)行按位異或得到最后的					hash值*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

從上面可以得知HashMap是支持Key為空的，而HashTable是直接用Key來獲取HashCode所以key為空會(huì)拋異常。

{其實(shí)上面就已經(jīng)解釋了為什么HashMap的長(zhǎng)度為什么要是2的冪因?yàn)镠ashMap 使用的方法很巧妙，它通過 hash & (table.length -1)來得到該對(duì)象的保存位，前面說過 HashMap 底層數(shù)組的長(zhǎng)度總是2的n次方，這是HashMap在速度上的優(yōu)化。當(dāng) length 總是2的n次方時(shí)，hash & (length-1)運(yùn)算等價(jià)于對(duì) length 取模，也就是hash%length，但是&比%具有更高的效率。比如 n % 32 = n & (32 -1)。}

解讀上述hash方法：

我們先研究下key的哈希值是如何計(jì)算出來的。key的哈希值是通過上述方法計(jì)算出來的。

這個(gè)哈希方法首先計(jì)算出key的hashCode賦值給h,然后與h無符號(hào)右移16位后的二進(jìn)制進(jìn)行按位異或得到最后的 hash值。計(jì)算過程如下所示：

 static final int hash(Object key) {int h;/*1）如果key等于null：可以看到當(dāng)key等于null的時(shí)候也是有哈希值的，返回的是0.2）如果key不等于null：首先計(jì)算出key的hashCode賦值給h,然后與h無符號(hào)右移16位后的二進(jìn)制進(jìn)行按位異或得到最后的					hash值*/return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

在putVal函數(shù)中使用到了上述hash函數(shù)計(jì)算的哈希值：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {。。。。。。。。。。。。。。if ((p = tab[i = (n - 1) & hash]) == null)//這里的n表示數(shù)組長(zhǎng)度16。。。。。。。。。。。。。。}

計(jì)算過程如下所示：

? 說明：

? 1）key.hashCode()；返回散列值也就是hashcode。假設(shè)隨便生成的一個(gè)值。

? 2）n表示數(shù)組初始化的長(zhǎng)度是16

? 3）&（按位與運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，都是1的時(shí)候，結(jié)果為1，否則為零。

? 4）^（按位異或運(yùn)算）：運(yùn)算規(guī)則：相同的二進(jìn)制數(shù)位上，數(shù)字相同，結(jié)果為0，不同為1。

簡(jiǎn)單來說就是：

• 高16 bit 不變，低16 bit 和高16 bit 做了一個(gè)異或（得到的 hashcode 轉(zhuǎn)化為32位二進(jìn)制，前16位和后16位低16 bit和高16 bit做了一個(gè)異或）

  問題：為什么要這樣操作呢？

  如果當(dāng)n即數(shù)組長(zhǎng)度很小，假設(shè)是16的話，那么n-1即為 —》1111 ，這樣的值和hashCode()直接做按位與操作，實(shí)際上只使用了哈希值的后4位。如果當(dāng)哈希值的高位變化很大，低位變化很小，這樣就很容易造成哈希沖突了，所以這里把高低位都利用起來，從而解決了這個(gè)問題。

  例如上述：
  hashCode()值：     1111 1111 1111 1111 1111 0000 1110 1010&
  n-1即16-1--》15：  。。。。。。。。。。。。。。。。。。。。。。1111
  -------------------------------------------------------------------0000 0000 0000 0000 0000 0000 0000 1010 ----》10作為索引
  其實(shí)就是將hashCode值作為數(shù)組索引，那么如果下個(gè)高位hashCode不一致，低位一致的話，就會(huì)造成計(jì)算的索引還是10,從而造成了哈希沖突了。降低性能。
  

• (n-1) & hash = -> 得到下標(biāo) (n-1) n表示數(shù)組長(zhǎng)度16，n-1就是15

• 取余數(shù)本質(zhì)是不斷做除法，把剩余的數(shù)減去，運(yùn)算效率要比位運(yùn)算低。

現(xiàn)在看putVal()方法，看看它到底做了什么。

主要參數(shù)：

• hash key的hash值
• key 原始Key
• value 要存放的值
• onlyIfAbsent 如果true代表不更改現(xiàn)有的值
• evict 如果為false表示table為創(chuàng)建狀態(tài)

putVal()方法源代碼如下所示：

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<K,V>[] tab; Node<K,V> p; int n, i;/*1）transient Node<K,V>[] table; 表示存儲(chǔ)Map集合中元素的數(shù)組。2）(tab = table) == null 表示將空的table賦值給tab,然后判斷tab是否等于null，第一次肯定是			null3）(n = tab.length) == 0 表示將數(shù)組的長(zhǎng)度0賦值給n,然后判斷n是否等于0，n等于0由于if判斷使用雙或，滿足一個(gè)即可，則執(zhí)行代碼 n = (tab = resize()).length; 進(jìn)行數(shù)組初始化。并將初始化好的數(shù)組長(zhǎng)度賦值給n.4）執(zhí)行完n = (tab = resize()).length，數(shù)組tab每個(gè)空間都是null*/if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;/*1）i = (n - 1) & hash 表示計(jì)算數(shù)組的索引賦值給i，即確定元素存放在哪個(gè)桶中2）p = tab[i = (n - 1) & hash]表示獲取計(jì)算出的位置的數(shù)據(jù)賦值給節(jié)點(diǎn)p3) (p = tab[i = (n - 1) & hash]) == null 判斷節(jié)點(diǎn)位置是否等于null，如果為null，則執(zhí)行代			碼：tab[i] = newNode(hash, key, value, null);根據(jù)鍵值對(duì)創(chuàng)建新的節(jié)點(diǎn)放入該位置的桶中小結(jié)：如果當(dāng)前桶沒有哈希碰撞沖突，則直接把鍵值對(duì)插入空間位置*/ if ((p = tab[i = (n - 1) & hash]) == null)//創(chuàng)建一個(gè)新的節(jié)點(diǎn)存入到桶中tab[i] = newNode(hash, key, value, null);else {// 執(zhí)行else說明tab[i]不等于null，表示這個(gè)位置已經(jīng)有值了。Node<K,V> e; K k;/*比較桶中第一個(gè)元素(數(shù)組中的結(jié)點(diǎn))的hash值和key是否相等1）p.hash == hash ：p.hash表示原來存在數(shù)據(jù)的hash值  hash表示后添加數(shù)據(jù)的hash值 比較兩個(gè)				 hash值是否相等說明：p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node對(duì)象。Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}而在Node類中具有成員變量hash用來記錄著之前數(shù)據(jù)的hash值的2）(k = p.key) == key ：p.key獲取原來數(shù)據(jù)的key賦值給k  key 表示后添加數(shù)據(jù)的key 比較兩					個(gè)key的地址值是否相等3）key != null && key.equals(k)：能夠執(zhí)行到這里說明兩個(gè)key的地址值不相等，那么先判斷后				添加的key是否等于null，如果不等于null再調(diào)用equals方法判斷兩個(gè)key的內(nèi)容是否相等*/if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))/*說明：兩個(gè)元素哈希值相等，并且key的值也相等將舊的元素整體對(duì)象賦值給e，用e來記錄*/ e = p;// hash值不相等或者key不相等；判斷p是否為紅黑樹結(jié)點(diǎn)else if (p instanceof TreeNode)// 放入樹中e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 說明是鏈表節(jié)點(diǎn)else {/*1)如果是鏈表的話需要遍歷到最后節(jié)點(diǎn)然后插入2)采用循環(huán)遍歷的方式，判斷鏈表中是否有重復(fù)的key*/for (int binCount = 0; ; ++binCount) {/*1)e = p.next 獲取p的下一個(gè)元素賦值給e2)(e = p.next) == null 判斷p.next是否等于null，等于null，說明p沒有下一個(gè)元					素，那么此時(shí)到達(dá)了鏈表的尾部，還沒有找到重復(fù)的key,則說明HashMap沒有包含該鍵將該鍵值對(duì)插入鏈表中*/if ((e = p.next) == null) {/*1）創(chuàng)建一個(gè)新的節(jié)點(diǎn)插入到尾部p.next = newNode(hash, key, value, null);Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {return new Node<>(hash, key, value, next);}注意第四個(gè)參數(shù)next是null，因?yàn)楫?dāng)前元素插入到鏈表末尾了，那么下一個(gè)節(jié)點(diǎn)肯定是								null2）這種添加方式也滿足鏈表數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，每次向后添加新的元素*/p.next = newNode(hash, key, value, null);/*1)節(jié)點(diǎn)添加完成之后判斷此時(shí)節(jié)點(diǎn)個(gè)數(shù)是否大于TREEIFY_THRESHOLD臨界值8，如果大于則將鏈表轉(zhuǎn)換為紅黑樹2）int binCount = 0 ：表示for循環(huán)的初始化值。從0開始計(jì)數(shù)。記錄著遍歷節(jié)點(diǎn)的個(gè)						數(shù)。值是0表示第一個(gè)節(jié)點(diǎn)，1表示第二個(gè)節(jié)點(diǎn)。。。。7表示第八個(gè)節(jié)點(diǎn)，加上數(shù)組中的的一						個(gè)元素，元素個(gè)數(shù)是9TREEIFY_THRESHOLD - 1 --》8 - 1 ---》7如果binCount的值是7(加上數(shù)組中的的一個(gè)元素，元素個(gè)數(shù)是9)TREEIFY_THRESHOLD - 1也是7，此時(shí)轉(zhuǎn)換紅黑樹*/if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//轉(zhuǎn)換為紅黑樹treeifyBin(tab, hash);// 跳出循環(huán)break;}/*執(zhí)行到這里說明e = p.next 不是null，不是最后一個(gè)元素。繼續(xù)判斷鏈表中結(jié)點(diǎn)的key值與插					  入的元素的key值是否相等*/if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等，跳出循環(huán)/*要添加的元素和鏈表中的存在的元素的key相等了，則跳出for循環(huán)。不用再繼續(xù)比較了直接執(zhí)行下面的if語句去替換去 if (e != null) */break;/*說明新添加的元素和當(dāng)前節(jié)點(diǎn)不相等，繼續(xù)查找下一個(gè)節(jié)點(diǎn)。用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表*/p = e;}}/*表示在桶中找到key值、hash值與插入元素相等的結(jié)點(diǎn)也就是說通過上面的操作找到了重復(fù)的鍵，所以這里就是把該鍵的值變?yōu)樾碌闹?#xff0c;并返回舊值這里完成了put方法的修改功能*/if (e != null) { // 記錄e的valueV oldValue = e.value;// onlyIfAbsent為false或者舊值為nullif (!onlyIfAbsent || oldValue == null)//用新值替換舊值//e.value 表示舊值  value表示新值 e.value = value;// 訪問后回調(diào)afterNodeAccess(e);// 返回舊值return oldValue;}}//修改記錄次數(shù)++modCount;// 判斷實(shí)際大小是否大于threshold閾值，如果超過則擴(kuò)容if (++size > threshold)resize();// 插入后回調(diào)afterNodeInsertion(evict);return null;
} 

6.2將鏈表轉(zhuǎn)換為紅黑樹的treeifyBin方法

節(jié)點(diǎn)添加完成之后判斷此時(shí)節(jié)點(diǎn)個(gè)數(shù)是否大于TREEIFY_THRESHOLD臨界值8，如果大于則將鏈表轉(zhuǎn)換為紅黑樹，轉(zhuǎn)換紅黑樹的方法 treeifyBin，整體代碼如下：

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//轉(zhuǎn)換為紅黑樹 tab表示數(shù)組名  hash表示哈希值treeifyBin(tab, hash);

treeifyBin方法如下所示：

  /*** Replaces all linked nodes in bin at index for given hash unless* table is too small, in which case resizes instead.替換指定哈希表的索引處桶中的所有鏈接節(jié)點(diǎn)，除非表太小，否則將修改大小。Node<K,V>[] tab = tab 數(shù)組名int hash = hash表示哈希值*/final void treeifyBin(Node<K,V>[] tab, int hash) {int n, index; Node<K,V> e;/*如果當(dāng)前數(shù)組為空或者數(shù)組的長(zhǎng)度小于進(jìn)行樹形化的閾值(MIN_TREEIFY_CAPACITY = 64),就去擴(kuò)容。而不是將節(jié)點(diǎn)變?yōu)榧t黑樹。目的：如果數(shù)組很小，那么轉(zhuǎn)換紅黑樹，然后遍歷效率要低一些。這時(shí)進(jìn)行擴(kuò)容，那么重新計(jì)算哈希值，鏈表長(zhǎng)度有可能就變短了，數(shù)據(jù)會(huì)放到數(shù)組中，這樣相對(duì)來說效率高一些。*/if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)//擴(kuò)容方法resize();else if ((e = tab[index = (n - 1) & hash]) != null) {/*1）執(zhí)行到這里說明哈希表中的數(shù)組長(zhǎng)度大于閾值64，開始進(jìn)行樹形化2）e = tab[index = (n - 1) & hash]表示將數(shù)組中的元素取出賦值給e,e是哈希表中指定位					置桶里的鏈表節(jié)點(diǎn)，從第一個(gè)開始*///hd：紅黑樹的頭結(jié)點(diǎn)   tl :紅黑樹的尾結(jié)點(diǎn)TreeNode<K,V> hd = null, tl = null;do {//新創(chuàng)建一個(gè)樹的節(jié)點(diǎn)，內(nèi)容和當(dāng)前鏈表節(jié)點(diǎn)e一致TreeNode<K,V> p = replacementTreeNode(e, null);if (tl == null)//將新創(chuàng)鍵的p節(jié)點(diǎn)賦值給紅黑樹的頭結(jié)點(diǎn)hd = p;else {/*p.prev = tl：將上一個(gè)節(jié)點(diǎn)p賦值給現(xiàn)在的p的前一個(gè)節(jié)點(diǎn)tl.next = p;將現(xiàn)在節(jié)點(diǎn)p作為樹的尾結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)*/p.prev = tl;tl.next = p;}tl = p;/*e = e.next 將當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)賦值給e,如果下一個(gè)節(jié)點(diǎn)不等于null則回到上面繼續(xù)取出鏈表中節(jié)點(diǎn)轉(zhuǎn)換為紅黑樹*/} while ((e = e.next) != null);/*讓桶中的第一個(gè)元素即數(shù)組中的元素指向新建的紅黑樹的節(jié)點(diǎn)，以后這個(gè)桶里的元素就是紅黑樹而不是鏈表數(shù)據(jù)結(jié)構(gòu)了*/if ((tab[index] = hd) != null)hd.treeify(tab);}}

小結(jié)：上述操作一共做了如下幾件事：

1.根據(jù)哈希表中元素個(gè)數(shù)確定是擴(kuò)容還是樹形化

2.如果是樹形化遍歷桶中的元素，創(chuàng)建相同個(gè)數(shù)的樹形節(jié)點(diǎn)，復(fù)制內(nèi)容，建立起聯(lián)系

3.然后讓桶中的第一個(gè)元素指向新創(chuàng)建的樹根節(jié)點(diǎn)，替換桶的鏈表內(nèi)容為樹形化內(nèi)容

6.3擴(kuò)容方法_resize

6.3.1擴(kuò)容機(jī)制

想要了解HashMap的擴(kuò)容機(jī)制你要有這兩個(gè)問題

• 1.什么時(shí)候才需要擴(kuò)容
• 2.HashMap的擴(kuò)容是什么

1.什么時(shí)候才需要擴(kuò)容

當(dāng)HashMap中的元素個(gè)數(shù)超過數(shù)組大小(數(shù)組長(zhǎng)度)*loadFactor(負(fù)載因子)時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容，loadFactor的默認(rèn)值(DEFAULT_LOAD_FACTOR)是0.75,這是一個(gè)折中的取值。也就是說，默認(rèn)情況下，數(shù)組大小為16，那么當(dāng)HashMap中的元素個(gè)數(shù)超過16×0.75=12(這個(gè)值就是閾值或者邊界值threshold值)的時(shí)候，就把數(shù)組的大小擴(kuò)展為2×16=32，即擴(kuò)大一倍，然后重新計(jì)算每個(gè)元素在數(shù)組中的位置，而這是一個(gè)非常耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)知元素的個(gè)數(shù)能夠有效的提高HashMap的性能。

補(bǔ)充：

當(dāng)HashMap中的其中一個(gè)鏈表的對(duì)象個(gè)數(shù)如果達(dá)到了8個(gè)，此時(shí)如果數(shù)組長(zhǎng)度沒有達(dá)到64，那么HashMap會(huì)先擴(kuò)容解決，如果已經(jīng)達(dá)到了64，那么這個(gè)鏈表會(huì)變成紅黑樹，節(jié)點(diǎn)類型由Node變成TreeNode類型。當(dāng)然，如果映射關(guān)系被移除后，下次執(zhí)行resize方法時(shí)判斷樹的節(jié)點(diǎn)個(gè)數(shù)低于6，也會(huì)再把樹轉(zhuǎn)換為鏈表。

2.HashMap的擴(kuò)容是什么

進(jìn)行擴(kuò)容，會(huì)伴隨著一次重新hash分配，并且會(huì)遍歷hash表中所有的元素，是非常耗時(shí)的。在編寫程序中，要盡量避免resize。

HashMap在進(jìn)行擴(kuò)容時(shí)，使用的rehash方式非常巧妙，因?yàn)槊看螖U(kuò)容都是翻倍，與原來計(jì)算的 (n-1)&hash的結(jié)果相比，只是多了一個(gè)bit位，所以節(jié)點(diǎn)要么就在原來的位置，要么就被分配到"原位置+舊容量"這個(gè)位置。

怎么理解呢？例如我們從16擴(kuò)展為32時(shí)，具體的變化如下所示：

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

說明：5是假設(shè)計(jì)算出來的原來的索引。這樣就驗(yàn)證了上述所描述的：擴(kuò)容之后所以節(jié)點(diǎn)要么就在原來的位置，要么就被分配到"原位置+舊容量"這個(gè)位置。

因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要重新計(jì)算hash，只需要看看原來的hash值新增的那個(gè)bit是1還是0就可以了，是0的話索引沒變，是1的話索引變成“原索引+oldCap(原位置+舊容量)”。可以看看下圖為16擴(kuò)充為32的resize示意圖：

正是因?yàn)檫@樣巧妙的rehash方式，既省去了重新計(jì)算hash值的時(shí)間，而且同時(shí)，由于新增的1bit是0還是1可以認(rèn)為是隨機(jī)的，在resize的過程中保證了rehash之后每個(gè)桶上的節(jié)點(diǎn)數(shù)一定小于等于原來桶上的節(jié)點(diǎn)數(shù)，保證了rehash之后不會(huì)出現(xiàn)更嚴(yán)重的hash沖突，均勻的把之前的沖突的節(jié)點(diǎn)分散到新的桶中了。

6.3.2源碼resize方法的解讀

下面是代碼的具體實(shí)現(xiàn)：

final Node<K,V>[] resize() {//得到當(dāng)前數(shù)組Node<K,V>[] oldTab = table;//如果當(dāng)前數(shù)組等于null長(zhǎng)度返回0，否則返回當(dāng)前數(shù)組的長(zhǎng)度int oldCap = (oldTab == null) ? 0 : oldTab.length;//當(dāng)前閥值點(diǎn) 默認(rèn)是12(16*0.75)int oldThr = threshold;int newCap, newThr = 0;//如果老的數(shù)組長(zhǎng)度大于0//開始計(jì)算擴(kuò)容后的大小if (oldCap > 0) {// 超過最大值就不再擴(kuò)充了，就只好隨你碰撞去吧if (oldCap >= MAXIMUM_CAPACITY) {//修改閾值為int的最大值threshold = Integer.MAX_VALUE;return oldTab;}/*沒超過最大值，就擴(kuò)充為原來的2倍1)(newCap = oldCap << 1) < MAXIMUM_CAPACITY 擴(kuò)大到2倍之后容量要小于最大容量2）oldCap >= DEFAULT_INITIAL_CAPACITY 原數(shù)組長(zhǎng)度大于等于數(shù)組初始化長(zhǎng)度16*/else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)//閾值擴(kuò)大一倍newThr = oldThr << 1; // double threshold}//老閾值點(diǎn)大于0 直接賦值else if (oldThr > 0) // 老閾值賦值給新的數(shù)組長(zhǎng)度newCap = oldThr;else {// 直接使用默認(rèn)值newCap = DEFAULT_INITIAL_CAPACITY;//16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 計(jì)算新的resize最大上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}//新的閥值 默認(rèn)原來是12 乘以2之后變?yōu)?4threshold = newThr;//創(chuàng)建新的哈希表@SuppressWarnings({"rawtypes","unchecked"})//newCap是新的數(shù)組長(zhǎng)度--》32Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//判斷舊數(shù)組是否等于空if (oldTab != null) {// 把每個(gè)bucket都移動(dòng)到新的buckets中//遍歷舊的哈希表的每個(gè)桶，重新計(jì)算桶里元素的新位置for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {//原來的數(shù)據(jù)賦值為null 便于GC回收oldTab[j] = null;//判斷數(shù)組是否有下一個(gè)引用if (e.next == null)//沒有下一個(gè)引用，說明不是鏈表，當(dāng)前桶上只有一個(gè)鍵值對(duì)，直接插入newTab[e.hash & (newCap - 1)] = e;//判斷是否是紅黑樹else if (e instanceof TreeNode)//說明是紅黑樹來處理沖突的，則調(diào)用相關(guān)方法把樹分開((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // 采用鏈表處理沖突Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;//通過上述講解的原理來計(jì)算節(jié)點(diǎn)的新位置do {// 原索引next = e.next;//這里來判斷如果等于true e這個(gè)節(jié)點(diǎn)在resize之后不需要移動(dòng)位置if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到bucket里if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引+oldCap放到bucket里if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}

6.4 刪除方法(remove)

理解了put方法之后，remove方法已經(jīng)沒什么難度了，所以重復(fù)的內(nèi)容就不再做詳細(xì)介紹了。

刪除的話就是首先先找到元素的位置，如果是鏈表就遍歷鏈表找到元素之后刪除。如果是用紅黑樹就遍歷樹然后找到之后做刪除，樹小于6的時(shí)候要轉(zhuǎn)鏈表。

刪除remove方法：

//remove方法的具體實(shí)現(xiàn)在removeNode方法中，所以我們重點(diǎn)看下removeNode方法
public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}

removeNode方法：

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;//根據(jù)hash找到位置 //如果當(dāng)前key映射到的桶不為空if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;//如果桶上的節(jié)點(diǎn)就是要找的key，則將node指向該節(jié)點(diǎn)if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {//說明節(jié)點(diǎn)存在下一個(gè)節(jié)點(diǎn)if (p instanceof TreeNode)//說明是以紅黑樹來處理的沖突，則獲取紅黑樹要?jiǎng)h除的節(jié)點(diǎn)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {//判斷是否以鏈表方式處理hash沖突，是的話則通過遍歷鏈表來尋找要?jiǎng)h除的節(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);}}//比較找到的key的value和要?jiǎng)h除的是否匹配if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//通過調(diào)用紅黑樹的方法來刪除節(jié)點(diǎn)if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)//鏈表刪除tab[index] = node.next;elsep.next = node.next;//記錄修改次數(shù)++modCount;//變動(dòng)的數(shù)量--size;afterNodeRemoval(node);return node;}}return null;}

6.5查找元素方法(get)

查找方法，通過元素的Key找到Value。

代碼如下：

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

get方法主要調(diào)用的是getNode方法，代碼如下：

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果哈希表不為空并且key對(duì)應(yīng)的桶上不為空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {/* 判斷數(shù)組元素是否相等根據(jù)索引的位置檢查第一個(gè)元素注意：總是檢查第一個(gè)元素*/if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 如果不是第一個(gè)元素，判斷是否有后續(xù)節(jié)點(diǎn)if ((e = first.next) != null) {// 判斷是否是紅黑樹，是的話調(diào)用紅黑樹中的getTreeNode方法獲取節(jié)點(diǎn)if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {// 不是紅黑樹的話，那就是鏈表結(jié)構(gòu)了，通過循環(huán)的方法判斷鏈表中是否存在該keyif (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}

小結(jié)：

1.get方法實(shí)現(xiàn)的步驟：

? 1）通過hash值獲取該key映射到的桶

? 2）桶上的key就是要查找的key,則直接找到并返回

? 3）桶上的key不是要找的key,則查看后續(xù)的節(jié)點(diǎn)：

? a:如果后續(xù)節(jié)點(diǎn)是紅黑樹節(jié)點(diǎn)，通過調(diào)用紅黑樹的方法根據(jù)key獲取value

? b:如果后續(xù)節(jié)點(diǎn)是鏈表節(jié)點(diǎn)，則通過循環(huán)遍歷鏈表根據(jù)key獲取value

2.上述紅黑樹節(jié)點(diǎn)調(diào)用的是getTreeNode方法通過樹形節(jié)點(diǎn)的find方法進(jìn)行查找：

 final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);}final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this;do {int ph, dir; K pk;TreeNode<K,V> pl = p.left, pr = p.right, q;if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;//找到之后直接返回else if (pl == null)p = pr;else if (pr == null)p = pl;else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;//遞歸查找else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null;}

3.查找紅黑樹，由于之前添加時(shí)已經(jīng)保證這個(gè)樹是有序的了，因此查找時(shí)基本就是折半查找，效率更高。

4.這里和插入時(shí)一樣，如果對(duì)比節(jié)點(diǎn)的哈希值和要查找的哈希值相等，就會(huì)判斷key是否相等，相等就直接返回。不相等就從子樹中遞歸查找。

? 若為樹，則在樹中通過key.equals(k)查找，O(logn)

? 若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。

6.6遍歷HashMap集合幾種方式

1、分別遍歷Key和Values

for (String key : map.keySet()) {System.out.println("Key: " + key);
}
for (String value : map.values()) {System.out.println("value: " + value);
}

2、使用Iterator迭代器迭代

Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {Map.Entry<Integer, String> entry = iterator.next();System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

3、通過get方式（不建議使用）

for (Integer key : map.keySet()) {System.out.println("Key: " + key + ", Value: " + map.get(key));
}

說明：根據(jù)阿里開發(fā)手冊(cè)，不建議使用這種方式，因?yàn)榈鷥纱?。keySet獲取Iterator一次，還有通過get又迭代一次。降低性能。

4.jdk8以后使用Map接口中的默認(rèn)方法：

default void forEach(BiConsumer<? super K,? super V> action) 
BiConsumer接口中的方法：void accept?(T t, U u) 對(duì)給定的參數(shù)執(zhí)行此操作。  參數(shù) t - 第一個(gè)輸入?yún)?shù) u - 第二個(gè)輸入?yún)?shù) 

遍歷代碼：

map.forEach((key, value) -> {System.out.println("Key: " + key + ", Value: " + value);
})

7.初始化問題

7.1HashMap的初始化問題描述

? 如果我們確切的知道我們有多少鍵值對(duì)需要存儲(chǔ)，那么我們?cè)诔跏蓟疕ashMap的時(shí)候就應(yīng)該指定它的容量，以防止HashMap自動(dòng)擴(kuò)容，影響使用效率。

? 默認(rèn)情況下HashMap的容量是16，但是，如果用戶通過構(gòu)造函數(shù)指定了一個(gè)數(shù)字作為容量，那么Hash會(huì)選擇大于該數(shù)字的第一個(gè)2的冪作為容量。(3->4、7->8、9->16) .這點(diǎn)我們?cè)谏鲜鲆呀?jīng)進(jìn)行過講解。

《阿里巴巴Java開發(fā)手冊(cè)》中建議我們?cè)O(shè)置HashMap的初始化容量。

那么，為什么要這么建議？你有想過沒有。

當(dāng)然，以上建議也是有理論支撐的。我們上面介紹過，HashMap的擴(kuò)容機(jī)制，就是當(dāng)達(dá)到擴(kuò)容條件時(shí)會(huì)進(jìn)行擴(kuò)容。HashMap的擴(kuò)容條件就是當(dāng)HashMap中的元素個(gè)數(shù)（size）超過臨界值（threshold）時(shí)就會(huì)自動(dòng)擴(kuò)容。在HashMap中，threshold = loadFactor * capacity。

所以，如果我們沒有設(shè)置初始容量大小，隨著元素的不斷增加，HashMap會(huì)有可能發(fā)生多次擴(kuò)容，而HashMap中的擴(kuò)容機(jī)制決定了每次擴(kuò)容都需要重建hash表，是非常影響性能的。

但是設(shè)置初始化容量，設(shè)置的數(shù)值不同也會(huì)影響性能，那么當(dāng)我們已知HashMap中即將存放的KV個(gè)數(shù)的時(shí)候，容量設(shè)置成多少為好呢？

7.2HashMap中容量的初始化

當(dāng)我們使用HashMap(int initialCapacity)來初始化容量的時(shí)候，jdk會(huì)默認(rèn)幫我們計(jì)算一個(gè)相對(duì)合理的值當(dāng)做初始容量。那么，是不是我們只需要把已知的HashMap中即將存放的元素個(gè)數(shù)直接傳給initialCapacity就可以了呢？

關(guān)于這個(gè)值的設(shè)置，在《阿里巴巴Java開發(fā)手冊(cè)》有以下建議：

也就是說，如果我們?cè)O(shè)置的默認(rèn)值是7，經(jīng)過Jdk處理之后，會(huì)被設(shè)置成8，但是，這個(gè)HashMap在元素個(gè)數(shù)達(dá)到 8*0.75 = 6的時(shí)候就會(huì)進(jìn)行一次擴(kuò)容，這明顯是我們不希望見到的。我們應(yīng)該盡量減少擴(kuò)容。原因也已經(jīng)分析過。

如果我們通過initialCapacity/ 0.75F + 1.0F計(jì)算，7/0.75 + 1 = 10 ,10經(jīng)過Jdk處理之后，會(huì)被設(shè)置成16，這就大大的減少了擴(kuò)容的幾率。

當(dāng)HashMap內(nèi)部維護(hù)的哈希表的容量達(dá)到75%時(shí)（默認(rèn)情況下），會(huì)觸發(fā)rehash，而rehash的過程是比較耗費(fèi)時(shí)間的。所以初始化容量要設(shè)置成initialCapacity/0.75 + 1的話，可以有效的減少?zèng)_突也可以減小誤差。

所以，我可以認(rèn)為，當(dāng)我們明確知道HashMap中元素的個(gè)數(shù)的時(shí)候，把默認(rèn)容量設(shè)置成initialCapacity/ 0.75F + 1.0F是一個(gè)在性能上相對(duì)好的選擇，但是，同時(shí)也會(huì)犧牲些內(nèi)存。

我們想要在代碼中創(chuàng)建一個(gè)HashMap的時(shí)候，如果我們已知這個(gè)Map中即將存放的元素個(gè)數(shù)，給HashMap設(shè)置初始容量可以在一定程度上提升效率。

但是，JDK并不會(huì)直接拿用戶傳進(jìn)來的數(shù)字當(dāng)做默認(rèn)容量，而是會(huì)進(jìn)行一番運(yùn)算，最終得到一個(gè)2的冪。原因也已經(jīng)分析過。

但是，為了最大程度的避免擴(kuò)容帶來的性能消耗，我們建議可以把默認(rèn)容量的數(shù)字設(shè)置成initialCapacity/ 0.75F + 1.0F。