從下圖我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的，一個長度為16的數(shù)組中，每個元素存儲的是一個鏈表的頭結(jié)點。那么這些元素是按照什么樣的規(guī)則存儲到數(shù)組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數(shù)組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數(shù)組下標為12的位置。

HashMap其實也是一個線性的數(shù)組實現(xiàn)的,所以可以理解為其存儲數(shù)據(jù)的容器就是一個線性數(shù)組。這可能讓我們很不解，一個線性的數(shù)組怎么實現(xiàn)按鍵值對來存取數(shù)據(jù)呢？這里HashMap有做一些處理。

首先HashMap里面實現(xiàn)一個靜態(tài)內(nèi)部類Entry，其重要的屬性有 key , value, next，從屬性key,value我們就能很明顯的看出來Entry就是HashMap鍵值對實現(xiàn)的一個基礎bean，我們上面說到HashMap的基礎就是一個線性數(shù)組，這個數(shù)組就是Entry[]，Map里面的內(nèi)容都保存在Entry[]里面。

WX20171011-230950.png

疑問：如果兩個key通過hash%Entry[].length得到的index相同，會不會有覆蓋的危險？
　　這里HashMap里面用到鏈式數(shù)據(jù)結(jié)構(gòu)的一個概念。上面我們提到過Entry類里面有一個next屬性，作用是指向下一個Entry。打個比方， 第一個鍵值對A進來，通過計算其key的hash得到的index=0，記做:Entry[0] = A。一會后又進來一個鍵值對B，通過計算其index也等于0，現(xiàn)在怎么辦？HashMap會這樣做:B.next = A,Entry[0] = B,如果又進來C,index也等于0,那么C.next = B,Entry[0] = C；這樣我們發(fā)現(xiàn)index=0的地方其實存取了A,B,C三個鍵值對,他們通過next這個屬性鏈接在一起。所以疑問不用擔心。也就是說數(shù)組中存儲的是最后插入的元素。到這里為止，HashMap的大致實現(xiàn)，我們應該已經(jīng)清楚了。

Java中hashmap的解決辦法就是采用的鏈地址法。

“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”
幾乎每個人都會回答“是的”，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值，而Hashtable則不能；HashMap是非synchronized;HashMap很快；以及HashMap儲存的是鍵值對等等。這顯示出你已經(jīng)用過HashMap，而且對它相當?shù)氖煜ぁ?br> “你知道HashMap的工作原理嗎？” “你知道HashMap的get()方法的工作原理嗎？”
“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象?！边@里關鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當?shù)恼_，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始，當面試官加入一些Java程序員每天要碰到的實際場景的時候，錯誤的答案頻現(xiàn)。下個問題可能是關于HashMap中的碰撞探測(collision detection)以及碰撞的解決方法：
“當兩個對象的hashcode相同會發(fā)生什么？” 從這里開始，真正的困惑開始了，一些面試者會回答因為hashcode相同，所以兩個對象是相等的，HashMap將會拋出異常，或者不會存儲它們。然后面試官可能會提醒他們有equals()和hashCode()兩個方法，并告訴他們兩個對象就算hashcode相同，但是它們可能并不相等。一些面試者可能就此放棄，而另外一些還能繼續(xù)挺進，他們回答“因為hashcode相同，所以它們的bucket位置相同，‘碰撞’會發(fā)生。因為HashMap使用鏈表存儲對象，這個Entry(包含有鍵值對的Map.Entry對象)會存儲在鏈表中。”這個答案非常的合理，雖然有很多種處理碰撞的方法，這種方法是最簡單的，也正是HashMap的處理方法。但故事還沒有完結(jié)，面試官會繼續(xù)問：
“如果兩個鍵的hashcode相同，你如何獲取值對象？” 面試者會回答：當我們調(diào)用get()方法，HashMap會使用鍵對象的hashcode找到bucket位置，然后獲取值對象。面試官提醒他如果有兩個值對象儲存在同一個bucket，他給出答案:將會遍歷鏈表直到找到值對象。面試官會問因為你并沒有值對象去比較，你是如何確定確定找到值對象的？除非面試者直到HashMap在鏈表中存儲的是鍵值對，否則他們不可能回答出這一題。
其中一些記得這個重要知識點的面試者會說，找到bucket位置之后，會調(diào)用keys.equals()方法去找到鏈表中正確的節(jié)點，最終找到要找的值對象。完美的答案！
許多情況下，面試者會在這個環(huán)節(jié)中出錯，因為他們混淆了hashCode()和equals()方法。因為在此之前hashCode()屢屢出現(xiàn)，而equals()方法僅僅在獲取值對象的時候才出現(xiàn)。一些優(yōu)秀的開發(fā)者會指出使用不可變的、聲明作final的對象，并且采用合適的equals()和hashCode()方法的話，將會減少碰撞的發(fā)生，提高效率。不可變性使得能夠緩存不同鍵的hashcode，這將提高整個獲取對象的速度，使用String，Interger這樣的wrapper類作為鍵是非常好的選擇。
如果你認為到這里已經(jīng)完結(jié)了，那么聽到下面這個問題的時候，你會大吃一驚。“如果HashMap的大小超過了負載因子(load factor)定義的容量，怎么辦？”除非你真正知道HashMap的工作原理，否則你將回答不出這道題。默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創(chuàng)建原來HashMap大小的兩倍的bucket數(shù)組，來重新調(diào)整map的大小，并將原來的對象放入新的bucket數(shù)組中。這個過程叫作rehashing，因為它調(diào)用hash方法找到新的bucket位置。
如果你能夠回答這道問題，下面的問題來了：“你了解重新調(diào)整HashMap大小存在什么問題嗎？”你可能回答不上來，這時面試官會提醒你當多線程的情況下，可能產(chǎn)生條件競爭(race condition)。
當重新調(diào)整HashMap大小的時候，確實存在條件競爭，因為如果兩個線程都發(fā)現(xiàn)HashMap需要重新調(diào)整大小了，它們會同時試著調(diào)整大小。在調(diào)整大小的過程中，存儲在鏈表中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap并不會將元素放在鏈表的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發(fā)生了，那么就死循環(huán)了。這個時候，你可以質(zhì)問面試官，為什么這么奇怪，要在多線程的環(huán)境下使用HashMap呢？：）
熱心的讀者貢獻了更多的關于HashMap的問題：
為什么String, Interger這樣的wrapper類適合作為鍵？ String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經(jīng)重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。
我們可以使用自定義的對象作為鍵嗎？ 這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規(guī)則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經(jīng)滿足了作為鍵的條件，因為當它創(chuàng)建之后就已經(jīng)不能改變了。
我們可以使用CocurrentHashMap來代替Hashtable嗎？這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據(jù)同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性?？纯?a target="_blank" rel="nofollow">這篇博客查看Hashtable和ConcurrentHashMap的區(qū)別。

我個人很喜歡這個問題，因為這個問題的深度和廣度，也不直接的涉及到不同的概念。讓我們再來看看這些問題設計哪些知識點：
hashing的概念
HashMap中解決碰撞的方法
equals()和hashCode()的應用，以及它們在HashMap中的重要性
不可變對象的好處
HashMap多線程的條件競爭
重新調(diào)整HashMap的大小

總結(jié)
HashMap的工作原理
HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調(diào)用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。
當兩個不同的鍵對象的hashcode相同時會發(fā)生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。