作者：hsm_computer
來源：cnblogs.com/JavaArchitect/p/10474448.html
我在面試Java初級開發的時候，經常會問：你有沒有重寫過hashcode方法？
不少候選人直接說沒寫過，
我就想，或許真的沒寫過，于是就再通過一個問題確認：你在用HashMap的時候，鍵（Key）部分，有沒有放過自定義物件？
而這個時候，候選人說放過，于是兩個問題的回答就自相矛盾了，
最近問下來，這個問題普遍回答不大好，于是在本文里，就干脆從hash表講起，講述HashMap的存資料規則，由此大家就自然清楚上述問題的答案了，
1. 通過Hash演算法來了解HashMap物件的高效性
我們先復習資料結構里的一個知識點：在一個長度為n（假設是10000）的線性表（假設是ArrayList）里，存放著無序的數字；如果我們要找一個指定的數字，就不得不通過從頭到尾依次遍歷來查找，這樣的平均查找次數是n除以2（這里是5000），
我們再來觀察Hash表（這里的Hash表純粹是資料結構上的概念，和Java無關），它的平均查找次數接近于1，代價相當小，關鍵是在Hash表里，存放在其中的資料和它的存盤位置是用Hash函式關聯的，
我們假設一個Hash函式是x*x%5，當然實際情況里不可能用這么簡單的Hash函式，我們這里純粹為了說明方便，而Hash表是一個長度是11的線性表，如果我們要把6放入其中，那么我們首先會對6用Hash函式計算一下，結果是1，所以我們就把6放入到索引號是1這個位置，同樣如果我們要放數字7，經過Hash函式計算，7的結果是4，那么它將被放入索引是4的這個位置，這個效果如下圖所示，
這樣做的好處非常明顯，比如我們要從中找6這個元素，我們可以先通過Hash函式計算6的索引位置，然后直接從1號索引里找到它了，
不過我們會遇到“Hash值沖突”這個問題，比如經過Hash函式計算后，7和8會有相同的Hash值，對此Java的HashMap物件采用的是”鏈地址法“的解決方案，效果如下圖所示，
具體的做法是，為所有Hash值是i的物件建立一個同義詞鏈表，假設我們在放入8的時候，發現4號位置已經被占，那么就會新建一個鏈表結點放入8，同樣，如果我們要找8，那么發現4號索引里不是8，那會沿著鏈表依次查找，
雖然我們還是無法徹底避免Hash值沖突的問題，但是Hash函式設計合理，仍能保證同義詞鏈表的長度被控制在一個合理的范圍里，這里講的理論知識并非無的放矢，大家能在后文里清晰地了解到重寫hashCode方法的重要性，
2. 為什么要重寫equals和hashCode方法
當我們用HashMap存入自定義的類時，如果不重寫這個自定義類的equals和hashCode方法，得到的結果會和我們預期的不一樣，我們來看WithoutHashCode.java這個例子，
在其中的第2到第18行，我們定義了一個Key類；在其中的第3行定義了唯一的一個屬性id，當前我們先注釋掉第9行的equals方法和第16行的hashCode方法，
import java.util.HashMap;
class Key {
private Integer id;
public Key(Integer id) {
this.id = id;
}
public Integer getId() {
return id;
}
//故意先注釋掉equals和hashCode方法
// public boolean equals(Object o) {
// if (o == null || !(o instanceof Key))
// { return false; }
// else
// { return this.getId().equals(((Key) o).getId());}
// }
// public int hashCode()
// { return id.hashCode(); }
}
public class WithoutHashCode {
public static void main(String\[\] args) {
Key k1 = new Key(1);
Key k2 = new Key(1);
HashMap<Key, String> hm = new HashMap<Key, String>();
hm.put(k1, "Key with id is 1");
System.out.println(hm.get(k2));
}
}
在main函式里的第22和23行，我們定義了兩個Key物件，它們的id都是1，就好比它們是兩把相同的都能打開同一扇門的鑰匙，
在第24行里，我們通過泛型創建了一個HashMap物件，它的鍵部分可以存放Key型別的物件，值部分可以存盤String型別的物件，
在第25行里，我們通過put方法把k1和一串字符放入到hm里；而在第26行，我們想用k2去從HashMap里得到值；這就好比我們想用k1這把鑰匙來鎖門，用k2來開門，這是符合邏輯的，但從當前結果看，26行的回傳結果不是我們想象中的那個字串，而是null，
原因有兩個—沒有重寫，第一是沒有重寫hashCode方法，第二是沒有重寫equals方法，
當我們往HashMap里放k1時，首先會呼叫Key這個類的hashCode方法計算它的hash值，隨后把k1放入hash值所指引的記憶體位置，
關鍵是我們沒有在Key里定義hashCode方法，這里呼叫的仍是Object類的hashCode方法（所有的類都是Object的子類），而Object類的hashCode方法回傳的hash值其實是k1物件的記憶體地址（假設是1000），
如果我們隨后是呼叫hm.get(k1)，那么我們會再次呼叫hashCode方法（還是回傳k1的地址1000），隨后根據得到的hash值，能很快地找到k1，
但我們這里的代碼是hm.get(k2)，當我們呼叫Object類的hashCode方法（因為Key里沒定義）計算k2的hash值時，其實得到的是k2的記憶體地址（假設是2000），
由于k1和k2是兩個不同的物件，所以它們的記憶體地址一定不會相同，也就是說它們的hash值一定不同，這就是我們無法用k2的hash值去拿k1的原因，
當我們把第16和17行的hashCode方法的注釋去掉后，會發現它是回傳id屬性的hashCode值，這里k1和k2的id都是1,所以它們的hash值是相等的，
我們再來更正一下存k1和取k2的動作，存k1時，是根據它id的hash值，假設這里是100，把k1物件放入到對應的位置，而取k2時，是先計算它的hash值（由于k2的id也是1，這個值也是100），隨后到這個位置去找，
但結果會出乎我們意料：明明100號位置已經有k1，但第26行的輸出結果依然是null，其原因就是沒有重寫Key物件的equals方法，
HashMap是用鏈地址法來處理沖突，也就是說，在100號位置上，有可能存在著多個用鏈表形式存盤的物件，它們通過hashCode方法回傳的hash值都是100，
當我們通過k2的hashCode到100號位置查找時，確實會得到k1，但k1有可能僅僅是和k2具有相同的hash值，但未必和k2相等（k1和k2兩把鑰匙未必能開同一扇門），這個時候，就需要呼叫Key物件的equals方法來判斷兩者是否相等了，
由于我們在Key物件里沒有定義equals方法，系統就不得不呼叫Object類的equals方法，由于Object的固有方法是根據兩個物件的記憶體地址來判斷，所以k1和k2一定不會相等，這就是為什么依然在26行通過hm.get(k2)依然得到null的原因，
為了解決這個問題，我們需要打開第9到14行equals方法的注釋，在這個方法里，只要兩個物件都是Key型別，而且它們的id相等，它們就相等，
3. 對面試問題的說明
由于在專案里經常會用到HashMap，所以我在面試的時候一定會問這個問題∶你有沒有重寫過hashCode方法？你在使用HashMap時有沒有重寫hashCode和equals方法？你是怎么寫的？
根據問下來的結果，我發現初級程式員對這個知識點普遍沒掌握好，重申一下，如果大家要在HashMap的“鍵”部分存放自定義的物件，一定要在這個物件里用自己的equals和hashCode方法來覆寫Object里的同名方法，
關注公眾號Java技術堆疊回復"面試"獲取我整理的2020最全面試題及答案，
推薦去我的博客閱讀更多：
1.Java JVM、集合、多執行緒、新特性系列教程
2.Spring MVC、Spring Boot、Spring Cloud 系列教程
3.Maven、Git、Eclipse、Intellij IDEA 系列工具教程
4.Java、后端、架構、阿里巴巴等大廠最新面試題
覺得不錯，別忘了點贊+轉發哦！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/153369.html
標籤：Java