摘要

HashMap的原理也是大廠面試中經(jīng)常會涉及的問題，同時也是工作中常用到的Java容器，本文主要通過對以下問題進(jìn)行分析講解，來幫助大家理解HashMap的原理。

• HashMap添加一個鍵值對的過程是怎么樣的?
• 為什么說HashMap不是線程安全的?
• 為什么要一起重寫hashCode()和equal()方法?

1、HashMap添加一個鍵值對的過程是怎么樣的?

這是網(wǎng)上找的一張流程圖，可以結(jié)合著步驟來看這個流程圖，了解添加鍵值對的過程。

1.初始化table

判斷table是否為空或為null，否則執(zhí)行resize()方法(resize方法一般是擴(kuò)容時調(diào)用，也可以調(diào)用來初始化table)。

2.計算hash值

根據(jù)鍵值key計算hash值。(因為hashCode是一個int類型的變量，是4字節(jié)，32位，所以這里會將hashCode的低16位與高16位進(jìn)行一個異或運算，來保留高位的特征，以便于得到的hash值更加均勻分布)

3.插入或更新節(jié)點

根據(jù)(n - 1) & hash計算得到插入的數(shù)組下標(biāo)i，然后進(jìn)行判斷

table[i]==null

那么說明當(dāng)前數(shù)組下標(biāo)下，沒有hash沖突的元素，直接新建節(jié)點添加。

table[i].hash == hash &&(table[i]== key || (key != null && key.equals(table[i].key)))

判斷table[i]的首個元素是否和key一樣，如果相同直接更新value。

table[i] instanceof TreeNode

判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對。

其他情況

上面的判斷條件都不滿足，說明table[i]存儲的是一個鏈表，那么遍歷鏈表，判斷是否存在已有元素的key與插入鍵值對的key相等，如果是，那么更新value，如果沒有，那么在鏈表末尾插入一個新節(jié)點。插入之后判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹。

4.擴(kuò)容

插入成功后，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold(一般是數(shù)組長度*負(fù)載因子0.75)，如果超過，進(jìn)行擴(kuò)容。

源代碼如下：

2.為什么說HashMap不是線程安全的?

其實通過學(xué)習(xí)HashMap添加鍵值對的方法，我們可以看到整個方法內(nèi)都沒有使用到鎖，所以一旦多線并發(fā)訪問，就有可能造成數(shù)據(jù)不一致的問題，

例如：

如果有兩個添加鍵值對的線程都執(zhí)行到if ((tab = table) == null || (n = tab.length) == 0)這行語句，都對table變量進(jìn)行數(shù)組初始化，就會造成已經(jīng)初始化好的數(shù)組table被覆蓋，然后前面初始化的線程會將鍵值對添加到之前初始化的數(shù)組中去，造成鍵值對丟失。

3.為什么要一起重寫hashCode()和equal()方法?

當(dāng)我們的對象一旦作為HashMap中的key，或者是HashSet中的元素使用時，就必須同時重寫hashCode()和equal()方法

首先看看hashCode()和equal()方法的默認(rèn)實現(xiàn)

可以看到Obejct類中的源碼如下，可以看到equals()方法的默認(rèn)實現(xiàn)是判斷兩個對象的內(nèi)存地址是否相同來決定返回結(jié)果。

網(wǎng)上很多博客說hashCode的默認(rèn)實現(xiàn)是返回內(nèi)存地址，其實不對，以O(shè)penJDK為例，hashCode的默認(rèn)計算方法有5種，有返回隨機(jī)數(shù)的，有返回內(nèi)存地址，具體采用哪一種計算方法取決于運行時庫和JVM的具體實現(xiàn)。

感興趣的朋友可以看看這篇博客 blog.csdn.net/xusiwei1236…

然后看看hashCode()方法，equal()方法在HashMap中的應(yīng)用

為了將一組鍵值對均勻得存儲在一個數(shù)組中，HashMap對key的hashCode進(jìn)行計算得到一個hash值，用hash對數(shù)組長度取模，得到數(shù)組下標(biāo)，將鍵值對存儲在數(shù)組下標(biāo)對應(yīng)的鏈表下(假設(shè)鏈表長度小于8，沒有達(dá)到轉(zhuǎn)換為紅黑樹的閥值)。

下面是添加鍵值對的putVal()方法，當(dāng)數(shù)組下標(biāo)對應(yīng)的是一個鏈表時執(zhí)行的代碼

可以清楚地看到判斷添加的key與鏈表中已存在的key是否相等的方法主要是e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))), 也就是： 1.先判斷hash值是否相等，不相等直接結(jié)束判斷，因為hash值不相等，key肯定不相等。 2.判斷兩個key對象的內(nèi)存地址是否相等(相等指向內(nèi)存中同一個對象)。 3.key不為null，調(diào)用key的equal()方法判斷是否相等，因為有可能兩個key在內(nèi)存中存儲的地址不一樣，但是是相等的。 就像是

背景

假設(shè)我們有一個KeyObject類，假設(shè)我們認(rèn)為兩個KeyObject的屬性a相等，那么KeyObject就是相等的相等的，我們將KeyObject作為HashMap的key，以KeyObject是否相等作為去重標(biāo)準(zhǔn)，不能重復(fù)添加KeyObject相等，value不等的值到HashMap中去

假設(shè)都hashCode()方法和equals()方法都不重寫(結(jié)果：HashMap無法保證去重)

執(zhí)行以下代碼：

如果KeyObject的hashCode()方法和equals()方法都不重寫，那么即便KeyObject的屬性a都是1，key1和key2的hashCode都是不相同的，key1和key2調(diào)用equals()方法也不相等，這樣hashMap中就可以同時存在key1和key2了。

打印結(jié)果：

假如只重寫hashCode()方法(結(jié)果：無法正確地與鏈表元素進(jìn)行相等判斷，從而無法保證去重)

執(zhí)行以下代碼：

此時equal()方法的實現(xiàn)是默認(rèn)實現(xiàn)，也就是當(dāng)兩個對象的內(nèi)存地址相等時，equal()方法才返回true，雖然key1和key2的a屬性是相同的，但是他們在內(nèi)存中是不同的對象，所以key1==key2結(jié)果會是false，KeyObject的equals()方法默認(rèn)實現(xiàn)是判斷兩個對象的內(nèi)存地址，所以 key1.equals(key2)也會是false，所以這兩個鍵值對可以重復(fù)地添加到hashMap中去。

輸出結(jié)果：

假如只重寫equals()方法(結(jié)果：映射到HashMap中不同數(shù)組下標(biāo)，無法保證去重)

假設(shè)只equals()方法，hashCode方法會是默認(rèn)實現(xiàn)，具體的計算方法取決于JVM，(測試時發(fā)現(xiàn)是內(nèi)存地址不同但是相等的對象，它們的hashCode不相同)，所以計算得到的數(shù)組下標(biāo)不相同，會存儲到hashMap中不同數(shù)組下標(biāo)下的鏈表中，也會導(dǎo)致HashMap中存在重復(fù)元素。

輸出結(jié)果如下：

總結(jié)

所以當(dāng)我們的對象一旦作為HashMap中的key，或者是HashSet中的元素使用時，就必須同時重寫hashCode()和equal()方法，因為hashCode會影響key存儲的數(shù)組下標(biāo)及與鏈表元素的初步判斷，equal()是作為判斷key與鏈表中的key是否相等的最后標(biāo)準(zhǔn)。

所以只重寫hashCode()方法，會導(dǎo)致無法正確地與鏈表元素進(jìn)行相等判斷，從而無法保證去重)

只重寫equals()方法導(dǎo)致鍵值對映射到HashMap中不同數(shù)組下標(biāo)，無法保證去重