第一文帶你解讀所有HashMap的面試題目錄HashMapHashMap的數(shù)據(jù)結(jié)構(gòu)JDK7和JDK8HashMap哪里不一樣HashMap是否安全HashMap的擴(kuò)容機(jī)制關(guān)于HashMap阿粉相信大家再面試的時(shí)候，是非常容易被問到的，為什么呢？因?yàn)橹辽偈窃贘DK8出來之后，非常容易被問到關(guān)于HashMap的知識(shí)點(diǎn)，而如果對(duì)于沒有研究過他的源代碼的同學(xué)來說，這個(gè)可能只是說出一部分來，比如線程安全，鏈表+紅黑樹，以及他的擴(kuò)容等等，今天阿粉就來把HashMap上面大部分會(huì)被在面試中問到的內(nèi)容，做個(gè)總結(jié)。

HashMap

說到HashMap想必大家從腦海中直接復(fù)現(xiàn)出了一大堆的面試題，

HashMap的數(shù)據(jù)結(jié)構(gòu)JDK7和JDK8HashMap哪里不一樣HashMap是否安全HashMap的擴(kuò)容機(jī)制

說到這里，我們就來挨著分析一下這個(gè)HashMap的這寫面試題。

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

這個(gè)HashMap的數(shù)據(jù)結(jié)構(gòu)，面試官這個(gè)問題，屬于那種可大可小的，往大了說，那就是需要你把所有的關(guān)于HashMap中的內(nèi)容都詳細(xì)的解釋明白，但是如果要是往小了說，那就是介紹一下內(nèi)部結(jié)構(gòu)，就可以了。

阿粉今天來分析一下這個(gè)數(shù)據(jù)結(jié)構(gòu)了。

HashMap里面有幾個(gè)比較重要的參數(shù)：

//默認(rèn)初始容量——必須是2的冪

staticfinalintDEFAULT_INITIAL_CAPACITY=14;

//當(dāng)沒有構(gòu)造函數(shù)中指定使用的負(fù)載系數(shù)

staticfinalfloatDEFAULT_LOAD_FACTOR=0.75f;

//擴(kuò)容的閾值，等于CAPACITY*LOAD_FACTOR

staticfinalintTREEIFY_THRESHOLD=8;

//降容的閾值

static

final

int

UNTREEIFY_THRESHOLD

=

6;

//擴(kuò)容的另外一個(gè)參數(shù)

static

final

int

MIN_TREEIFY_CAPACITY

=

64;

參數(shù)我們都看到了上述的這些內(nèi)容了，如果用大白話，怎么去形容這些參數(shù)呢？其實(shí)這就涉及到這個(gè)后面的JDK8中的HashMap不一樣的結(jié)構(gòu)了，

我們也知道JDK8中的HashMap，如果在橫向上是數(shù)組的話，那么他的縱向的每一個(gè)元素上面，都是一個(gè)單項(xiàng)的鏈表，而這個(gè)鏈表，會(huì)根據(jù)長(zhǎng)度，來進(jìn)行不通的演化，而這個(gè)演化就是擴(kuò)容成為樹結(jié)構(gòu)和降容成為鏈表結(jié)構(gòu)的關(guān)鍵，而這些關(guān)鍵，都是通過這些參數(shù)來進(jìn)行的定義。

CAPACITY就相當(dāng)于是HashMap中的默認(rèn)初始容量。

LOAD_FACTOR負(fù)載因子

TREEIFY_THRESHOLD樹化的閾值，也就是說table的node中的鏈表長(zhǎng)度超過這個(gè)閾值的時(shí)候，該鏈表會(huì)變成樹

UNTREEIFY_THRESHOLD樹降級(jí)成為鏈表的閾值（也就是說table的node中的樹長(zhǎng)度低于這個(gè)閾值的時(shí)候，樹會(huì)變成鏈表）

MIN_TREEIFY_CAPACITY樹化的另一個(gè)參數(shù)，就是當(dāng)hashmap中的node的個(gè)數(shù)大于這個(gè)值的時(shí)候，hashmap中的有些鏈表才會(huì)變成樹。

transientNodeK,V[]tableHash表

有些小伙伴在面試的時(shí)候，就會(huì)說，當(dāng)HashMap中的某個(gè)node鏈表長(zhǎng)度大于8的時(shí)候，HashMap中的這個(gè)鏈表就會(huì)變成樹，實(shí)際上不是的，這個(gè)還和MIN_TREEIFY_CAPACITY有關(guān)系，也就是說整個(gè)HashMap的node數(shù)量大于64，node的鏈表長(zhǎng)度大于8才會(huì)變成樹。

JDK7和JDK8HashMap哪里不一樣

JDK7我們大家也都知道，如果按照橫向是數(shù)組，那么他的縱向每個(gè)元素上面，都是一個(gè)單向的鏈表，而橫向上，每一個(gè)實(shí)體，就相當(dāng)于是一個(gè)Entry的實(shí)例。

而這每一個(gè)Entry中都包含了四個(gè)屬性，

keyvaluehash值用于單項(xiàng)列表的next

就像下圖這個(gè)樣子

JDK7

所以JDK7的HashMap的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組+鏈表的形式構(gòu)成

而JDK8就不一樣了，因?yàn)樗麄兊膬?nèi)部很巧妙的給增加了紅黑樹，如下圖

JDK8

所以JDK8的HashMap的數(shù)據(jù)結(jié)構(gòu)就是數(shù)組+鏈表+紅黑樹的形式構(gòu)成了。

HashMap是否安全

一說這個(gè)，肯定都是非?；A(chǔ)的面試題，都知道HashMap是屬于那種線程不安全的類，為什么不安全，他不安全到底會(huì)提現(xiàn)在哪個(gè)地方，難道面試的時(shí)候，你就只會(huì)說他的內(nèi)部沒有被synchronize關(guān)鍵字控制么？

所以，說起HashMap的不安全，那么就得從put和get方法說起了。

這個(gè)直接先看內(nèi)部實(shí)現(xiàn)，我們先來看put方法，然后去分析這個(gè)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)

{

NodeK,V[]

tab;

NodeK,V

int

n,

i;

//在這里先進(jìn)行

Hash表的初始化

if

((tab

=

table)

==

null

||

(n

=

tab.length)

==

0)

n

=

(tab

=

resize()).length;

//通過

Hash

值計(jì)算在

Hash

表中的位置，并將這個(gè)位置的元素賦值給P

如果等于空的話創(chuàng)建一個(gè)新的

node

if

((p

=

tab[i

=

(n

-

1)

hash])

==

null)

tab[i]

=

newNode(hash,

key,

value,

null);

else

{

NodeK,V

K

k;

//Hash表的當(dāng)前的

index

已經(jīng)存在了元素，向這個(gè)元素后追加鏈表

if

(p.hash

==

hash

((k

=

p.key)

==

key

||

(key

!=

null

key.equals(k))))

e

=

p;

else

if

(p

instanceof

TreeNode)

e

=

((TreeNodeK,V)p).putTreeVal(this,

tab,

hash,

key,

value);

else

{

for

(int

binCount

=

0;

;

++binCount)

{

//新建接點(diǎn)，并且追加到列表

if

((e

=

p.next)

==

null)

{

p.next

=

newNode(hash,

key,

value,

null);

if

(binCount

=

TREEIFY_THRESHOLD

-

1)

//

-1

for

1st

treeifyBin(tab,

hash);

break;

}

if

(e.hash

==

hash

((k

=

e.key)

==

key

||

(key

!=

null

key.equals(k))))

break;

p

=

e;

}

}

if

(e

!=

null)

{

//

existing

mapping

for

key

V

oldValue

=

e.value;

if

(!onlyIfAbsent

||

oldValue

==

null)

e.value

=

value;

afterNodeAccess(e);

return

oldValue;

}

}

++modCount;

if

(++size

threshold)

resize();

afterNodeInsertion(evict);

return

null;

}

看到源碼之后，我們猜想一下都會(huì)有哪些地方會(huì)出問題呢？比如，這時(shí)候如果有兩個(gè)線程同時(shí)去執(zhí)行put

一個(gè)線程A執(zhí)行put(1,A

一個(gè)線程B執(zhí)行put(2,B

如果這個(gè)時(shí)候線程A和B都執(zhí)行了if((p=tab[i=(n-1)hash])==null)但是，如果這個(gè)時(shí)候線程A先執(zhí)行了tab[i]=newNode(hash,key,value,null);這時(shí)候，內(nèi)部是沒啥問題的，已經(jīng)放進(jìn)去了，

這時(shí)候如果線程B去執(zhí)行tab[i]=newNode(hash,key,value,null);就會(huì)導(dǎo)致A線程中的key為1的元素A丟失。直接被線程B進(jìn)行了覆蓋，這也是為什么會(huì)有一些人說，JDK7中是對(duì)擴(kuò)容時(shí)會(huì)造成環(huán)形鏈或數(shù)據(jù)丟失，而在JDK8中是會(huì)會(huì)發(fā)生數(shù)據(jù)覆蓋的情況。

就會(huì)出現(xiàn)null的問題，這個(gè)問題，不論是JDK7還是JDK8全都有這個(gè)問題，如果面試的時(shí)候，能夠從這個(gè)地方分析一下的，至少這個(gè)線程不安全，你確實(shí)是自己去研究了一下，所以這就可以完美的解釋了，HashMap的線程不安全的問題了。

HashMap的擴(kuò)容機(jī)制

我們?cè)谏厦嬉捕剂信e了一下HashMap的一些關(guān)鍵參數(shù)，接下來，就來分析他的擴(kuò)容是怎么實(shí)現(xiàn)的，

public

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);

}

這段代碼，寫的看起來非常的舒服，指定了初始容量和加載因子，下一次需要擴(kuò)容的容量threshold值由tableSizeFor方法得出

static

final

int

tableSizeFor(int

cap)

{

int

n

=

cap

-

1;

//

：無符號(hào)右移。無論是正數(shù)還是負(fù)數(shù)，高位通通補(bǔ)0。

n

|=

n

n

|=

n

n

|=

n

n

|=

n

n

|=

n

return

(n

0)

1

:

(n

=

MAXIMUM_CAPACITY)

MAXIMUM_CAPACITY

:

n

+

1;

}

而tableSizeFor這個(gè)方法是用于計(jì)算出大于等于cap值的最大的2的冪值,而后續(xù)HashMap需要擴(kuò)容時(shí)，每次table數(shù)組長(zhǎng)度都擴(kuò)展為原來的兩倍，所以，table數(shù)組長(zhǎng)度總是為2的冪值。

為什么用位移運(yùn)算，不直接使用.pow的方法，這個(gè)東西，很明顯，位運(yùn)算這種方式，效率可比.pow的效率要高很多，接下來就是正兒八經(jīng)的擴(kuò)容方法了。

final

NodeK,V[]

resize()

{

NodeK,V[]

oldTab

=

table;

int

oldCap

=

(oldTab

==

null)

0

:

oldTab.length;

//舊容量

int

oldThr

=

threshold;//

舊的需要擴(kuò)容的閾值

int

newCap,

newThr

=

0;

if

(oldCap

0)

{//如果不是第一次擴(kuò)容

if

(oldCap

=

MAXIMUM_CAPACITY)

{

threshold

=

Integer.MAX_VALUE;//

如果容量大于最大值，將閾值設(shè)為最大值，這樣不會(huì)發(fā)生下次擴(kuò)容

return

oldTab;

}

//

擴(kuò)容容量為上一次容量的兩倍

else

if

((newCap

=

oldCap

1)

MAXIMUM_CAPACITY

oldCap

=

DEFAULT_INITIAL_CAPACITY)

newThr

=

oldThr

1;

//

下次擴(kuò)容閾值等于本次擴(kuò)容閾值*2，因?yàn)閿U(kuò)容會(huì)擴(kuò)為原來容量的兩倍，所以依然滿足

newThr

=

newCap

*

loadFactor

}

else

if

(oldThr

0)

//

第一次擴(kuò)容，并且用戶指定了初始容量

newCap

=

oldThr;

//

擴(kuò)展的容量為閾值

else

{

//

第一次擴(kuò)容，并且初始容量和加載因子使用的默認(rèn)值

newCap

=

DEFAULT_INITIAL_CAPACITY;

newThr

=

(int)(DEFAULT_LOAD_FACTOR

*

DEFAULT_INITIAL_CAPACITY);

}

if

(newThr

==

0)

{

//

如果用戶指定了初始容量時(shí)，并且是第一次擴(kuò)容

float

ft

=

(float)newCap

*

loadFactor;

//

下次擴(kuò)容閾值為

newCap

*

loadFactor

newThr

=

(newCap

MAXIMUM_CAPACITY

ft

(float)MAXIMUM_CAPACITY

(int)ft

:

Integer.MAX_VALUE);

}

threshold

=

newThr;

@SuppressWarnings({"rawtypes","unchecked"})

NodeK,V[]

newTab

=

(NodeK,V[])new

Node[newCap];//

新的數(shù)組

table

=

newTab;

if

(oldTab

!=

null)

{

for

(int

j

=

0;

j

oldCap;

++j)

{

//將舊數(shù)組數(shù)據(jù)移動(dòng)到新數(shù)組

NodeK,V

if

((e

=

oldTab[j])

!=

null)

{

oldTab[j]

=

null;

if

(e.next

==

null)

//

如果還不是鏈表或紅黑樹，把數(shù)據(jù)直接移動(dòng)到新數(shù)組中對(duì)應(yīng)位置

newTab[e.hash

(newCap

-

1)]

=

e;

else

if

(e

instanceof

Tree