建站
咨詢
售后
建站咨詢
新聞中心
我在面試 Java初級(jí)開(kāi)發(fā)的時(shí)候，經(jīng)常會(huì)問(wèn)：你有沒(méi)有重寫(xiě)過(guò)hashcode方法？不少候選人直接說(shuō)沒(méi)寫(xiě)過(guò)。我就想，或許真的沒(méi)寫(xiě)過(guò)，于是就再通過(guò)一個(gè)問(wèn)題確認(rèn)：你在用HashMap的時(shí)候，鍵（Key）部分，有沒(méi)有放過(guò)自定義對(duì)象？而這個(gè)時(shí)候，候選人說(shuō)放過(guò)，于是兩個(gè)問(wèn)題的回答就自相矛盾了。
創(chuàng)新互聯(lián)公司專注于五蓮網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供五蓮營(yíng)銷型網(wǎng)站建設(shè)，五蓮網(wǎng)站制作、五蓮網(wǎng)頁(yè)設(shè)計(jì)、五蓮網(wǎng)站官網(wǎng)定制、成都微信小程序服務(wù)，打造五蓮網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供五蓮網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。
最近問(wèn)下來(lái)，這個(gè)問(wèn)題普遍回答不大好，于是在本文里，就干脆從hash表講起，講述HashMap的存數(shù)據(jù)規(guī)則，由此大家就自然清楚上述問(wèn)題的答案了。
# 1、通過(guò)Hash算法來(lái)了解HashMap對(duì)象的高效性
我們先復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)里的一個(gè)知識(shí)點(diǎn)：在一個(gè)長(zhǎng)度為n（假設(shè)是10000）的線性表（假設(shè)是ArrayList）里，存放著無(wú)序的數(shù)字；如果我們要找一個(gè)指定的數(shù)字，就不得不通過(guò)從頭到尾依次遍歷來(lái)查找，這樣的平均查找次數(shù)是n除以2（這里是5000）。
我們?cè)賮?lái)觀察Hash表（這里的Hash表純粹是數(shù)據(jù)結(jié)構(gòu)上的概念，和Java無(wú)關(guān)）。它的平均查找次數(shù)接近于1，代價(jià)相當(dāng)小，關(guān)鍵是在Hash表里，存放在其中的數(shù)據(jù)和它的存儲(chǔ)位置是用Hash函數(shù)關(guān)聯(lián)的。
我們假設(shè)一個(gè)Hash函數(shù)是x*x%5。當(dāng)然實(shí)際情況里不可能用這么簡(jiǎn)單的Hash函數(shù)，我們這里純粹為了說(shuō)明方便，而Hash表是一個(gè)長(zhǎng)度是11的線性表。如果我們要把6放入其中，那么我們首先會(huì)對(duì)6用Hash函數(shù)計(jì)算一下，結(jié)果是1，所以我們就把6放入到索引號(hào)是1這個(gè)位置。同樣如果我們要放數(shù)字7，經(jīng)過(guò)Hash函數(shù)計(jì)算，7的結(jié)果是4，那么它將被放入索引是4的這個(gè)位置。這個(gè)效果如下圖所示。
這樣做的好處非常明顯。比如我們要從中找6這個(gè)元素，我們可以先通過(guò)Hash函數(shù)計(jì)算6的索引位置，然后直接從1號(hào)索引里找到它了。
不過(guò)我們會(huì)遇到“hash值沖突”這個(gè)問(wèn)題。比如經(jīng)過(guò)Hash函數(shù)計(jì)算后，7和8會(huì)有相同的Hash值，對(duì)此Java的HashMap對(duì)象采用的是”鏈地址法“的解決方案。效果如下圖所示。
具體的做法是，為所有Hash值是i的對(duì)象建立一個(gè)同義詞鏈表。假設(shè)我們?cè)诜湃?的時(shí)候，發(fā)現(xiàn)4號(hào)位置已經(jīng)被占，那么就會(huì)新建一個(gè)鏈表結(jié)點(diǎn)放入8。同樣，如果我們要找8，那么發(fā)現(xiàn)4號(hào)索引里不是8，那會(huì)沿著鏈表依次查找。
雖然我們還是無(wú)法徹底避免Hash值沖突的問(wèn)題，但是Hash函數(shù)設(shè)計(jì)合理，仍能保證同義詞鏈表的長(zhǎng)度被控制在一個(gè)合理的范圍里。這里講的理論知識(shí)并非無(wú)的放矢，大家能在后文里清晰地了解到重寫(xiě)hashCode方法的重要性。
# 2、為什么要重寫(xiě)equals和hashCode方法
當(dāng)我們用HashMap存入自定義的類時(shí)，如果不重寫(xiě)這個(gè)自定義類的equals和hashCode方法，得到的結(jié)果會(huì)和我們預(yù)期的不一樣。我們來(lái)看WithoutHashCode.java這個(gè)例子。
在其中的第2到第18行，我們定義了一個(gè)Key類；在其中的第3行定義了唯一的一個(gè)屬性id。當(dāng)前我們先注釋掉第9行的equals方法和第16行的hashCode方法。
在main函數(shù)里的第22和23行，我們定義了兩個(gè)Key對(duì)象，它們的id都是1，就好比它們是兩把相同的都能打開(kāi)同一扇門(mén)的鑰匙。
在第24行里，我們通過(guò)泛型創(chuàng)建了一個(gè)HashMap對(duì)象。它的鍵部分可以存放Key類型的對(duì)象，值部分可以存儲(chǔ)String類型的對(duì)象。
在第25行里，我們通過(guò)put方法把k1和一串字符放入到hm里； 而在第26行，我們想用k2去從HashMap里得到值；這就好比我們想用k1這把鑰匙來(lái)鎖門(mén)，用k2來(lái)開(kāi)門(mén)。這是符合邏輯的，但從當(dāng)前結(jié)果看，26行的返回結(jié)果不是我們想象中的那個(gè)字符串，而是null。
原因有兩個(gè)—沒(méi)有重寫(xiě)。第一是沒(méi)有重寫(xiě)hashCode方法，第二是沒(méi)有重寫(xiě)equals方法。
當(dāng)我們往HashMap里放k1時(shí)，首先會(huì)調(diào)用Key這個(gè)類的hashCode方法計(jì)算它的hash值，隨后把k1放入hash值所指引的內(nèi)存位置。
關(guān)鍵是我們沒(méi)有在Key里定義hashCode方法。這里調(diào)用的仍是Object類的hashCode方法（所有的類都是Object的子類），而Object類的hashCode方法返回的hash值其實(shí)是k1對(duì)象的內(nèi)存地址（假設(shè)是1000）。
如果我們隨后是調(diào)用hm.get(k1)，那么我們會(huì)再次調(diào)用hashCode方法（還是返回k1的地址1000），隨后根據(jù)得到的hash值，能很快地找到k1。
但我們這里的代碼是hm.get(k2)，當(dāng)我們調(diào)用Object類的hashCode方法（因?yàn)镵ey里沒(méi)定義）計(jì)算k2的hash值時(shí)，其實(shí)得到的是k2的內(nèi)存地址（假設(shè)是2000）。由于k1和k2是兩個(gè)不同的對(duì)象，所以它們的內(nèi)存地址一定不會(huì)相同，也就是說(shuō)它們的hash值一定不同，這就是我們無(wú)法用k2的hash值去拿k1的原因。
當(dāng)我們把第16和17行的hashCode方法的注釋去掉后，會(huì)發(fā)現(xiàn)它是返回id屬性的hashCode值，這里k1和k2的id都是1,所以它們的hash值是相等的。
我們?cè)賮?lái)更正一下存k1和取k2的動(dòng)作。存k1時(shí)，是根據(jù)它id的hash值，假設(shè)這里是100，把k1對(duì)象放入到對(duì)應(yīng)的位置。而取k2時(shí)，是先計(jì)算它的hash值（由于k2的id也是1，這個(gè)值也是100），隨后到這個(gè)位置去找。
但結(jié)果會(huì)出乎我們意料：明明100號(hào)位置已經(jīng)有k1，但第26行的輸出結(jié)果依然是null。其原因就是沒(méi)有重寫(xiě)Key對(duì)象的equals方法。
HashMap是用鏈地址法來(lái)處理沖突，也就是說(shuō)，在100號(hào)位置上，有可能存在著多個(gè)用鏈表形式存儲(chǔ)的對(duì)象。它們通過(guò)hashCode方法返回的hash值都是100。
當(dāng)我們通過(guò)k2的hashCode到100號(hào)位置查找時(shí)，確實(shí)會(huì)得到k1。但k1有可能僅僅是和k2具有相同的hash值，但未必和k2相等（k1和k2兩把鑰匙未必能開(kāi)同一扇門(mén)），這個(gè)時(shí)候，就需要調(diào)用Key對(duì)象的equals方法來(lái)判斷兩者是否相等了。
由于我們?cè)贙ey對(duì)象里沒(méi)有定義equals方法，系統(tǒng)就不得不調(diào)用Object類的equals方法。由于Object的固有方法是根據(jù)兩個(gè)對(duì)象的內(nèi)存地址來(lái)判斷，所以k1和k2一定不會(huì)相等，這就是為什么依然在26行通過(guò)hm.get(k2)依然得到null的原因。
為了解決這個(gè)問(wèn)題，我們需要打開(kāi)第9到14行equals方法的注釋。在這個(gè)方法里，只要兩個(gè)對(duì)象都是Key類型，而且它們的id相等，它們就相等。
# 3、對(duì)面試問(wèn)題的說(shuō)明
由于在項(xiàng)目里經(jīng)常會(huì)用到HashMap，所以我在面試的時(shí)候一定會(huì)問(wèn)這個(gè)問(wèn)題。
- 你有沒(méi)有重寫(xiě)過(guò)hashCode方法？
- 你在使用HashMap時(shí)有沒(méi)有重寫(xiě)hashCode和equals方法？你是怎么寫(xiě)的？
- 一個(gè)對(duì)象的hashcode可以改變么？
根據(jù)問(wèn)下來(lái)的結(jié)果，我發(fā)現(xiàn)初級(jí)程序員對(duì)這個(gè)知識(shí)點(diǎn)普遍沒(méi)掌握好。重申一下，如果大家要在HashMap的“鍵”部分存放自定義的對(duì)象，一定要在這個(gè)對(duì)象里用自己的equals和hashCode方法來(lái)覆蓋Object里的同名方法。
新聞名稱：面試題：為什么要重寫(xiě)hashcode和equals方法？
網(wǎng)頁(yè)路徑：http://www.5511xx.com/article/dpogghc.html
