原文鏈接： 存檔鏈接： --- HashMap 和 Hashtable 的比較是 Java 面試中的常見問題，用來考驗程序員是否能夠正確使用集合類以及是否可以隨機應變使用多種思路解決問題。HashMap 的工作原理、ArrayList 與 Vector 的比較以及這個問題是有關 Java 集合框架的最經典的問題。Hashtable 是個過時的集合類，存在于 Java API 中很久了。在 Java 4 中被重寫了，實現了 Map 接口，所以自此以后也成了 Java 集合框架中的一部分。Hashtable 和 HashMap 在 Java 面試中相當容易被問到，甚至成為了集合框架面試題中最常被考的問題，所以在參加任何 Java 面試之前，都不要忘了準備這一題。 這篇文章中，我們不僅將會看到 HashMap 和 Hashtable 的區別，還將看到它們之間的相似之處。 ### HashMap 和 Hashtable 的區別 HashMap 和 Hashtable 都實現了 Map 接口，但決定用哪一個之前先要弄清楚它們之間的分別。主要的區別有：線程安全性，同步 (synchronization)，以及速度。 1. HashMap 幾乎可以等價于 Hashtable，除了 HashMap 是非 synchronized 的，并可以接受 null(HashMap 可以接受為 null 的鍵值 (key) 和值 (value)，而 Hashtable 則不行)。 2. HashMap 是非 synchronized，而 Hashtable 是 synchronized，這意味著 Hashtable 是線程安全的，多個線程可以共享一個 Hashtable；而如果沒有正確的同步的話，多個線程是不能共享 HashMap 的。Java 5 提供了 ConcurrentHashMap，它是 HashTable 的替代，比 HashTable 的擴展性更好。 3. 另一個區別是 HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的。所以當有其它線程改變了 HashMap 的結構（增加或者移除元素），將會拋出ConcurrentModificationException，但迭代器本身的 remove() 方法移除元素則不會拋出ConcurrentModificationException 異常。但這并不是一個一定發生的行為，要看 JVM。這條同樣也是Enumeration 和 Iterato r的區別。 4. 由于 Hashtable 是線程安全的也是 synchronized，所以在單線程環境下它比 HashMap 要慢。如果你不需要同步，只需要單一線程，那么使用 HashMap 性能要好過 Hashtable。 5. HashMap 不能保證隨著時間的推移 Map 中的元素次序是不變的。 ### 要注意的一些重要術語： 1) sychronized 意味著在一次僅有一個線程能夠更改 Hashtable。就是說任何線程要更新 Hashtable 時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新 Hashtable。 2) Fail-safe 和 iterator 迭代器相關。如果某個集合對象創建了 Iterator 或者 ListIterator，然后其它的線程試圖“結構上”更改集合對象，將會拋出 ConcurrentModificationException 異常。但其它線程可以通過 set() 方法更改集合對象是允許的，因為這并沒有從“結構上”更改集合。但是假如已經從結構上進行了更改，再調用 set() 方法，將會拋出 IllegalArgumentException 異常。 3) 結構上的更改指的是刪除或者插入一個元素，這樣會影響到 map 的結構。 ### 我們能否讓 HashMap 同步？ HashMap 可以通過下面的語句進行同步： Map m = Collections.synchronizeMap(hashMap); ### 結論 Hashtable 和 HashMap 有幾個主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用 Java 5 或以上的話，請使用 ConcurrentHashMap 吧。 轉載自：[HashMap和Hashtable的區別](https://link.juejin.im?target=http%3A%2F%2Fwww.importnew.com%2F7010.html) * * * 關于 HashMap 線程不安全這一點，《Java并發編程的藝術》一書中是這樣說的： > HashMap 在并發執行 put 操作時會引起死循環，導致 CPU 利用率接近 100%。因為多線程會導致 HashMap 的 Node 鏈表形成環形數據結構，一旦形成環形數據結構，Node 的 next 節點永遠不為空，就會在獲取 Node 時產生死循環。 原因： * [疫苗：JAVA HASHMAP的死循環 —— 酷殼](https://link.juejin.im?target=http%3A%2F%2Fcoolshell.cn%2Farticles%2F9606.html) * [HashMap在java并發中如何發生死循環](https://link.juejin.im?target=http%3A%2F%2Ffirezhfox.iteye.com%2Fblog%2F2241043) * [How does a HashMap work in JAVA](https://link.juejin.im?target=http%3A%2F%2Fcoding-geek.com%2Fhow-does-a-hashmap-work-in-java%2F) * * * 下面的是自己有道云筆記中記錄的： **HashMap ， HashTable 和 HashSet 區別** 1. 關于 HashMap 的一些說法： a) HashMap 實際上是一個“鏈表散列”的數據結構，即數組和鏈表的結合體。HashMap 的底層結構是一個數組，數組中的每一項是一條鏈表。 b) HashMap 的實例有倆個參數影響其性能： “初始容量” 和 裝填因子。 c) HashMap 實現不同步，線程不安全。 HashTable 線程安全 d) HashMap 中的 key-value 都是存儲在 Entry 中的。 e) HashMap 可以存 null 鍵和 null 值，不保證元素的順序恒久不變，它的底層使用的是數組和鏈表，通過hashCode() 方法和 equals 方法保證鍵的唯一性 f) 解決沖突主要有三種方法：定址法，拉鏈法，再散列法。HashMap 是采用拉鏈法解決哈希沖突的。 注： 鏈表法是將相同 hash 值的對象組成一個鏈表放在 hash 值對應的槽位； 用開放定址法解決沖突的做法是：當沖突發生時，使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。 沿此序列逐個單元地查找，直到找到給定 的關鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址，則可將待插入的新結點存人該地址單元）。 拉鏈法解決沖突的做法是： 將所有關鍵字為同義詞的結點鏈接在同一個單鏈表中 。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數 組T[0..m-1]。凡是散列地址為i的結點，均插入到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。在拉鏈法中，裝填因子α可以大于1，但一般均取α≤1。拉鏈法適合未規定元素的大小。 1. Hashtable 和 HashMap 的區別： a) 繼承不同。 public class Hashtable extends Dictionary implements Map public class HashMap extends AbstractMap implements Map b) Hashtable 中的方法是同步的，而 HashMap 中的方法在缺省情況下是非同步的。在多線程并發的環境下，可以直接使用 Hashtable，但是要使用 HashMap 的話就要自己增加同步處理了。 c) Hashtable 中， key 和 value 都不允許出現 null 值。 在 HashMap 中， null 可以作為鍵，這樣的鍵只有一個；可以有一個或多個鍵所對應的值為 null 。當 get() 方法返回 null 值時，即可以表示 HashMap 中沒有該鍵，也可以表示該鍵所對應的值為 null 。因此，在 HashMap 中不能由 get() 方法來判斷 HashMap 中是否存在某個鍵， 而應該用 containsKey() 方法來判斷。 d) 兩個遍歷方式的內部實現上不同。Hashtable、HashMap 都使用了Iterator。而由于歷史原因，Hashtable還使用了 Enumeration 的方式 。 e) 哈希值的使用不同，HashTable 直接使用對象的 hashCode。而 HashMap 重新計算 hash 值。 f) Hashtable 和 HashMap 它們兩個內部實現方式的數組的初始大小和擴容的方式。HashTable 中 hash 數組默認大小是11，增加的方式是 old*2+1。HashMap 中 hash 數組的默認大小是 16，而且一定是2的指數。 注： HashSet 子類依靠 hashCode() 和 equal() 方法來區分重復元素。 HashSet 內部使用 Map 保存數據，即將 HashSet 的數據作為 Map 的 key 值保存，這也是 HashSet 中元素不能重復的原因。而 Map 中保存 key 值的,會去判斷當前 Map 中是否含有該 Key 對象，內部是先通過 key 的hashCode, 確定有相同的 hashCode 之后，再通過 equals 方法判斷是否相同。 * * * 《HashMap 的工作原理》 HashMap的工作原理是近年來常見的Java面試題。幾乎每個Java程序員都知道HashMap，都知道哪里要用HashMap，知道 Hashtable和HashMap之間的區別，那么為何這道面試題如此特殊呢？是因為這道題考察的深度很深。這題經常出現在高級或中高級面試中。投資銀行更喜歡問這個問題，甚至會要求你實現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的問題： 1. **為什么String, Interger這樣的wrapper類適合作為鍵？** String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了，而且String最為常用。因為String是不可變的，也是final的，而且已經重寫了equals()和hashCode()方法了。其他的wrapper類也有這個特點。不可變性是必要的，因為為了要計算hashCode()，就要防止鍵值改變，如果鍵值在放入時和獲取時返回不同的hashcode的話，那么就不能從HashMap中找到你想要的對象。不可變性還有其他的優點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的，那么請這么做吧。因為獲取對象的時候要用到equals()和hashCode()方法，那么鍵對象正確的重寫這兩個方法是非常重要的。如果兩個不相等的對象返回不同的hashcode的話，那么碰撞的幾率就會小些，這樣就能提高HashMap的性能。 2. **我們可以使用自定義的對象作為鍵嗎？** 這是前一個問題的延伸。當然你可能使用任何對象作為鍵，只要它遵守了equals()和hashCode()方法的定義規則，并且當對象插入到Map中之后將不會再改變了。如果這個自定義對象時不可變的，那么它已經滿足了作為鍵的條件，因為當它創建之后就已經不能改變了。 3. **我們可以使用CocurrentHashMap來代替Hashtable嗎？** 這是另外一個很熱門的面試題，因為ConcurrentHashMap越來越多人用了。我們知道Hashtable是synchronized的，但是ConcurrentHashMap同步性能更好，因為它僅僅根據同步級別對map的一部分進行上鎖。ConcurrentHashMap當然可以代替HashTable，但是HashTable提供更強的線程安全性。看看 [這篇博客](https://link.juejin.im?target=http%3A%2F%2Fjavarevisited.blogspot.sg%2F2011%2F04%2Fdifference-between-concurrenthashmap.html) 查看Hashtable和ConcurrentHashMap的區別。 我個人很喜歡這個問題，因為這個問題的深度和廣度，也不直接的涉及到不同的概念。讓我們再來看看這些問題設計哪些知識點： * hashing的概念 * HashMap中解決碰撞的方法 * equals()和hashCode()的應用，以及它們在HashMap中的重要性 * 不可變對象的好處 * HashMap多線程的條件競爭 * 重新調整HashMap的大小 ### 總結 #### HashMap的工作原理 HashMap基于hashing原理，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時，它調用鍵對象的hashCode()方法來計算hashcode，讓后找到bucket位置來儲存值對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然后返回值對象。HashMap使用鏈表來解決碰撞問題，當發生碰撞了，對象將會儲存在鏈表的下一個節點中。 HashMap在每個鏈表節點中儲存鍵值對對象。 當兩個不同的鍵對象的hashcode相同時會發生什么？ 它們會儲存在同一個bucket位置的鏈表中。鍵對象的equals()方法用來找到鍵值對。 因為HashMap的好處非常多，我曾經在電子商務的應用中使用HashMap作為緩存。因為金融領域非常多的運用Java，也出于性能的考慮，我們會經常用到HashMap和ConcurrentHashMap。你可以查看更多的關于HashMap的文章: * [HashMap和Hashtable的區別](https://link.juejin.im?target=http%3A%2F%2Fwww.importnew.com%2F7010.html) * [HashMap和HashSet的區別](https://link.juejin.im?target=http%3A%2F%2Fwww.importnew.com%2F6931.html) 轉載自：[HashMap的工作原理](https://link.juejin.im?target=http%3A%2F%2Fwww.importnew.com%2F7099.html) * * * 其他的 HashMap 學習資料： * [jdk7中HashMap知識點整理](https://link.juejin.im?target=https%3A%2F%2Fsegmentfault.com%2Fa%2F1190000003617333) * [HashMap源碼分析（四）put-jdk8-紅黑樹的引入](https://link.juejin.im?target=http%3A%2F%2Fblog.csdn.net%2Fq291611265%2Farticle%2Fdetails%2F46797557) * [JDK7與JDK8中HashMap的實現](https://link.juejin.im?target=https%3A%2F%2Fmy.oschina.net%2Fhosee%2Fblog%2F618953) * [JDK1.8HashMap原理和源碼分析(java面試收藏)](https://link.juejin.im?target=https%3A%2F%2Fwenku.baidu.com%2Fview%2F6e1035943968011ca30091cd.html) * [談談ConcurrentHashMap1.7和1.8的不同實現](https://link.juejin.im?target=http%3A%2F%2Fwww.jianshu.com%2Fp%2Fe694f1e868ec) * [jdk1.8的HashMap和ConcurrentHashMap](https://link.juejin.im?target=https%3A%2F%2Fmy.oschina.net%2Fpingpangkuangmo%2Fblog%2F817973) * [ConcurrentHashMap源碼分析（JDK8版本）](https://link.juejin.im?target=http%3A%2F%2Fblog.csdn.net%2Fu010723709%2Farticle%2Fdetails%2F48007881) * * * ### 最后 謝謝閱讀，如果可以的話歡迎大家轉發和點贊。如需轉載注明[原地址](https://link.juejin.im?target=www.54tianzhisheng.cn%2F2017%2F06%2F10%2FHashMap-Hashtable%2F)就行。 群 528776268 歡迎各位大牛進群一起討論。  作者：zhisheng 鏈接：https://juejin.im/post/593e5364ac502e006c0c7690 來源：掘金 著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。