作者：hsm_computer
來源：https://www.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方法。
在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方法？你是怎麼寫的？
- 一個對象的hashcode可以改變麼？
根據問下來的結果，我發現初級程序員對這個知識點普遍沒掌握好。重申一下，如果大家要在HashMap的“鍵”部分存放自定義的對象，一定要在這個對象裡用自己的equals和hashCode方法來覆蓋Object裡的同名方法。
閱讀更多 程序員BUG 的文章
