??點(diǎn)擊上方?好好學(xué)java?，選擇?星標(biāo)?公眾號(hào)

重磅資訊、干貨，第一時(shí)間送達(dá) 今日推薦：終于放棄了單調(diào)的swagger-ui了，選擇了這款神器—knife4j個(gè)人原創(chuàng)+1博客：點(diǎn)擊前往，查看更多

前言

HashMap可以說(shuō)是面試的重中之重，去10家公司面試，8家都會(huì)問(wèn)道，為什么大家都愛(ài)用HashMap打開話題？

HashMap是怎么實(shí)現(xiàn)的？

jdk1.7的HashMap是用數(shù)組+鏈表實(shí)現(xiàn)的

jdk1.8的HashMap是用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)的

附上我歷時(shí)三個(gè)月總結(jié)的?Java 面試 + Java 后端技術(shù)學(xué)習(xí)指南，這是本人這幾年及春招的總結(jié)，目前，已經(jīng)拿到了大廠offer，拿去不謝！

下載方式

1.?首先掃描下方二維碼

2.?后臺(tái)回復(fù)「Java面試」即可獲取

HashMap的主干是一個(gè)數(shù)組，假設(shè)我們有3個(gè)鍵值對(duì)dnf:1，cf:2，lol:3，每次放的時(shí)候會(huì)根據(jù)key.hash % table.length（對(duì)象的hashcode進(jìn)行一些操作后對(duì)數(shù)組的長(zhǎng)度取余）確定這個(gè)鍵值對(duì)應(yīng)該放在數(shù)組的哪個(gè)位位置

1 = indexFor(dnf)，我們將鍵值對(duì)放在數(shù)組下標(biāo)為1的位置

3 = indexFor(cf) ?

1 = indexFor(lol)，這時(shí)發(fā)現(xiàn)數(shù)組下標(biāo)為1的位置已經(jīng)有值了，我們把lol:3放到鏈表的第一位，將原先的dnf:1用鏈表的形式放到lol鍵值對(duì)的下面

jdk1.7是頭插法
jdk1.8是尾插法

在獲取key為dnf的鍵值對(duì)時(shí)，1=hash(dnf)，得到這個(gè)鍵值對(duì)在數(shù)組下標(biāo)為1的位置，dnf和lol不相等，和下一個(gè)元素比較，相等返回。set和get的過(guò)程就是這么簡(jiǎn)單。先定位到槽的位置（即數(shù)組中的位置），再遍歷鏈表找到相同的元素。

由上圖可以看出，HashMap在發(fā)生hash沖突的時(shí)候用的是鏈地址法，解決hash沖突并不只有這一種方法，常見(jiàn)的有如下四種方法

開放定址法

鏈地址法

再哈希法

公共溢出區(qū)域法。

JDK1.7源碼

幾個(gè)重要的屬性

//初始容量是16，且容量必須是2的倍數(shù) static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;//最大容量是2的30次方 static?final?int?MAXIMUM_CAPACITY?=?1?<<?30;//負(fù)載因子 static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;static?final?Entry<?,?>[]?EMPTY_TABLE?=?{};//HashMap的主干是一個(gè)Entry數(shù)組,在需要的時(shí)候進(jìn)行擴(kuò)容，長(zhǎng)度必須是2的被數(shù) transient?Entry<K,V>[]?table?=?(Entry<K,V>[])?EMPTY_TABLE;//放置的key-value對(duì)的個(gè)數(shù) transient?int?size;//進(jìn)行擴(kuò)容的閾值，值為?capacity?*?load?factor，即容量?*?負(fù)載因子 int?threshold;//負(fù)載因子 final?float?loadFactor;

這里說(shuō)一下threshold和loadFactor，threshold = capacity * load factor，即擴(kuò)容的閾值=數(shù)組長(zhǎng)度 * 負(fù)載因子，如果hashmap中放了16個(gè)元素，負(fù)載因子為0.75，則擴(kuò)容閾值為16*0.75=12

負(fù)載因子越小，容易擴(kuò)容，浪費(fèi)空間，但查找效率高

負(fù)載因子越大，不易擴(kuò)容，對(duì)空間的利用更加充分，查找效率低（鏈表拉長(zhǎng)）

存儲(chǔ)數(shù)據(jù)的靜態(tài)內(nèi)部類，數(shù)組+鏈表，這里的數(shù)組指的就是Entry數(shù)組

static?class?Entry<K,V>?implements?Map.Entry<K,V>?{final?K?key;V?value;Entry<K,V>?next;//存儲(chǔ)指向下一個(gè)Entry的引用，單鏈表結(jié)構(gòu)int?hash;//對(duì)key的hashcode值進(jìn)行hash運(yùn)算后得到的值，存儲(chǔ)在Entry，避免重復(fù)計(jì)算Entry(int?h,?K?k,?V?v,?Entry<K,V>?n)?{value?=?v;next?=?n;key?=?k;hash?=?h;} }

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

其他都是在此基礎(chǔ)上的擴(kuò)展，主要就是設(shè)置初始容量和負(fù)載因子，這2個(gè)參數(shù)前面介紹過(guò)了哈。

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;threshold?=?initialCapacity;init(); }

最重要的知識(shí)點(diǎn)來(lái)了，對(duì)著流程看源碼比較好理解

put方法的執(zhí)行過(guò)程

key為null直接放在table[0]處，對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;

如果節(jié)點(diǎn)已經(jīng)存在就替換old value(保證key的唯一性)，并返回old Value

如果達(dá)到擴(kuò)容的閾值（超過(guò)capacity * load factor），并且發(fā)生碰撞，就要resize

將元素放到bucket的首位，即頭插法

public?V?put(K?key,?V?value)?{//hashmap的數(shù)組為空if?(table?==?EMPTY_TABLE)?{inflateTable(threshold);}if?(key?==?null)return?putForNullKey(value);//獲取hash值int?hash?=?hash(key);//找到應(yīng)該放到table的哪個(gè)位置int?i?=?indexFor(hash,?table.length);//遍歷table[i]位置的鏈表，查找相同的key,若找到則使用新的value替換oldValue,并返回oldValuefor?(Entry<K,V>?e?=?table[i];?e?!=?null;?e?=?e.next)?{Object?k;//如果key已經(jīng)存在，將value設(shè)置為新的，并返回舊的value值if?(e.hash?==?hash?&&?((k?=?e.key)?==?key?||?key.equals(k)))?{V?oldValue?=?e.value;e.value?=?value;e.recordAccess(this);return?oldValue;}}modCount++;//將元素放到table[i]，新的元素總在table[i]位置的第一個(gè)元素，原來(lái)的元素后移addEntry(hash,?key,?value,?i);return?null; }

為空時(shí)，HashMap還沒(méi)有創(chuàng)建這個(gè)數(shù)組，有可能用的是默認(rèn)的16的初始值，還有可能自定義了長(zhǎng)度，這時(shí)需要把數(shù)組長(zhǎng)度變?yōu)?的最小倍數(shù)，并且這個(gè)2的倍數(shù)大于等于初始容量

private?void?inflateTable(int?toSize)?{//返回大于或等于最接近2的冪數(shù)int?capacity?=?roundUpToPowerOf2(toSize);threshold?=?(int)?Math.min(capacity?*?loadFactor,?MAXIMUM_CAPACITY?+?1);table?=?new?Entry[capacity];initHashSeedAsNeeded(capacity); }

若key為null，則將值放在table[0]這個(gè)鏈上

private?V?putForNullKey(V?value)?{for?(Entry<K,V>?e?=?table[0];?e?!=?null;?e?=?e.next)?{if?(e.key?==?null)?{V?oldValue?=?e.value;e.value?=?value;e.recordAccess(this);return?oldValue;}}modCount++;addEntry(0,?null,?value,?0);return?null; }

找到應(yīng)該放在數(shù)組的位置，h & (length-1)這個(gè)式子你可以認(rèn)為hash值對(duì)數(shù)組長(zhǎng)度取余，后面會(huì)說(shuō)到這個(gè)式子

static?int?indexFor(int?h,?int?length)?{//?assert?Integer.bitCount(length)?==?1?:?"length?must?be?a?non-zero?power?of?2";return?h?&?(length-1); }

添加元素

void?addEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{//?容量超過(guò)閾值，并且發(fā)生碰撞時(shí)進(jìn)行擴(kuò)容if?((size?>=?threshold)?&&?(null?!=?table[bucketIndex]))?{//?數(shù)組擴(kuò)容為原來(lái)的2倍，并將元素復(fù)制到新數(shù)組上resize(2?*?table.length);//?重新計(jì)算hash值，如果不做特殊設(shè)置的話，和之前算出來(lái)的hash值一樣hash?=?(null?!=?key)???hash(key)?:?0;bucketIndex?=?indexFor(hash,?table.length);}createEntry(hash,?key,?value,?bucketIndex); }

將新增加的元素放到table的第一位，并且將其他元素跟在第一個(gè)元素后面

void?createEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{Entry<K,V>?e?=?table[bucketIndex];table[bucketIndex]?=?new?Entry<>(hash,?key,?value,?e);size++; }

容量超過(guò)閾值并且發(fā)生碰撞，開始擴(kuò)容

void?resize(int?newCapacity)?{Entry[]?oldTable?=?table;int?oldCapacity?=?oldTable.length;//容量已經(jīng)達(dá)到最大if?(oldCapacity?==?MAXIMUM_CAPACITY)?{threshold?=?Integer.MAX_VALUE;return;}Entry[]?newTable?=?new?Entry[newCapacity];transfer(newTable,?initHashSeedAsNeeded(newCapacity));table?=?newTable;threshold?=?(int)Math.min(newCapacity?*?loadFactor,?MAXIMUM_CAPACITY?+?1); }

重新計(jì)算元素在新的數(shù)組中的位置，并進(jìn)行復(fù)制處理，initHashSeedAsNeeded函數(shù)默認(rèn)情況下會(huì)一直返回false，即rehash在默認(rèn)情況下為false

void?transfer(Entry[]?newTable,?boolean?rehash)?{int?newCapacity?=?newTable.length;//?遍歷數(shù)組for?(Entry<K,V>?e?:?table)?{//?遍歷鏈表while(null?!=?e)?{Entry<K,V>?next?=?e.next;if?(rehash)?{e.hash?=?null?==?e.key???0?:?hash(e.key);}int?i?=?indexFor(e.hash,?newCapacity);e.next?=?newTable[i];newTable[i]?=?e;e?=?next;}} }

這個(gè)transfer函數(shù)挺有意思的，如果你仔細(xì)理解它的復(fù)制過(guò)程，會(huì)發(fā)現(xiàn)有如下2個(gè)特別有意思的地方

原來(lái)在oldTable[i]位置的元素，會(huì)被放到newTable[i]或者newTable[i+oldTable.length]的位置

鏈表在轉(zhuǎn)移的時(shí)候會(huì)反轉(zhuǎn)

這2個(gè)點(diǎn)需要注意一下，我會(huì)在JDK1.8中再次提到這2個(gè)點(diǎn)

get方法的執(zhí)行過(guò)程

key為null直接從table[0]處取，對(duì)key的hashCode()做hash運(yùn)算，計(jì)算index;

通過(guò)key.equals(k)去查找對(duì)應(yīng)的Entry，接著返回value

public?V?get(Object?key)?{if?(key?==?null)return?getForNullKey();Entry<K,V>?entry?=?getEntry(key);return?null?==?entry???null?:?entry.getValue(); }

從table[0]初獲取key為null的值

private?V?getForNullKey()?{if?(size?==?0)?{return?null;}for?(Entry<K,V>?e?=?table[0];?e?!=?null;?e?=?e.next)?{if?(e.key?==?null)return?e.value;}return?null; }

key不為null時(shí)

final?Entry<K,V>?getEntry(Object?key)?{if?(size?==?0)?{return?null;}int?hash?=?(key?==?null)???0?:?hash(key);for?(Entry<K,V>?e?=?table[indexFor(hash,?table.length)];e?!=?null;e?=?e.next)?{Object?k;if?(e.hash?==?hash?&&((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))return?e;}return?null; }

JDK1.8源碼

jdk1.8存取key為null的數(shù)據(jù)并沒(méi)有進(jìn)行特判，而是通過(guò)將hash值返回為0將其放在table[0]處

put執(zhí)行過(guò)程

對(duì)key的hashcode()高16位和低16位進(jìn)行異或運(yùn)算求出具體的hash值

如果table數(shù)組沒(méi)有初始化，則初始化table數(shù)組長(zhǎng)度為16

根據(jù)hash值計(jì)算index，如果沒(méi)碰撞則直接放到bucket里（bucket可為鏈表或者紅黑樹）

如果碰撞導(dǎo)致鏈表過(guò)長(zhǎng)，就把鏈表轉(zhuǎn)為紅黑樹

如果key已經(jīng)存在，用new value替換old value，并返回old value

如果超過(guò)擴(kuò)容的閾值則進(jìn)行擴(kuò)容，threshold = capacity * load factor

jdk1.8和jdk1.7重新獲取元素值在新數(shù)組中所處的位置的算法發(fā)生了變化（實(shí)際效果沒(méi)發(fā)生改變）

jdk1.7，hash & (length-1)

jdk1.8，判斷原來(lái)hash值要新增的bit位是0還是1。假如是0，放到newTable[i]，否則放到newTable[i+oldTable.length]

get執(zhí)行過(guò)程

對(duì)key的hashcode()高16位和低16位進(jìn)行異或運(yùn)算求出具體的hash值

如果在bucket里的第一個(gè)節(jié)點(diǎn)直接命中，則直接返回

如果有沖突，通過(guò)key.equals(k)去查找對(duì)應(yīng)的Node，并返回value。在樹中查找的效率為O(logn)，在鏈表中查找的效率為O(n)

常見(jiàn)面試題

HashMap，HashTable，ConcurrentHashMap之間的區(qū)別

對(duì)象key和value是否允許為空是否線程安全

HashMap	key和value都允許為null	否
HashTable	key和value都不允許為null	是
ConcurrentHashMap	key和value都不允許為null	是

HashMap在什么條件下擴(kuò)容

jdk1.7

超過(guò)擴(kuò)容的閾值

發(fā)生碰撞

jdk1.8

超過(guò)擴(kuò)容的閾值

HashMap的大小為什么是2的n次方

為了通過(guò)hash值確定元素在數(shù)組中存的位置，我們需要進(jìn)行如下操作hash%length，當(dāng)時(shí)%操作比較耗時(shí)間，所以優(yōu)化為 hash & (length - 1)

當(dāng)length為2的n次方時(shí)，hash & (length - 1) =hash % length

我們假設(shè)數(shù)組的長(zhǎng)度為15和16，hash碼為8和9

h & (length - 1)hlengthindex

8 & (15 - 1)	0100	1110	0100
9 & (15 - 1)	0101	1110	0100
8 & (16 - 1)	0100	1111	0100
9 & (16 - 1)	0101	1111	0101

可以看出數(shù)組長(zhǎng)度為15的時(shí)候，hash碼為8和9的元素被放到數(shù)組中的同一個(gè)位置形成鏈表，鍵低了查詢效率，當(dāng)hahs碼和15-1(1110)進(jìn)行&時(shí)，最后一位永遠(yuǎn)是0，這樣0001，0011，0101，1001，1011，0111，1101這些位置永遠(yuǎn)不會(huì)被放置元素，這樣會(huì)導(dǎo)致

空間浪費(fèi)大

增加了碰撞的幾率，減慢查詢的效率

當(dāng)數(shù)組長(zhǎng)度為時(shí)，的所有位都是1，如8-1=7即111，那么進(jìn)行低位&運(yùn)算時(shí)，值總與原來(lái)的hash值相同，降低了碰撞的概率

JDK1.8發(fā)生了哪些變化？

由數(shù)組+鏈表改為數(shù)組+鏈表+紅黑樹，當(dāng)鏈表的長(zhǎng)度超過(guò)8時(shí)，鏈表變?yōu)榧t黑樹。
為什么要這么改？
我們知道鏈表的查找效率為O(n)，而紅黑樹的查找效率為O（logn），查找效率變高了。
為什么不直接用紅黑樹？
因?yàn)榧t黑樹的查找效率雖然變高了，但是插入效率變低了，如果從一開始就用紅黑樹并不合適。從概率學(xué)的角度選了一個(gè)合適的臨界值為8

優(yōu)化了hash算法

計(jì)算元素在新數(shù)組中位置的算法發(fā)生了變化，新算法通過(guò)新增位判斷oldTable[i]應(yīng)該放在newTable[i]還是newTable[i+oldTable.length]

頭插法改為尾插法，擴(kuò)容時(shí)鏈表沒(méi)有發(fā)生倒置（避免形成死循環(huán)）

HashMap在高并發(fā)下會(huì)發(fā)生什么問(wèn)題？

多線程擴(kuò)容，會(huì)讓鏈表形成環(huán)，從而造成死循環(huán)

多線程put可能導(dǎo)致元素丟失

如何避免HashMap在高并發(fā)下的問(wèn)題？

使用ConcurrentHashMap

用Collections.synchronizedMap(hashMap)包裝成同步集合

最后，再附上我歷時(shí)三個(gè)月總結(jié)的?Java 面試 + Java 后端技術(shù)學(xué)習(xí)指南，這是本人這幾年及春招的總結(jié)，目前，已經(jīng)拿到了大廠offer，拿去不謝！

下載方式

1.?首先掃描下方二維碼

2.?后臺(tái)回復(fù)「Java面試」即可獲取

總結(jié)

以上是生活随笔為你收集整理的去哪面试都会问的HashMap的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。