我在面試Java初級開發(fā)的時候，經(jīng)常會問：你有沒有重寫過hashcode方法？不少候選人直接說沒寫過。我就想，或許真的沒寫過，于是就再通過一個問題確認(rèn)：你在用HashMap的時候，鍵(Key)部分，有沒有放過自定義對象？而這個時候，候選人說放過，于是兩個問題的回答就自相矛盾了。

最近問下來，這個問題普遍回答不大好，于是在本文里，就干脆從hash表講起，講述HashMap的存數(shù)據(jù)規(guī)則，由此大家就自然清楚上述問題的答案了。

1. 通過Hash算法來了解HashMap對象的高效性

我們先復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)里的一個知識點：在一個長度為n(假設(shè)是10000)的線性表(假設(shè)是ArrayList)里，存放著無序的數(shù)字；如果我們要找一個指定的數(shù)字，就不得不通過從頭到尾依次遍歷來查找，這樣的平均查找次數(shù)是n除以2(這里是5000)。

我們再來觀察Hash表(這里的Hash表純粹是數(shù)據(jù)結(jié)構(gòu)上的概念，和Java無關(guān))。它的平均查找次數(shù)接近于1，代價相當(dāng)小，關(guān)鍵是在Hash表里，存放在其中的數(shù)據(jù)和它的存儲位置是用Hash函數(shù)關(guān)聯(lián)的。

我們假設(shè)一個Hash函數(shù)是x*x%5。當(dāng)然實際情況里不可能用這么簡單的Hash函數(shù)，我們這里純粹為了說明方便，而Hash表是一個長度是11的線性表。如果我們要把6放入其中，那么我們首先會對6用Hash函數(shù)計算一下，結(jié)果是1，所以我們就把6放入到索引號是1這個位置。同樣如果我們要放數(shù)字7，經(jīng)過Hash函數(shù)計算，7的結(jié)果是4，那么它將被放入索引是4的這個位置。這個效果如下圖所示。

這樣做的好處非常明顯。比如我們要從中找6這個元素，我們可以先通過Hash函數(shù)計算6的索引位置，然后直接從1號索引里找到它了。

不過我們會遇到“Hash值沖突”這個問題。比如經(jīng)過Hash函數(shù)計算后，7和8會有相同的Hash值，對此Java的HashMap對象采用的是”鏈地址法“的解決方案。效果如下圖所示。

具體的做法是，為所有Hash值是i的對象建立一個同義詞鏈表。假設(shè)我們在放入8的時候，發(fā)現(xiàn)4號位置已經(jīng)被占，那么就會新建一個鏈表結(jié)點放入8。同樣，如果我們要找8，那么發(fā)現(xiàn)4號索引里不是8，那會沿著鏈表依次查找。

雖然我們還是無法徹底避免Hash值沖突的問題，但是Hash函數(shù)設(shè)計合理，仍能保證同義詞鏈表的長度被控制在一個合理的范圍里。這里講的理論知識并非無的放矢，大家能在后文里清晰地了解到重寫hashCode方法的重要性。

2. 為什么要重寫equals和hashCode方法

當(dāng)我們用HashMap存入自定義的類時，如果不重寫這個自定義類的equals和hashCode方法，得到的結(jié)果會和我們預(yù)期的不一樣。我們來看WithoutHashCode.java這個例子。

在其中的第2到第18行，我們定義了一個Key類；在其中的第3行定義了唯一的一個屬性id。當(dāng)前我們先注釋掉第9行的equals方法和第16行的hashCode方法。

1 import java.util.HashMap;2 class Key {3 private Integer id;4 public Integer getId()5 {return id; }6 public Key(Integer id)7 {this.id = id; }8 //故意先注釋掉equals和hashCode方法9 // public boolean equals(Object o) {10 // if (o == null || !(o instanceof Key))11 // { return false; }12 // else13 // { return this.getId().equals(((Key) o).getId());}14 // }15 16 // public int hashCode()17 // { return id.hashCode(); }18 }19 20 public class WithoutHashCode {21 public static void main(String[] args) {22 Key k1 = new Key(1);23 Key k2 = new Key(1);24 HashMap hm = new HashMap();25 hm.put(k1, "Key with id is 1"); 26 System.out.println(hm.get(k2)); 27 }28 }

在main函數(shù)里的第22和23行，我們定義了兩個Key對象，它們的id都是1，就好比它們是兩把相同的都能打開同一扇門的鑰匙。

在第24行里，我們通過泛型創(chuàng)建了一個HashMap對象。它的鍵部分可以存放Key類型的對象，值部分可以存儲String類型的對象。

在第25行里，我們通過put方法把k1和一串字符放入到hm里；而在第26行，我們想用k2去從HashMap里得到值；這就好比我們想用k1這把鑰匙來鎖門，用k2來開門。這是符合邏輯的，但從當(dāng)前結(jié)果看，26行的返回結(jié)果不是我們想象中的那個字符串，而是null。

原因有兩個—沒有重寫。第一是沒有重寫hashCode方法，第二是沒有重寫equals方法。

當(dāng)我們往HashMap里放k1時，首先會調(diào)用Key這個類的hashCode方法計算它的hash值，隨后把k1放入hash值所指引的內(nèi)存位置。

關(guān)鍵是我們沒有在Key里定義hashCode方法。這里調(diào)用的仍是Object類的hashCode方法(所有的類都是Object的子類)，而Object類的hashCode方法返回的hash值其實是k1對象的內(nèi)存地址(假設(shè)是1000)。

如果我們隨后是調(diào)用hm.get(k1)，那么我們會再次調(diào)用hashCode方法(還是返回k1的地址1000)，隨后根據(jù)得到的hash值，能很快地找到k1。

但我們這里的代碼是hm.get(k2)，當(dāng)我們調(diào)用Object類的hashCode方法(因為Key里沒定義)計算k2的hash值時，其實得到的是k2的內(nèi)存地址(假設(shè)是2000)。由于k1和k2是兩個不同的對象，所以它們的內(nèi)存地址一定不會相同，也就是說它們的hash值一定不同，這就是我們無法用k2的hash值去拿k1的原因。

當(dāng)我們把第16和17行的hashCode方法的注釋去掉后，會發(fā)現(xiàn)它是返回id屬性的hashCode值，這里k1和k2的id都是1,所以它們的hash值是相等的。

我們再來更正一下存k1和取k2的動作。存k1時，是根據(jù)它id的hash值，假設(shè)這里是100，把k1對象放入到對應(yīng)的位置。而取k2時，是先計算它的hash值(由于k2的id也是1，這個值也是100)，隨后到這個位置去找。

但結(jié)果會出乎我們意料：明明100號位置已經(jīng)有k1，但第26行的輸出結(jié)果依然是null。其原因就是沒有重寫Key對象的equals方法。

HashMap是用鏈地址法來處理沖突，也就是說，在100號位置上，有可能存在著多個用鏈表形式存儲的對象。它們通過hashCode方法返回的hash值都是100。

當(dāng)我們通過k2的hashCode到100號位置查找時，確實會得到k1。但k1有可能僅僅是和k2具有相同的hash值，但未必和k2相等(k1和k2兩把鑰匙未必能開同一扇門)，這個時候，就需要調(diào)用Key對象的equals方法來判斷兩者是否相等了。

由于我們在Key對象里沒有定義equals方法，系統(tǒng)就不得不調(diào)用Object類的equals方法。由于Object的固有方法是根據(jù)兩個對象的內(nèi)存地址來判斷，所以k1和k2一定不會相等，這就是為什么依然在26行通過hm.get(k2)依然得到null的原因。

為了解決這個問題，我們需要打開第9到14行equals方法的注釋。在這個方法里，只要兩個對象都是Key類型，而且它們的id相等，它們就相等。

3. 對面試問題的說明

由于在項目里經(jīng)常會用到HashMap，所以我在面試的時候一定會問這個問題∶你有沒有重寫過hashCode方法？你在使用HashMap時有沒有重寫hashCode和equals方法？你是怎么寫的？

根據(jù)問下來的結(jié)果，我發(fā)現(xiàn)初級程序員對這個知識點普遍沒掌握好。重申一下，如果大家要在HashMap的“鍵”部分存放自定義的對象，一定要在這個對象里用自己的equals和hashCode方法來覆蓋Object里的同名方法。?

ps: 想要查看之前的文章都已經(jīng)保存

- THE END -

作者簡介

Mr.W

白天搬磚，晚上砌夢想。

相信每個人有故事，程序員更是有許多事故，書寫最接地氣的程序員故事,為大家找出更好的資料。

總結(jié)

以上是生活随笔為你收集整理的为什么使用HashMap需要重写hashcode和equals方法_为什么要重写hashcode和equals方法？你能说清楚了吗...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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