前言：這篇文章寫的越品越有味

首先再次強調hashcode （==）和equals的真正含義（我記得以前有人會說，equals是判斷對象內容，hashcode是判斷是否相等之類）：

equals：是否同一個對象實例。注意，是“實例”。比如String s = new String(“test”);  s.equals(s), 這就是同一個對象實例的比較；

等號(==)：對比對象實例的內存地址（也即對象實例的ID），來判斷是否是同一對象實例；又可以說是判斷對象實例是否物理相等；

Hashcode：我覺得可以這樣理解：并不是對象的內存地址，而是利用hash算法，對對象實例的一種描述符（或者說對象存儲位置的hash算法映射）——對象實例的哈希碼。

為什么需要使用Hashcode，可以從java集合的常用需求來描述：

Java中的集合（Collection）有兩類，一類是List，再有一類是Set。前者集合內的元素是有序的，元素可以重復；后者元素無序，但元素不可重復。那么這里就有一個比較嚴重的問題了：要想保證元素不重復，可兩個元素是否重復應該依據什么來判斷呢？這就是 Object.equals方法了。但是，如果每增加一個元素就檢查一次，那么當元素很多時，后添加到集合中的元素比較的次數就非常多了。也就是說，如果集合中現在已經有1000個元素，那么第1001個元素加入集合時，它就要調用1000次equals方法。這顯然會大大降低效率。  于是，Java采用了哈希表的原理。哈希算法也稱為散列算法，是將數據依特定算法直接指定到一個地址上。可以這樣簡單理解，hashCode方法實際上返回的就是對象存儲位置的映像。   這樣一來，當集合要添加新的元素時，先調用這個元素的hashCode方法，就能定位到它應該放置的存儲位置。如果這個位置上沒有元素，它就可以直接存儲在這個位置上，不用再進行任何比較了；如果這個位置上已經有元素了，就調用它的equals方法與新元素進行比較，相同的話就不存了，不相同就表示發生沖突了，散列表對于沖突有具體的解決辦法，但最終還會將新元素保存在適當的位置。這樣一來，實際調用equals方法的次數就大大降低了，幾乎只需要一兩次。

簡單歸納，hashmap的深入理解：

HashMap的數據結構是基于數組和鏈表的。（以數組存儲元素，如有hash相同的元素，在數組結構中，創建鏈表結構，再把hash相同的元素放到鏈表的下一個節點）

hashMap的結構類似這樣  元素0–>[hashCode=0, key.value=x1的數據]  元素1–>[hashCode=1, key.value=y1的數據]  。。。。。。  元素n–>[hashCode=n, key.value=z1的數據]假設沒有hashCode=1的元素加入，但是有兩個hashCode=0的數據，它的結構就變成這樣  元素0–>[hashCode=0, key.value=x1的數據].next–>[hashCode=0, key.value=x2的數據]  元素1–>[null]  ……  元素n–>[hashCode=n, key.value=z1的數據]

put和get都首先會調用hashcode方法，去查找相關的key，當有沖突時，再調用equals（這也是為什么剛開始就重溫hashcode和equals的原因）！

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

正文（以下來自轉載）

HashMap的工作原理是近年來常見的Java面試題。幾乎每個Java程序員都知道HashMap，都知道哪里要用HashMap，知道Hashtable和HashMap之間的區別，那么為何這道面試題如此特殊呢？是因為這道題考察的深度很深。這題經常出現在高級或中高級面試中。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復雜。讓我們開始探索的旅程吧！

先來些簡單的問題

“你用過HashMap嗎？” “什么是HashMap？你為什么用到它？”

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

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

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

但一些面試者可能可以給出答案，“HashMap是基于hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，我們先對鍵調用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象。”這里關鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象，作為Map.Entry。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點，或者錯誤的認為僅僅只在bucket中存儲值的話，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當的正確，也顯示出面試者確實知道hashing以及HashMap的工作原理。但是這僅僅是故事的開始，當面試官加入一些Java程序員每天要碰到的實際場景的時候，錯誤的答案頻現。下個問題可能是關于HashMap中的碰撞探測(collision detection)以及碰撞的解決方法：

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

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

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

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

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

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

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

熱心的讀者貢獻了更多的關于HashMap的問題：

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

總結

HashMap的工作原理

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

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