HashMap的(de)工作原理是(shi)近年(nian)來常見的(de)Java面試題。幾乎每個Java程序員都知道(dao)HashMap，都知道(dao)哪里要用HashMap，知道(dao)，那么為(wei)(wei)何這(zhe)道(dao)面試題如此特殊呢？是(shi)因為(wei)(wei)這(zhe)道(dao)題考察的(de)深度很(hen)深。這(zhe)題經(jing)常出現(xian)在高級或中(zhong)高級面試中(zhong)，甚至會要求你(ni)實現(xian)HashMap來考察你(ni)的(de)編(bian)程能力。ConcurrentHashMap和其它同步集合(he)的(de)引入讓這(zhe)道(dao)題變(bian)得更加復雜(za)。讓我們開始探索的(de)旅程吧！

先來(lai)些簡單的問題

“你(ni)用過HashMap嗎(ma)？” ;“什么是HashMap？你(ni)為什么用到(dao)它？”

幾(ji)乎(hu)每個(ge)人都會回答(da)“是(shi)的(de)”，然后回答(da)HashMap的(de)一些特性，譬如HashMap可(ke)以(yi)(yi)接受(shou)null鍵值和值，而Hashtable則不能；HashMap是(shi)非synchronized;HashMap很(hen)快(kuai)；以(yi)(yi)及HashMap儲存的(de)是(shi)鍵值對等(deng)等(deng)。這顯示(shi)出你(ni)已經用過HashMap，而且對它相(xiang)當的(de)熟悉。但是(shi)面試(shi)官來(lai)個(ge)急轉直下，從此(ci)刻開始(shi)問(wen)出一些刁鉆的(de)問(wen)題，關于HashMap的(de)更多(duo)基礎的(de)細(xi)節(jie)。面試(shi)官可(ke)能會問(wen)出下面的(de)問(wen)題：

“你(ni)知(zhi)道HashMap的工作原理嗎？” “你(ni)知(zhi)道HashMap的get()方(fang)法的工作原理嗎？”

你也許會回答“我沒(mei)有詳查標準的Java API，你可以看看Java源代碼或(huo)者Open JDK。”“我可以用Google找(zhao)到答案。”

但(dan)一(yi)(yi)些(xie)面試者可(ke)(ke)能(neng)可(ke)(ke)以(yi)給出答(da)案(an)，“HashMap是(shi)基于(yu)hashing的(de)(de)原(yuan)理(li)，我(wo)們(men)使用put(key, value)存(cun)儲對(dui)(dui)(dui)象(xiang)(xiang)到(dao)HashMap中，使用get(key)從HashMap中獲取對(dui)(dui)(dui)象(xiang)(xiang)。當(dang)我(wo)們(men)給put()方(fang)(fang)法傳遞(di)鍵和(he)值時，我(wo)們(men)先(xian)對(dui)(dui)(dui)鍵調用hashCode()方(fang)(fang)法，返回的(de)(de)hashCode用于(yu)找(zhao)到(dao)bucket位置(zhi)來(lai)儲存(cun)Entry對(dui)(dui)(dui)象(xiang)(xiang)。”這(zhe)里關(guan)鍵點在于(yu)指出，HashMap是(shi)在bucket中儲存(cun)鍵對(dui)(dui)(dui)象(xiang)(xiang)和(he)值對(dui)(dui)(dui)象(xiang)(xiang)，作為Map.Entry。這(zhe)一(yi)(yi)點有(you)助(zhu)于(yu)理(li)解(jie)(jie)獲取對(dui)(dui)(dui)象(xiang)(xiang)的(de)(de)邏(luo)輯。如果你(ni)沒有(you)意識到(dao)這(zhe)一(yi)(yi)點，或(huo)者錯(cuo)誤的(de)(de)認為僅僅只在bucket中存(cun)儲值的(de)(de)話，你(ni)將(jiang)不會回答(da)如何從HashMap中獲取對(dui)(dui)(dui)象(xiang)(xiang)的(de)(de)邏(luo)輯。這(zhe)個答(da)案(an)相(xiang)當(dang)的(de)(de)正(zheng)確，也顯示(shi)出面試者確實(shi)知道hashing以(yi)及(ji)HashMap的(de)(de)工作原(yuan)理(li)。但(dan)是(shi)這(zhe)僅僅是(shi)故(gu)事的(de)(de)開始(shi)，當(dang)面試官加入一(yi)(yi)些(xie)Java程(cheng)序員每天要碰(peng)到(dao)的(de)(de)實(shi)際場景的(de)(de)時候，錯(cuo)誤的(de)(de)答(da)案(an)頻現。下個問題可(ke)(ke)能(neng)是(shi)關(guan)于(yu)HashMap中的(de)(de)碰(peng)撞探測(collision detection)以(yi)及(ji)碰(peng)撞的(de)(de)解(jie)(jie)決方(fang)(fang)法：

“當兩個對象的hashcode相同會發生什么？” 從這里開始，真正的困惑開始了，一些面試者會回答因為hashcode相同，所以兩個對象是相等的，HashMap將會拋出異常，或者不會存儲它們。然后面試官可能會提醒他們有equals()和hashCode()兩個方法，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續挺進，他們回答“因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。”這個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結，面試官會繼續問：

“如果兩個鍵的hashcode相同，你如何獲取值對象？” 面試者會回答：當我們調用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。

其中一些記得這個重要知(zhi)識點的(de)面試者會說，找(zhao)到(dao)bucket位置之后，會調(diao)用(yong)keys.equals()方法去找(zhao)到(dao)鏈表(biao)中正確的(de)節(jie)點，最終找(zhao)到(dao)要找(zhao)的(de)值(zhi)對象。完美的(de)答案！

許多情況下(xia)，面試者(zhe)會(hui)在這個環節(jie)中出(chu)錯，因(yin)為他們混淆了hashCode()和equals()方法。因(yin)為在此之前hashCode()屢屢出(chu)現(xian)(xian)，而equals()方法僅僅在獲(huo)(huo)取(qu)值對(dui)象的(de)(de)時候才出(chu)現(xian)(xian)。一些優秀的(de)(de)開發(fa)者(zhe)會(hui)指出(chu)使(shi)用不(bu)可變(bian)的(de)(de)、聲明作final的(de)(de)對(dui)象，并(bing)且采用合適的(de)(de)equals()和hashCode()方法的(de)(de)話(hua)，將會(hui)減少碰撞的(de)(de)發(fa)生(sheng)，提(ti)高(gao)(gao)效率。不(bu)可變(bian)性使(shi)得能(neng)夠緩存不(bu)同鍵的(de)(de)hashcode，這將提(ti)高(gao)(gao)整個獲(huo)(huo)取(qu)對(dui)象的(de)(de)速度，使(shi)用String，Interger這樣的(de)(de)wrapper類作為鍵是非常好的(de)(de)選擇。

如果你認為到這里已經完結了，那么聽到下面這個問題的時候，你會大吃一驚。“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，并將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。

如果你能夠回答這道問題，下面的問題來了：“你了解重新調整HashMap大小存在什么問題嗎？”你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產生條件競爭(race condition)。

當重新(xin)調(diao)整HashMap大(da)小(xiao)(xiao)(xiao)的時候(hou)，確實(shi)存在條(tiao)件競爭(zheng)，因為如果兩個(ge)線程(cheng)都發現HashMap需(xu)要重新(xin)調(diao)整大(da)小(xiao)(xiao)(xiao)了(le)，它們會(hui)同時試著調(diao)整大(da)小(xiao)(xiao)(xiao)。在調(diao)整大(da)小(xiao)(xiao)(xiao)的過程(cheng)中(zhong)，存儲在鏈(lian)表中(zhong)的元(yuan)素的次序(xu)會(hui)反過來，因為移動到(dao)新(xin)的bucket位(wei)置(zhi)的時候(hou)，HashMap并不會(hui)將元(yuan)素放(fang)在鏈(lian)表的尾(wei)部，而(er)是放(fang)在頭部，這是為了(le)避免尾(wei)部遍歷(tail traversing)。如果條(tiao)件競爭(zheng)發生了(le)，那么就(jiu)死(si)循環了(le)。這個(ge)時候(hou)，你(ni)可以質問面試官，為什么這么奇怪，要在多線程(cheng)的環境下使用HashMap呢(ni)？：）

熱心(xin)的(de)讀者貢獻了更(geng)多的(de)關于(yu)HashMap的(de)問題：

為什么String, Interger這樣的wrapper類適合作為鍵？ String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。

我們可以使用自定義的對象作為鍵嗎？ 這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。

我們可以使用CocurrentHashMap來代替Hashtable嗎？這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。看看查看Hashtable和ConcurrentHashMap的區別。

我個人(ren)很喜歡這個問題，因為這個問題的深度(du)和廣(guang)度(du)，也不直(zhi)接的涉及到不同的概念。讓我們再來看(kan)看(kan)這些問題設計哪些知識點(dian)：

hashing的概念(nian)

HashMap中解決(jue)碰撞(zhuang)的方法

equals()和hashCode()的(de)(de)應用(yong)，以及它(ta)們在HashMap中的(de)(de)重要(yao)性

不可變對象的好處

HashMap多(duo)線程(cheng)的條件競爭

重(zhong)新調(diao)整HashMap的大小

總(zong)結(jie)

HashMap的工(gong)作原(yuan)理

HashMap基于(yu)hashing原理，我們通過put()和(he)get()方(fang)法儲(chu)存(cun)(cun)和(he)獲取對(dui)象。當我們將鍵(jian)(jian)值對(dui)傳遞給put()方(fang)法時，它調用(yong)鍵(jian)(jian)對(dui)象的hashCode()方(fang)法來(lai)計(ji)算(suan)hashcode，讓后(hou)找到bucket位(wei)置來(lai)儲(chu)存(cun)(cun)值對(dui)象。當獲取對(dui)象時，通過鍵(jian)(jian)對(dui)象的equals()方(fang)法找到正確的鍵(jian)(jian)值對(dui)，然后(hou)返回值對(dui)象。HashMap使用(yong)鏈表來(lai)解(jie)決碰(peng)(peng)撞(zhuang)問題，當發生碰(peng)(peng)撞(zhuang)了(le)，對(dui)象將會儲(chu)存(cun)(cun)在鏈表的下一個節點(dian)中(zhong)。 HashMap在每個鏈表節點(dian)中(zhong)儲(chu)存(cun)(cun)鍵(jian)(jian)值對(dui)對(dui)象。

當兩個不同(tong)的鍵對(dui)(dui)象的hashcode相(xiang)同(tong)時會發生什么？ 它(ta)們會儲存在同(tong)一(yi)個bucket位置的鏈表中。鍵對(dui)(dui)象的equals()方(fang)法用(yong)來找到鍵值對(dui)(dui)。

。