前言

在面試 Java的時候，經(jīng)常會被問的一個問題是：你有沒有重寫過 hashcode方法唁情？不少候選人直接說沒寫過笋敞。或許真的是沒寫過荠瘪，于是還可以再通過一個問題確認(rèn)：你在用 HashMap的時候夯巷，鍵（ Key）部分，有沒有放過自定義對象哀墓？而這個時候趁餐，候選人說放過，于是兩個問題的回答就自相矛盾了篮绰。

其實(shí)很多人這個問題普遍回答得都不大好后雷，于是在本文里，就干脆 從 hash表講起吠各，講述HashMap的存數(shù)據(jù)規(guī)則臀突，由此大家就自然清楚上述問題的答案了。

Hash算法

先復(fù)習(xí)一下數(shù)據(jù)結(jié)構(gòu)里的一個知識點(diǎn)：在一個長度為 n（假設(shè)是 10000）的線性表（假設(shè)是ArrayList）里贾漏，存放著無序的數(shù)字候学；如果我們要找一個指定的數(shù)字，就不得不通過從頭到尾依次遍歷來查找纵散。

我們再來觀察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)然實(shí)際情況里不可能用這么簡單的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é)點(diǎn)放入 8。同樣偷崩，如果我們要找 8辟拷，那么發(fā)現(xiàn) 4號索引里不是 8，那會沿著鏈表依次查找阐斜。

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

為什么要重寫equals和hashCode算法

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

我們定義了一個 Key類颜骤；在其中定義了唯一的一個屬性 id。當(dāng)前我們先注釋 equals()方法和 hashCode()方法捣卤。

在 main函數(shù)里忍抽，我們定義了兩個 Key對象八孝，它們的 id都是 1，邏輯上我們就認(rèn)為它們是兩個相同的對象鸠项；就好比它們是兩把相同的鑰匙干跛，都能打開同一扇門。

在 main函數(shù)里祟绊，我們通過泛型創(chuàng)建了一個HashMap<Key, String>的對象楼入。它的鍵部分（HashMap的key）可以存放 Key類型的對象，值部分可以存儲String類型的對象牧抽。

在 main函數(shù)里嘉熊，我們通過 put方法把 key1和一個字符串放入到 hashMap里；并且我們想用 key2去從HashMap里得到值扬舒；這就好比一把鎖有兩把一模一樣的鑰匙阐肤，用key1可以打開鎖，用key2也可以打開鎖讲坎。這是符合邏輯的孕惜，但從當(dāng)前結(jié)果看， 返回結(jié)果不是我們想象中的那個字符串晨炕，而是 null诊赊。

原因有兩個：一是沒有重寫hashCode方法，二是沒有重寫equals方法府瞄。

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

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

如果我們隨后是調(diào)用 hashMap.get(key1)秆撮，那么我們會再次調(diào)用 hashCode方法（還是返回 key1的地址 1000），隨后根據(jù)得到的 hash值换况，能很快地找到 key1职辨。

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

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

我們再來更正一下存 key1和取 key2的動作。存 key1時榜聂，是根據(jù)它 id的 hash值搞疗，假設(shè)這里是 100，把 key1對象放入到對應(yīng)的位置须肆。而取 key2時匿乃，是先計算它的 hash值（由于 key2的id也是 1，這個值也是 100）休吠，隨后到這個位置去找。

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

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

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

由于我們在 Key對象里沒有定義 equals方法，系統(tǒng)就不得不調(diào)用 Object類的 equals方法艳狐。由于 Object的固有方法是根據(jù)兩個對象的內(nèi)存地址來判斷定硝，所以 key1和 key2一定不會相等，這就是為什么輸出結(jié)果依然是 null的原因毫目。

為了解決這個問題蔬啡，我們需要取消 equals方法的注釋。在這個方法里镀虐，我們認(rèn)為只要兩個對象都是 Key類型箱蟆，而且它們的 id相等，它們就相等刮便。

小結(jié)

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

最后再強(qiáng)調(diào)一下：如果大家要在HashMap的 “鍵” 部分存放自定義的對象久信，一定要重寫 equals和 hashCode方法來覆蓋 Object里的同名方法。

注意：Equals 與 hashCode 的定義必須一致：如果 x.equals(y) 返回 true, 那么 x.hashCode( ) 就必須與 y.hashCode( ) 具有相同的值漓摩。 例如裙士， 如果用定義的 User.equals 比較的是User的 ID， 那么 hashCode 方法就需要散列 ID管毙，而不是User的name或address腿椎。