我在面試 Java初級開發(fā)的時(shí)候，經(jīng)常會問：你有沒有重寫過hashcode方法道批？不少候選人直接說沒寫過错英。我就想，或許真的沒寫過隆豹，于是就再通過一個(gè)問題確認(rèn)：你在用HashMap的時(shí)候椭岩，鍵（Key）部分，有沒有放過自定義對象？而這個(gè)時(shí)候判哥，候選人說放過氮唯，于是兩個(gè)問題的回答就自相矛盾了。
最近問下來姨伟，這個(gè)問題普遍回答不大好惩琉，于是在本文里，就干脆從hash表講起夺荒，講述HashMap的存數(shù)據(jù)規(guī)則瞒渠，由此大家就自然清楚上述問題的答案了。
1 通過Hash算法來了解HashMap對象的高效性
我們先復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)里的一個(gè)知識點(diǎn)：在一個(gè)長度為n（假設(shè)是10000）的線性表（假設(shè)是LinkedList）里技扼，存放著無序的數(shù)字伍玖；如果我們要找一個(gè)指定的數(shù)字，就不得不通過從頭到尾依次遍歷來查找剿吻，這樣的平均查找次數(shù)是n除以2（這里是5000）窍箍。
我們再來觀察Hash表（這里的Hash表純粹是數(shù)據(jù)結(jié)構(gòu)上的概念，和Java無關(guān)）丽旅。它的平均查找次數(shù)接近于1椰棘，代價(jià)相當(dāng)小，關(guān)鍵是在Hash表里榄笙，存放在其中的數(shù)據(jù)和它的存儲位置是用Hash函數(shù)關(guān)聯(lián)的邪狞。
我們假設(shè)一個(gè)Hash函數(shù)是x*x%5。當(dāng)然實(shí)際情況里不可能用這么簡單的Hash函數(shù)茅撞，我們這里純粹為了說明方便帆卓，而Hash表是一個(gè)長度是11的線性表。如果我們要把6放入其中米丘，那么我們首先會對6用Hash函數(shù)計(jì)算一下剑令，結(jié)果是1，所以我們就把6放入到索引號是1這個(gè)位置拄查。同樣如果我們要放數(shù)字7吁津，經(jīng)過Hash函數(shù)計(jì)算，7的結(jié)果是4靶累，那么它將被放入索引是4的這個(gè)位置腺毫。這個(gè)效果如下圖所示。
這樣做的好處非常明顯挣柬。比如我們要從中找6這個(gè)元素，我們可以先通過Hash函數(shù)計(jì)算6的索引位置睛挚，然后直接從1號索引里找到它了邪蛔。
不過我們會遇到“Hash值沖突”這個(gè)問題。比如經(jīng)過Hash函數(shù)計(jì)算后扎狱，7和8會有相同的Hash值侧到，對此Java的HashMap對象采用的是”鏈地址法“的解決方案勃教。效果如下圖所示。
具體的做法是匠抗，為所有Hash值是i的對象建立一個(gè)同義詞鏈表故源。假設(shè)我們在放入8的時(shí)候，發(fā)現(xiàn)4號位置已經(jīng)被占汞贸，那么就會新建一個(gè)鏈表結(jié)點(diǎn)放入8绳军。同樣，如果我們要找8矢腻，那么發(fā)現(xiàn)4號索引里不是8门驾，那會沿著鏈表依次查找。
雖然我們還是無法徹底避免Hash值沖突的問題多柑，但是Hash函數(shù)設(shè)計(jì)合理奶是，仍能保證同義詞鏈表的長度被控制在一個(gè)合理的范圍里。這里講的理論知識并非無的放矢竣灌，大家能在后文里清晰地了解到重寫hashCode方法的重要性聂沙。
2 為什么要重寫equals和hashCode方法
當(dāng)我們用HashMap存入自定義的類時(shí)，如果不重寫這個(gè)自定義類的equals和hashCode方法初嘹，得到的結(jié)果會和我們預(yù)期的不一樣逐纬。我們來看WithoutHashCode.java這個(gè)例子。
在其中的第2到第18行削樊，我們定義了一個(gè)Key類豁生；在其中的第3行定義了唯一的一個(gè)屬性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 // else
13 // { 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<Key,String> hm = new HashMap<Key,String>();
25 hm.put(k1, "Key with id is 1");
26 System.out.println(hm.get(k2));
27 }
28 }
在main函數(shù)里的第22和23行甸箱，我們定義了兩個(gè)Key對象，它們的id都是1迅脐，就好比它們是兩把相同的都能打開同一扇門的鑰匙芍殖。
在第24行里，我們通過泛型創(chuàng)建了一個(gè)HashMap對象谴蔑。它的鍵部分可以存放Key類型的對象豌骏，值部分可以存儲String類型的對象。
在第25行里隐锭，我們通過put方法把k1和一串字符放入到hm里窃躲； 而在第26行，我們想用k2去從HashMap里得到值钦睡；這就好比我們想用k1這把鑰匙來鎖門蒂窒，用k2來開門。這是符合邏輯的，但從當(dāng)前結(jié)果看洒琢，26行的返回結(jié)果不是我們想象中的那個(gè)字符串秧秉，而是null。
原因有兩個(gè)衰抑。第一是沒有重寫hashCode方法象迎，第二是沒有重寫equals方法。
當(dāng)我們往HashMap里放k1時(shí)呛踊，首先會調(diào)用Key這個(gè)類的hashCode方法計(jì)算它的hash值砾淌，隨后把k1放入hash值所指引的內(nèi)存位置。
關(guān)鍵是我們沒有在Key里定義hashCode方法恋技。這里調(diào)用的仍是Object類的hashCode方法（所有的類都是Object的子類）拇舀，而Object類的hashCode方法返回的hash值其實(shí)是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方法（因?yàn)镵ey里沒定義）計(jì)算k2的hash值時(shí)，其實(shí)得到的是k2的內(nèi)存地址（假設(shè)是2000）站楚。由于k1和k2是兩個(gè)不同的對象脱惰，所以它們的內(nèi)存地址一定不會相同，也就是說它們的hash值一定不同窿春，這就是我們無法用k2的hash值去拿k1的原因拉一。
當(dāng)我們把第16和17行的hashCode方法的注釋去掉后，會發(fā)現(xiàn)它是返回id屬性的hashCode值旧乞，這里k1和k2的id都是1,所以它們的hash值是相等的蔚润。
我們再來更正一下存k1和取k2的動作。存k1時(shí)尺栖，是根據(jù)它id的hash值嫡纠，假設(shè)這里是100，把k1對象放入到對應(yīng)的位置延赌。而取k2時(shí)除盏，是先計(jì)算它的hash值（由于k2的id也是1，這個(gè)值也是100）挫以，隨后到這個(gè)位置去找者蠕。
但結(jié)果會出乎我們意料：明明100號位置已經(jīng)有k1，但第26行的輸出結(jié)果依然是null屡贺。其原因就是沒有重寫Key對象的equals方法蠢棱。
HashMap是用鏈地址法來處理沖突锌杀，也就是說甩栈，在100號位置上泻仙，有可能存在著多個(gè)用鏈表形式存儲的對象。它們通過hashCode方法返回的hash值都是100量没。
當(dāng)我們通過k2的hashCode到100號位置查找時(shí)玉转，確實(shí)會得到k1。但k1有可能僅僅是和k2具有相同的hash值殴蹄，但未必和k2相等（k1和k2兩把鑰匙未必能開同一扇門）究抓，這個(gè)時(shí)候，就需要調(diào)用Key對象的equals方法來判斷兩者是否相等了袭灯。
由于我們在Key對象里沒有定義equals方法刺下，系統(tǒng)就不得不調(diào)用Object類的equals方法。由于Object的固有方法是根據(jù)兩個(gè)對象的內(nèi)存地址來判斷稽荧，所以k1和k2一定不會相等橘茉，這就是為什么依然在26行通過hm.get(k2)依然得到null的原因。
為了解決這個(gè)問題姨丈，我們需要打開第9到14行equals方法的注釋畅卓。在這個(gè)方法里，只要兩個(gè)對象都是Key類型蟋恬，而且它們的id相等翁潘，它們就相等。
3 對面試問題的說明
由于在項(xiàng)目里經(jīng)常會用到HashMap歼争，所以我在面試的時(shí)候一定會問這個(gè)問題∶你有沒有重寫過hashCode方法拜马？你在使用HashMap時(shí)有沒有重寫hashCode和equals方法？你是怎么寫的沐绒？
根據(jù)問下來的結(jié)果俩莽，我發(fā)現(xiàn)初級程序員對這個(gè)知識點(diǎn)普遍沒掌握好。重申一下洒沦，如果大家要在HashMap的“鍵”部分存放自定義的對象豹绪，一定要在這個(gè)對象里用自己的equals和hashCode方法來覆蓋Object里的同名方法。
本文是從Java核心技術(shù)及面試指南這本書中相關(guān)內(nèi)容改編而來申眼。
原文可見：為什么要重寫hashcode和equals方法瞒津？初級程序員在面試中很少能說清楚。
備注：在Java 8 之前括尸，HashMap和其他基于map的類都是通過鏈地址法解決沖突巷蚪，它們使用單向鏈表來存儲相同索引值的元素。在最壞的情況下濒翻，這種方式會將HashMap的get方法的性能從O(1)降低到O(n)屁柏。為了解決在頻繁沖突時(shí)hashmap性能降低的問題啦膜，Java 8中使用平衡樹來替代鏈表存儲沖突的元素。這意味著我們可以將最壞情況下的性能從O(n)提高到O(logn)淌喻。
在Java 8中使用常量TREEIFY_THRESHOLD來控制是否切換到平衡樹來存儲僧家。目前，這個(gè)常量值是8裸删，這意味著當(dāng)有超過8個(gè)元素的索引一樣時(shí)八拱，HashMap會使用樹來存儲它們。
這一改變是為了繼續(xù)優(yōu)化常用類涯塔。大家可能還記得在Java 7中為了優(yōu)化常用類對ArrayList和HashMap采用了延遲加載的機(jī)制肌稻，在有元素加入之前不會分配內(nèi)存，這會減少空的鏈表和HashMap占用的內(nèi)存匕荸。
這一動態(tài)的特性使得HashMap一開始使用鏈表爹谭，并在沖突的元素?cái)?shù)量超過指定值時(shí)用平衡二叉樹替換鏈表。不過這一特性在所有基于hash table的類中并沒有榛搔，例如Hashtable和WeakHashMap诺凡。
目前，只有ConcurrentHashMap,LinkedHashMap和HashMap會在頻繁沖突的情況下使用平衡樹药薯。
詳情可見：[譯]Java 8中HashMap和LinkedHashMap如何解決沖突
關(guān)于Java 8中HashMap的解析可以參考：
Java8的HashMap詳解（存儲結(jié)構(gòu)绑洛，功能實(shí)現(xiàn)，擴(kuò)容優(yōu)化童本，線程安全真屯，遍歷方法）
Java 8系列之重新認(rèn)識HashMap
感謝@皮特天的指正
