建站
咨詢
售后
建站咨詢
新聞中心
摘要
HashMap的原理也是大廠面試中經(jīng)常會涉及的問題，同時也是工作中常用到的Java容器，本文主要通過對以下問題進行分析講解，來幫助大家理解HashMap的原理。
專注于為中小企業(yè)提供網(wǎng)站制作、做網(wǎng)站服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)望江免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了上千企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。
- HashMap添加一個鍵值對的過程是怎么樣的?
- 為什么說HashMap不是線程安全的?
- 為什么要一起重寫hashCode()和equal()方法?
1、HashMap添加一個鍵值對的過程是怎么樣的?
這是網(wǎng)上找的一張流程圖，可以結(jié)合著步驟來看這個流程圖，了解添加鍵值對的過程。
1.初始化table
判斷table是否為空或為null，否則執(zhí)行resize()方法(resize方法一般是擴容時調(diào)用，也可以調(diào)用來初始化table)。
2.計算hash值
根據(jù)鍵值key計算hash值。(因為hashCode是一個int類型的變量，是4字節(jié)，32位，所以這里會將hashCode的低16位與高16位進行一個異或運算，來保留高位的特征，以便于得到的hash值更加均勻分布)
3.插入或更新節(jié)點
根據(jù)(n - 1) & hash計算得到插入的數(shù)組下標(biāo)i，然后進行判斷
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.擴容
插入成功后，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold(一般是數(shù)組長度*負(fù)載因子0.75)，如果超過，進行擴容。
源代碼如下：
2.為什么說HashMap不是線程安全的?
其實通過學(xué)習(xí)HashMap添加鍵值對的方法，我們可以看到整個方法內(nèi)都沒有使用到鎖，所以一旦多線并發(fā)訪問，就有可能造成數(shù)據(jù)不一致的問題，
例如：
如果有兩個添加鍵值對的線程都執(zhí)行到if ((tab = table) == null || (n = tab.length) == 0)這行語句，都對table變量進行數(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種，有返回隨機數(shù)的，有返回內(nèi)存地址，具體采用哪一種計算方法取決于運行時庫和JVM的具體實現(xiàn)。
感興趣的朋友可以看看這篇博客 blog.csdn.net/xusiwei1236…
然后看看hashCode()方法，equal()方法在HashMap中的應(yīng)用
為了將一組鍵值對均勻得存儲在一個數(shù)組中，HashMap對key的hashCode進行計算得到一個hash值，用hash對數(shù)組長度取模，得到數(shù)組下標(biāo)，將鍵值對存儲在數(shù)組下標(biāo)對應(yīng)的鏈表下(假設(shè)鏈表長度小于8，沒有達到轉(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é)果：無法正確地與鏈表元素進行相等判斷，從而無法保證去重)
執(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)致無法正確地與鏈表元素進行相等判斷，從而無法保證去重)
只重寫equals()方法導(dǎo)致鍵值對映射到HashMap中不同數(shù)組下標(biāo)，無法保證去重
網(wǎng)站名稱：面試官：談一談你對HashMap的理解？
網(wǎng)站鏈接：http://m.5511xx.com/article/cophpjh.html
