摘要

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

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

1、HashMap添加一個(gè)鍵值對(duì)的過程是怎么樣的?

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

1.初始化table

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

2.計(jì)算hash值

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

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

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

table[i]==null

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

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

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

table[i] instanceof TreeNode

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

其他情況

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

4.擴(kuò)容

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

源代碼如下：

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

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

例如：

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

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

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

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

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

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

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

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

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

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

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

背景

假設(shè)我們有一個(gè)KeyObject類，假設(shè)我們認(rèn)為兩個(gè)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中就可以同時(shí)存在key1和key2了。

打印結(jié)果：

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

執(zhí)行以下代碼：

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

輸出結(jié)果：

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

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

輸出結(jié)果如下：

總結(jié)

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

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

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