HashMap是面試中經(jīng)常問(wèn)到的一個(gè)知識(shí)點(diǎn),也是判斷一個(gè)候選人基礎(chǔ)是否扎實(shí)的標(biāo)準(zhǔn)之一?？梢?jiàn)HashMap的掌握是多重要。

一、HashMap源碼分析

1、構(gòu)造函數(shù)

讓我們先從構(gòu)造函數(shù)說(shuō)起，HashMap有四個(gè)構(gòu)造方法，別慌

1.1 ?HashMap()

????//?1.無(wú)參構(gòu)造方法、//?構(gòu)造一個(gè)空的HashMap，初始容量為16，負(fù)載因子為0.75public?HashMap()?{????????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted}

無(wú)參構(gòu)造方法就沒(méi)什么好說(shuō)的了。

1.2 HashMap(int initialCapacity)

????//?2.構(gòu)造一個(gè)初始容量為initialCapacity，負(fù)載因子為0.75的空的HashMap，public?HashMap(int?initialCapacity)?{????????this(initialCapacity,?DEFAULT_LOAD_FACTOR);}

HashMap(int initialCapacity) 這個(gè)構(gòu)造方法調(diào)用了1.3中的構(gòu)造方法。

1.3 HashMap(int initialCapacity, float loadFactor)

????//?3.構(gòu)造一個(gè)空的初始容量為initialCapacity，負(fù)載因子為loadFactor的HashMappublic?HashMap(int?initialCapacity,?float?loadFactor)?{????????if?(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);}????//最大容量//static?final?int?MAXIMUM_CAPACITY?=?1?<<?30;

當(dāng)指定的初始容量< 0時(shí)拋出IllegalArgumentException異常，當(dāng)指定的初始容量> MAXIMUM_CAPACITY時(shí)，就讓初始容量 = MAXIMUM_CAPACITY。當(dāng)負(fù)載因子小于0或者不是數(shù)字時(shí)，拋出IllegalArgumentException異常。

設(shè)定threshold。 這個(gè)threshold = capacity * load factor 。當(dāng)HashMap的size到了threshold時(shí)，就要進(jìn)行resize，也就是擴(kuò)容。

tableSizeFor()的主要功能是返回一個(gè)比給定整數(shù)大且最接近的2的冪次方整數(shù)，如給定10，返回2的4次方16.

我們進(jìn)入tableSizeFor(int cap)的源碼中看看：

????//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;}

note： HashMap要求容量必須是2的冪。

首先，int n = cap -1是為了防止cap已經(jīng)是2的冪時(shí)，執(zhí)行完后面的幾條無(wú)符號(hào)右移操作之后，返回的capacity是這個(gè)cap的2倍，因?yàn)閏ap已經(jīng)是2的冪了，就已經(jīng)滿足條件了。 如果不懂可以往下看完幾個(gè)無(wú)符號(hào)移位后再回來(lái)看。（建議自己在紙上畫一下）

• 如果n這時(shí)為0了（經(jīng)過(guò)了cap-1之后），則經(jīng)過(guò)后面的幾次無(wú)符號(hào)右移依然是0，最后返回的capacity是1（最后有個(gè)n+1的操作）。這里只討論n不等于0的情況。

以16位為例，假設(shè)開始時(shí) n 為 0000 1xxx xxxx xxxx ?（x代表不關(guān)心0還是1）

• 第一次右移 n |= n >>> 1;

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

• 第二次右移 n |= n >>> 2;

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

• 第三次右移 n |= n >>> 4;

  這次把已經(jīng)有的高位中的連續(xù)的4個(gè)1，右移4位，再做或操作，這樣n的二進(jìn)制表示的高位中會(huì)有8個(gè)連續(xù)的1。如0000 1111 1111 xxxx 。

第。。。，你還忍心讓我繼續(xù)推么？相信聰明的你已經(jīng)想出來(lái)了，容量最大也就是32位的正數(shù)，所以最后一次 ? ? n |= n >>> 16; 可以保證最高位后面的全部置為1。當(dāng)然如果是32個(gè)1的話，此時(shí)超出了MAXIMUM_CAPACITY ，所以取值到 MAXIMUM_CAPACITY 。

這里我從別人的文章當(dāng)一個(gè)別人的圖片，懶得畫了

?

注意，得到的這個(gè)capacity卻被賦值給了threshold。 這里我和這篇博客的博主開始的想法一樣，認(rèn)為應(yīng)該這么寫：this.threshold = tableSizeFor(initialCapacity) * this.loadFactor; ?因?yàn)檫@樣子才符合threshold的定義：threshold = capacity * load factor ?。但是，請(qǐng)注意，在構(gòu)造方法中，并沒(méi)有對(duì)table這個(gè)成員變量進(jìn)行初始化，table的初始化被推遲到了put方法中，在put方法中會(huì)對(duì)threshold重新計(jì)算 。

我說(shuō)一下我在理解這個(gè)tableSizeFor函數(shù)中間遇到的坑吧，我在想如果n=-1時(shí)的情況，因?yàn)槌跏既萘靠梢詡鬟M(jìn)來(lái)0。我將n= -1 和下面幾條運(yùn)算一起新寫了個(gè)測(cè)試程序，發(fā)現(xiàn)輸出都是 -1。 這是因?yàn)橛?jì)算機(jī)中數(shù)字是由補(bǔ)碼存儲(chǔ)的，-1的補(bǔ)碼是 0xffffffff。所以無(wú)符號(hào)右移之后再進(jìn)行或運(yùn)算之后還是 -1。 那我想如果就無(wú)符號(hào)右移呢？ 比如-1>>>10。聽(tīng)我娓娓道來(lái)，32個(gè)1無(wú)符號(hào)右移10位后，高10位為0，低22位為1，此時(shí)這個(gè)數(shù)變成了正數(shù)，由于正數(shù)的補(bǔ)碼和原碼相同，所以就變成了0x3FFFFF即10進(jìn)制的4194303。真刺激。

好開森，這個(gè)構(gòu)造方法我們算是拿下了。怎么樣，我猜你現(xiàn)在一定很激動(dòng)，Hey，old ?Fe，這才剛開始。接下來(lái)看最后一個(gè)構(gòu)造方法。

1.4 HashMap(Map<? extends K, ? extends V> m)

????//?4.?構(gòu)造一個(gè)和指定Map有相同mappings的HashMap，初始容量能充足的容下指定的Map,負(fù)載因子為0.75public?HashMap(Map<??extends?K,???extends?V>?m)?{????????this.loadFactor?=?DEFAULT_LOAD_FACTOR;putMapEntries(m,?false);}

套路，直接看 putMapEntries(m,false) 。源碼如下：

????

????/***?將m的所有元素存入本HashMap實(shí)例中*/final?void?putMapEntries(Map<??extends?K,???extends?V>?m,?boolean?evict)?{????????//得到?m?中元素的個(gè)數(shù)int?s?=?m.size();????????//當(dāng)?m?中有元素時(shí)，則需將map中元素放入本HashMap實(shí)例。if?(s?>?0)?{????????????//?判斷table是否已經(jīng)初始化，如果未初始化，則先初始化一些變量。（table初始化是在put時(shí)）if?(table?==?null)?{?//?pre-size//?根據(jù)待插入的map?的?size?計(jì)算要?jiǎng)?chuàng)建的　HashMap?的容量。float?ft?=?((float)s?/?loadFactor)?+?1.0F;????????????????int?t?=?((ft?<?(float)MAXIMUM_CAPACITY)??(int)ft?:?MAXIMUM_CAPACITY);????????????????//?把要?jiǎng)?chuàng)建的　HashMap?的容量存在　threshold　中if?(t?>?threshold)threshold?=?tableSizeFor(t);}????????????//?如果table初始化過(guò)，因?yàn)閯e的函數(shù)也會(huì)調(diào)用它，所以有可能HashMap已經(jīng)被初始化過(guò)了。//?判斷待插入的　map?的?size,若　size?大于　threshold，則先進(jìn)行　resize()，進(jìn)行擴(kuò)容else?if?(s?>?threshold)resize();????????????//然后就開始遍歷?帶插入的?map?，將每一個(gè)?<Key?,Value>?插入到本HashMap實(shí)例。for?(Map.Entry<??extends?K,???extends?V>?e?:?m.entrySet())?{K?key?=?e.getKey();V?value?=?e.getValue();????????????????//?put(K,V)也是調(diào)用　putVal　函數(shù)進(jìn)行元素的插入putVal(hash(key),?key,?value,?false,?evict);}}}

介紹putVal方法前，說(shuō)一下HashMap的幾個(gè)重要的成員變量：

????/***?The?table,?initialized?on?first?use,?and?resized?as*?necessary.?When?allocated,?length?is?always?a?power?of?two.*?(We?also?tolerate?length?zero?in?some?operations?to?allow*?bootstrapping?mechanics?that?are?currently?not?needed.)*///實(shí)際存儲(chǔ)key，value的數(shù)組，只不過(guò)key，value被封裝成Node了transient?Node<K,V>[]?table;????/***?The?number?of?key-value?mappings?contained?in?this?map.*/transient?int?size;????/***?The?number?of?times?this?HashMap?has?been?structurally?modified*?Structural?modifications?are?those?that?change?the?number?of?mappings?in*?the?HashMap?or?otherwise?modify?its?internal?structure?(e.g.,*?rehash).??This?field?is?used?to?make?iterators?on?Collection-views?of*?the?HashMap?fail-fast.??(See?ConcurrentModificationException).*/transient?int?modCount;????/***?The?next?size?value?at?which?to?resize?(capacity?*?load?factor).**?@serial*///?(The?javadoc?description?is?true?upon?serialization.//?Additionally,?if?the?table?array?has?not?been?allocated,?this//?field?holds?the?initial?array?capacity,?or?zero?signifying//?DEFAULT_INITIAL_CAPACITY.)//因?yàn)?tableSizeFor(int)?返回值給了thresholdint?threshold;????/***?The?load?factor?for?the?hash?table.**?@serial*/final?float?loadFactor;

其實(shí)就是哈希表。HashMap使用鏈表法避免哈希沖突（相同hash值），當(dāng)鏈表長(zhǎng)度大于TREEIFY_THRESHOLD（默認(rèn)為8）時(shí)，將鏈表轉(zhuǎn)換為紅黑樹，當(dāng)然小于UNTREEIFY_THRESHOLD（默認(rèn)為6）時(shí)，又會(huì)轉(zhuǎn)回鏈表以達(dá)到性能均衡。 我們看一張HashMap的數(shù)據(jù)結(jié)構(gòu)（數(shù)組+鏈表+紅黑樹 ）就更能理解table了：

再回到putMapEntries函數(shù)中，如果table為null，那么這時(shí)就設(shè)置合適的threshold，如果不為空并且指定的map的size>threshold，那么就resize()。然后把指定的map的所有Key，Value，通過(guò)putVal添加到我們創(chuàng)建的新的map中。

putVal中傳入了個(gè)hash(key)，那我們就先來(lái)看看hash(key):

/***?key?的?hash值的計(jì)算是通過(guò)hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h?=?k.hashCode())?^?(h?>>>?16)*?主要是從速度、功效、質(zhì)量來(lái)考慮的，這么做可以在數(shù)組table的length比較小的時(shí)候*?也能保證考慮到高低Bit都參與到Hash的計(jì)算中，同時(shí)不會(huì)有太大的開銷*/static?final?int?hash(Object?key)?{????????int?h;????????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);}

異或運(yùn)算：(h = key.hashCode()) ^ (h >>> 16)

原 來(lái) 的 hashCode : 1111 1111 1111 1111 0100 1100 0000 1010
移位后的hashCode: 0000 0000 0000 0000 1111 1111 1111 1111
進(jìn)行異或運(yùn)算 結(jié)果：1111 1111 1111 1111 1011 0011 1111 0101

這樣做的好處是，可以將hashcode高位和低位的值進(jìn)行混合做異或運(yùn)算，而且混合后，低位的信息中加入了高位的信息，這樣高位的信息被變相的保留了下來(lái)。摻雜的元素多了，那么生成的hash值的隨機(jī)性會(huì)增大。

剛才我們漏掉了resize()和putVal() 兩個(gè)函數(shù)，現(xiàn)在我們按順序分析一波：

首先resize() ,先看一下哪些函數(shù)調(diào)用了resize()，從而在整體上有個(gè)概念：

?

接下來(lái)上源碼：

????final?Node<K,V>[]?resize()?{????????//?保存當(dāng)前tableNode<K,V>[]?oldTab?=?table;????????//?保存當(dāng)前table的容量int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;????????//?保存當(dāng)前閾值int?oldThr?=?threshold;????????//?初始化新的table容量和閾值?int?newCap,?newThr?=?0;????????/*1.?resize（）函數(shù)在size　>?threshold時(shí)被調(diào)用。oldCap大于?0?代表原來(lái)的?table?表非空，oldCap?為原表的大小，oldThr（threshold）?為?oldCap?×?load_factor*/if?(oldCap?>?0)?{????????????//?若舊table容量已超過(guò)最大容量，更新閾值為Integer.MAX_VALUE（最大整形值），這樣以后就不會(huì)自動(dòng)擴(kuò)容了。if?(oldCap?>=?MAXIMUM_CAPACITY)?{threshold?=?Integer.MAX_VALUE;????????????????return?oldTab;}?????????????//?容量翻倍，使用左移，效率更高else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&oldCap?>=?DEFAULT_INITIAL_CAPACITY)????????????????//?閾值翻倍newThr?=?oldThr?<<?1;?//?double?threshold}????????/*2.?resize（）函數(shù)在table為空被調(diào)用。oldCap?小于等于?0?且?oldThr?大于0，代表用戶創(chuàng)建了一個(gè)?HashMap，但是使用的構(gòu)造函數(shù)為??????HashMap(int?initialCapacity,?float?loadFactor)?或?HashMap(int?initialCapacity)或?HashMap(Map<??extends?K,???extends?V>?m)，導(dǎo)致?oldTab?為?null，oldCap?為0，?oldThr?為用戶指定的?HashMap的初始容量。*/else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold//當(dāng)table沒(méi)初始化時(shí)，threshold持有初始容量。還記得threshold?=?tableSizeFor(t)么;newCap?=?oldThr;????????/*3.?resize（）函數(shù)在table為空被調(diào)用。oldCap?小于等于?0?且?oldThr?等于0，用戶調(diào)用?HashMap()構(gòu)造函數(shù)創(chuàng)建的　HashMap，所有值均采用默認(rèn)值，oldTab（Table）表為空，oldCap為0，oldThr等于0，*/else?{???????????????//?zero?initial?threshold?signifies?using?defaultsnewCap?=?DEFAULT_INITIAL_CAPACITY;newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);}????????//?新閾值為0if?(newThr?==?0)?{????????????float?ft?=?(float)newCap?*?loadFactor;newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY??(int)ft?:?Integer.MAX_VALUE);}threshold?=?newThr;????????@SuppressWarnings({"rawtypes","unchecked"})????????//?初始化tableNode<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];table?=?newTab;????????if?(oldTab?!=?null)?{????????????//?把?oldTab?中的節(jié)點(diǎn)　reHash?到　newTab?中去for?(int?j?=?0;?j?<?oldCap;?++j)?{Node<K,V>?e;????????????????if?((e?=?oldTab[j])?!=?null)?{oldTab[j]?=?null;????????????????????//?若節(jié)點(diǎn)是單個(gè)節(jié)點(diǎn)，直接在?newTab　中進(jìn)行重定位if?(e.next?==?null)newTab[e.hash?&?(newCap?-?1)]?=?e;????????????????????//?若節(jié)點(diǎn)是　TreeNode?節(jié)點(diǎn)，要進(jìn)行?紅黑樹的?rehash　操作else?if?(e?instanceof?TreeNode)((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);????????????????????//?若是鏈表，進(jìn)行鏈表的?rehash　操作else?{?//?preserve?orderNode<K,V>?loHead?=?null,?loTail?=?null;Node<K,V>?hiHead?=?null,?hiTail?=?null;Node<K,V>?next;????????????????????????//?將同一桶中的元素根據(jù)(e.hash?&?oldCap)是否為0進(jìn)行分割（代碼后有圖解，可以回過(guò)頭再來(lái)看），分成兩個(gè)不同的鏈表，完成rehashdo?{next?=?e.next;????????????????????????????//?根據(jù)算法　e.hash?&?oldCap?判斷節(jié)點(diǎn)位置rehash　后是否發(fā)生改變//最高位==0，這是索引不變的鏈表。if?((e.hash?&?oldCap)?==?0)?{?if?(loTail?==?null)loHead?=?e;????????????????????????????????elseloTail.next?=?e;loTail?=?e;}????????????????????????????//最高位==1?（這是索引發(fā)生改變的鏈表）else?{??if?(hiTail?==?null)hiHead?=?e;????????????????????????????????elsehiTail.next?=?e;hiTail?=?e;}}?while?((e?=?next)?!=?null);????????????????????????if?(loTail?!=?null)?{??//?原bucket位置的尾指針不為空(即還有node)??loTail.next?=?null;?//?鏈表最后得有個(gè)nullnewTab[j]?=?loHead;?//?鏈表頭指針?lè)旁谛峦暗南嗤聵?biāo)(j)處}????????????????????????if?(hiTail?!=?null)?{hiTail.next?=?null;????????????????????????????//?rehash　后節(jié)點(diǎn)新的位置一定為原來(lái)基礎(chǔ)上加上　oldCap，具體解釋看下圖newTab[j?+?oldCap]?=?hiHead;}}}}}????????return?newTab;}
}

引自美團(tuán)點(diǎn)評(píng)技術(shù)博客。我們使用的是2次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來(lái)2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置?？聪聢D可以明白這句話的意思，n為table的長(zhǎng)度，圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果。

?

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

?

因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒(méi)變，是1的話索引變成“原索引+oldCap”，可以看看下圖為16擴(kuò)充為32的resize示意圖 ：

?

什么時(shí)候擴(kuò)容：通過(guò)HashMap源碼可以看到是在put操作時(shí)，即向容器中添加元素時(shí)，判斷當(dāng)前容器中元素的個(gè)數(shù)是否達(dá)到閾值（當(dāng)前數(shù)組長(zhǎng)度乘以加載因子的值）的時(shí)候，就要自動(dòng)擴(kuò)容了。

擴(kuò)容(resize)：其實(shí)就是重新計(jì)算容量；而這個(gè)擴(kuò)容是計(jì)算出所需容器的大小之后重新定義一個(gè)新的容器，將原來(lái)容器中的元素放入其中。

resize()告一段落，接下來(lái)看 putVal() 。

上源碼：

?

???//實(shí)現(xiàn)put和相關(guān)方法。final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,???????????????????boolean?evict)?{Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;????????//如果table為空或者長(zhǎng)度為0，則resize()if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)n?=?(tab?=?resize()).length;????????//確定插入table的位置，算法是(n?-?1)?&?hash，在n為2的冪時(shí)，相當(dāng)于取摸操作。找到key值對(duì)應(yīng)的槽并且是第一個(gè)，直接加入if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)tab[i]?=?newNode(hash,?key,?value,?null);????????//在table的i位置發(fā)生碰撞，有兩種情況，1、key值是一樣的，替換value值，//2、key值不一樣的有兩種處理方式：2.1、存儲(chǔ)在i位置的鏈表；2.2、存儲(chǔ)在紅黑樹中else?{Node<K,V>?e;?K?k;????????????//第一個(gè)node的hash值即為要加入元素的hashif?(p.hash?==?hash?&&((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))e?=?p;????????????//2.2else?if?(p?instanceof?TreeNode)e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);????????????//2.1else?{????????????????//不是TreeNode,即為鏈表,遍歷鏈表for?(int?binCount?=?0;?;?++binCount)?{????????????????///鏈表的尾端也沒(méi)有找到key值相同的節(jié)點(diǎn)，則生成一個(gè)新的Node,//并且判斷鏈表的節(jié)點(diǎn)個(gè)數(shù)是不是到達(dá)轉(zhuǎn)換成紅黑樹的上界達(dá)到，則轉(zhuǎn)換成紅黑樹。if?((e?=?p.next)?==?null)?{?????????????????????????//?創(chuàng)建鏈表節(jié)點(diǎn)并插入尾部p.next?=?newNode(hash,?key,?value,?null);????????????????????????超過(guò)了鏈表的設(shè)置長(zhǎng)度8就轉(zhuǎn)換成紅黑樹if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1sttreeifyBin(tab,?hash);????????????????????????break;}????????????????????if?(e.hash?==?hash?&&((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????????????????break;p?=?e;}}????????????//如果e不為空就替換舊的oldValue值if?(e?!=?null)?{?//?existing?mapping?for?keyV?oldValue?=?e.value;????????????????if?(!onlyIfAbsent?||?oldValue?==?null)e.value?=?value;afterNodeAccess(e);????????????????return?oldValue;}}++modCount;????????if?(++size?>?threshold)resize();afterNodeInsertion(evict);????????return?null;}

注：hash 沖突發(fā)生的幾種情況：
1.兩節(jié)點(diǎn)key 值相同（hash值一定相同），導(dǎo)致沖突；
2.兩節(jié)點(diǎn)key 值不同，由于 hash 函數(shù)的局限性導(dǎo)致hash 值相同，沖突；
3.兩節(jié)點(diǎn)key 值不同，hash 值不同，但 hash 值對(duì)數(shù)組長(zhǎng)度取模后相同，沖突；

相比put方法，get方法就比較簡(jiǎn)單，這里就不說(shuō)了。

1.7和1.8的HashMap的不同點(diǎn)

（1）JDK1.7用的是頭插法，而JDK1.8及之后使用的都是尾插法，那么為什么要這樣做呢？因?yàn)镴DK1.7是用單鏈表進(jìn)行的縱向延伸，當(dāng)采用頭插法就是能夠提高插入的效率，但是也會(huì)容易出現(xiàn)逆序且環(huán)形鏈表死循環(huán)問(wèn)題。但是在JDK1.8之后是因?yàn)榧尤肓思t黑樹使用尾插法，能夠避免出現(xiàn)逆序且鏈表死循環(huán)的問(wèn)題。

（2）擴(kuò)容后數(shù)據(jù)存儲(chǔ)位置的計(jì)算方式也不一樣：

1. 在JDK1.7的時(shí)候是直接用hash值和需要擴(kuò)容的二進(jìn)制數(shù)進(jìn)行&（這里就是為什么擴(kuò)容的時(shí)候?yàn)樯兑欢ū仨毷?的多少次冪的原因所在，因?yàn)槿绻挥?的n次冪的情況時(shí)最后一位二進(jìn)制數(shù)才一定是1，這樣能最大程度減少hash碰撞）（hash值 & length-1） 。

2. 而在JDK1.8的時(shí)候直接用了JDK1.7的時(shí)候計(jì)算的規(guī)律，也就是擴(kuò)容前的原始位置+擴(kuò)容的大小值=JDK1.8的計(jì)算方式，而不再是JDK1.7的那種異或的方法。但是這種方式就相當(dāng)于只需要判斷Hash值的新增參與運(yùn)算的位是0還是1就直接迅速計(jì)算出了擴(kuò)容后的儲(chǔ)存方式。

（3）JDK1.7的時(shí)候使用的是數(shù)組+ 單鏈表的數(shù)據(jù)結(jié)構(gòu)。但是在JDK1.8及之后時(shí)，使用的是數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)（當(dāng)鏈表的深度達(dá)到8的時(shí)候，也就是默認(rèn)閾值，就會(huì)自動(dòng)擴(kuò)容把鏈表轉(zhuǎn)成紅黑樹的數(shù)據(jù)結(jié)構(gòu)來(lái)把時(shí)間復(fù)雜度從O（N）變成O（logN）提高了效率）。

HashMap為什么是線程不安全的？

HashMap 在并發(fā)時(shí)可能出現(xiàn)的問(wèn)題主要是兩方面：

1. put的時(shí)候?qū)е碌亩嗑€程數(shù)據(jù)不一致
   比如有兩個(gè)線程A和B，首先A希望插入一個(gè)key-value對(duì)到HashMap中，首先計(jì)算記錄所要落到的 hash桶的索引坐標(biāo)，然后獲取到該桶里面的鏈表頭結(jié)點(diǎn)，此時(shí)線程A的時(shí)間片用完了，而此時(shí)線程B被調(diào)度得以執(zhí)行，和線程A一樣執(zhí)行，只不過(guò)線程B成功將記錄插到了桶里面，假設(shè)線程A插入的記錄計(jì)算出來(lái)的 hash桶索引和線程B要插入的記錄計(jì)算出來(lái)的 hash桶索引是一樣的，那么當(dāng)線程B成功插入之后，線程A再次被調(diào)度運(yùn)行時(shí)，它依然持有過(guò)期的鏈表頭但是它對(duì)此一無(wú)所知，以至于它認(rèn)為它應(yīng)該這樣做，如此一來(lái)就覆蓋了線程B插入的記錄，這樣線程B插入的記錄就憑空消失了，造成了數(shù)據(jù)不一致的行為。

2. resize而引起死循環(huán)
   這種情況發(fā)生在HashMap自動(dòng)擴(kuò)容時(shí)，當(dāng)2個(gè)線程同時(shí)檢測(cè)到元素個(gè)數(shù)超過(guò) 數(shù)組大小 × 負(fù)載因子。此時(shí)2個(gè)線程會(huì)在put()方法中調(diào)用了resize()，兩個(gè)線程同時(shí)修改一個(gè)鏈表結(jié)構(gòu)會(huì)產(chǎn)生一個(gè)循環(huán)鏈表（JDK1.7中，會(huì)出現(xiàn)resize前后元素順序倒置的情況）。接下來(lái)再想通過(guò)get()獲取某一個(gè)元素，就會(huì)出現(xiàn)死循環(huán)。

HashMap和HashTable的區(qū)別

HashMap和Hashtable都實(shí)現(xiàn)了Map接口，但決定用哪一個(gè)之前先要弄清楚它們之間的分別。主要的區(qū)別有：線程安全性，同步(synchronization)，以及速度。

1. HashMap幾乎可以等價(jià)于Hashtable，除了HashMap是非synchronized的，并可以接受null(HashMap可以接受為null的鍵值(key)和值(value)，而Hashtable則不行)。

2. HashMap是非synchronized，而Hashtable是synchronized，這意味著Hashtable是線程安全的，多個(gè)線程可以共享一個(gè)Hashtable；而如果沒(méi)有正確的同步的話，多個(gè)線程是不能共享HashMap的。Java 5提供了ConcurrentHashMap，它是HashTable的替代，比HashTable的擴(kuò)展性更好。

3. 另一個(gè)區(qū)別是HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別。

4. 由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過(guò)Hashtable。

5. HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。

需要注意的重要術(shù)語(yǔ)：

1. sychronized意味著在一次僅有一個(gè)線程能夠更改Hashtable。就是說(shuō)任何線程要更新Hashtable時(shí)要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。

2. Fail-safe和iterator迭代器相關(guān)。如果某個(gè)集合對(duì)象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對(duì)象，將會(huì)拋出ConcurrentModificationException異常。但其它線程可以通過(guò)set()方法更改集合對(duì)象是允許的，因?yàn)檫@并沒(méi)有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改，再調(diào)用set()方法，將會(huì)拋出IllegalArgumentException異常。

3. 結(jié)構(gòu)上的更改指的是刪除或者插入一個(gè)元素，這樣會(huì)影響到map的結(jié)構(gòu)。