原文轉(zhuǎn)自：http://www.54tianzhisheng.cn/2017/06/10/HashMap-Hashtable/
HashMap 和 Hashtable 的比較是 Java 面試中的常見問題，用來考驗程序員是否能夠正確使用集合類以及是否可以隨機應變使用多種思路解決問題岸啡。HashMap 的工作原理原叮、ArrayList 與 Vector 的比較以及這個問題是有關(guān) Java 集合框架的最經(jīng)典的問題。Hashtable 是個過時的集合類巡蘸，存在于 Java API 中很久了奋隶。在 Java 4 中被重寫了，實現(xiàn)了 Map 接口悦荒，所以自此以后也成了 Java 集合框架中的一部分唯欣。Hashtable 和 HashMap 在 Java 面試中相當容易被問到，甚至成為了集合框架面試題中最常被考的問題搬味，所以在參加任何 Java 面試之前境氢，都不要忘了準備這一題。
這篇文章中碰纬，我們不僅將會看到 HashMap 和 Hashtable 的區(qū)別萍聊，還將看到它們之間的相似之處。
HashMap 和 Hashtable 都實現(xiàn)了 Map 接口悦析，但決定用哪一個之前先要弄清楚它們之間的分別寿桨。主要的區(qū)別有：線程安全性，同步 (synchronization)强戴，以及速度亭螟。
HashMap 幾乎可以等價于 Hashtable挡鞍，除了 HashMap 是非 synchronized 的，并可以接受 null(HashMap 可以接受為 null 的鍵值 (key) 和值 (value)预烙，而 Hashtable 則不行)墨微。
HashMap 是非 synchronized，而 Hashtable 是 synchronized扁掸，這意味著 Hashtable 是線程安全的翘县，多個線程可以共享一個 Hashtable；而如果沒有正確的同步的話也糊，多個線程是不能共享 HashMap 的炼蹦。Java 5 提供了 ConcurrentHashMap，它是 HashTable 的替代狸剃，比 HashTable 的擴展性更好掐隐。
另一個區(qū)別是 HashMap 的迭代器 (Iterator) 是 fail-fast 迭代器，而 Hashtable 的 enumerator 迭代器不是 fail-fast 的钞馁。所以當有其它線程改變了 HashMap 的結(jié)構(gòu)（增加或者移除元素）虑省，將會拋出ConcurrentModificationException，但迭代器本身的 remove() 方法移除元素則不會拋出ConcurrentModificationException 異常僧凰。但這并不是一個一定發(fā)生的行為探颈，要看 JVM。這條同樣也是Enumeration 和 Iterato r的區(qū)別训措。
由于 Hashtable 是線程安全的也是 synchronized伪节，所以在單線程環(huán)境下它比 HashMap 要慢。如果你不需要同步绩鸣，只需要單一線程怀大，那么使用 HashMap 性能要好過 Hashtable。
HashMap 不能保證隨著時間的推移 Map 中的元素次序是不變的呀闻。
1) sychronized 意味著在一次僅有一個線程能夠更改 Hashtable化借。就是說任何線程要更新 Hashtable 時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新 Hashtable捡多。
2) Fail-safe 和 iterator 迭代器相關(guān)蓖康。如果某個集合對象創(chuàng)建了 Iterator 或者 ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對象垒手，將會拋出 ConcurrentModificationException 異常蒜焊。但其它線程可以通過 set() 方法更改集合對象是允許的，因為這并沒有從“結(jié)構(gòu)上”更改集合科贬。但是假如已經(jīng)從結(jié)構(gòu)上進行了更改山涡，再調(diào)用 set() 方法，將會拋出 IllegalArgumentException 異常。
3) 結(jié)構(gòu)上的更改指的是刪除或者插入一個元素鸭丛，這樣會影響到 map 的結(jié)構(gòu)。
HashMap 可以通過下面的語句進行同步：
Map m = Collections.synchronizeMap(hashMap);
Hashtable 和 HashMap 有幾個主要的不同：線程安全以及速度鳞溉。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用 Java 5 或以上的話鼠哥，請使用 ConcurrentHashMap 吧熟菲。
轉(zhuǎn)載自：HashMap和Hashtable的區(qū)別
關(guān)于 HashMap 線程不安全這一點，《Java并發(fā)編程的藝術(shù)》一書中是這樣說的：
HashMap 在并發(fā)執(zhí)行 put 操作時會引起死循環(huán)朴恳，導致 CPU 利用率接近 100%抄罕。因為多線程會導致 HashMap 的 Node 鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)于颖，Node 的 next 節(jié)點永遠不為空呆贿，就會在獲取 Node 時產(chǎn)生死循環(huán)。
原因：
疫苗：JAVA HASHMAP的死循環(huán) —— 酷殼
HashMap在java并發(fā)中如何發(fā)生死循環(huán)
How does a HashMap work in JAVA
下面的是自己有道云筆記中記錄的：
HashMap 森渐， HashTable 和 HashSet 區(qū)別
關(guān)于 HashMap 的一些說法：
a) HashMap 實際上是一個“鏈表散列”的數(shù)據(jù)結(jié)構(gòu)做入，即數(shù)組和鏈表的結(jié)合體。HashMap 的底層結(jié)構(gòu)是一個數(shù)組同衣，數(shù)組中的每一項是一條鏈表竟块。
b) HashMap 的實例有倆個參數(shù)影響其性能： “初始容量” 和 裝填因子。
c) HashMap 實現(xiàn)不同步耐齐，線程不安全浪秘。 HashTable 線程安全
d) HashMap 中的 key-value 都是存儲在 Entry 中的。
e) HashMap 可以存 null 鍵和 null 值埠况，不保證元素的順序恒久不變耸携，它的底層使用的是數(shù)組和鏈表，通過hashCode() 方法和 equals 方法保證鍵的唯一性
f) 解決沖突主要有三種方法：定址法询枚，拉鏈法违帆，再散列法。HashMap 是采用拉鏈法解決哈希沖突的金蜀。
注： 鏈表法是將相同 hash 值的對象組成一個鏈表放在 hash 值對應的槽位刷后；
用開放定址法解決沖突的做法是：當沖突發(fā)生時，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個探查(測)序列渊抄。 沿此序列逐個單元地查找尝胆，直到找到給定 的關(guān)鍵字，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入护桦，在探查到開放的地址含衔，則可將待插入的新結(jié)點存人該地址單元）。
拉鏈法解決沖突的做法是： 將所有關(guān)鍵字為同義詞的結(jié)點鏈接在同一個單鏈表中 。若選定的散列表長度為m贪染，則可將散列表定義為一個由m個頭指針組成的指針數(shù) 組T[0..m-1]缓呛。凡是散列地址為i的結(jié)點，均插入到以T[i]為頭指針的單鏈表中杭隙。T中各分量的初值均應為空指針哟绊。在拉鏈法中，裝填因子α可以大于1痰憎，但一般均取α≤1票髓。拉鏈法適合未規(guī)定元素的大小。
Hashtable 和 HashMap 的區(qū)別：
a) 繼承不同铣耘。
public class Hashtable extends Dictionary implements Map
public class HashMap extends AbstractMap implements Map
b) Hashtable 中的方法是同步的洽沟，而 HashMap 中的方法在缺省情況下是非同步的。在多線程并發(fā)的環(huán)境下蜗细，可以直接使用 Hashtable裆操，但是要使用 HashMap 的話就要自己增加同步處理了。
c) Hashtable 中鳄乏， key 和 value 都不允許出現(xiàn) null 值跷车。 在 HashMap 中， null 可以作為鍵橱野，這樣的鍵只有一個朽缴；可以有一個或多個鍵所對應的值為 null 。當 get() 方法返回 null 值時水援，即可以表示 HashMap 中沒有該鍵密强，也可以表示該鍵所對應的值為 null 。因此蜗元，在 HashMap 中不能由 get() 方法來判斷 HashMap 中是否存在某個鍵或渤， 而應該用 containsKey() 方法來判斷。
d) 兩個遍歷方式的內(nèi)部實現(xiàn)上不同奕扣。Hashtable薪鹦、HashMap 都使用了Iterator。而由于歷史原因惯豆，Hashtable還使用了 Enumeration 的方式 池磁。
e) 哈希值的使用不同，HashTable 直接使用對象的 hashCode楷兽。而 HashMap 重新計算 hash 值地熄。
f) Hashtable 和 HashMap 它們兩個內(nèi)部實現(xiàn)方式的數(shù)組的初始大小和擴容的方式。HashTable 中 hash 數(shù)組默認大小是11芯杀，增加的方式是 old*2+1端考。HashMap 中 hash 數(shù)組的默認大小是 16雅潭，而且一定是2的指數(shù)。
注： HashSet 子類依靠 hashCode() 和 equal() 方法來區(qū)分重復元素却特。
HashSet 內(nèi)部使用 Map 保存數(shù)據(jù)扶供，即將 HashSet 的數(shù)據(jù)作為 Map 的 key 值保存，這也是 HashSet 中元素不能重復的原因核偿。而 Map 中保存 key 值的,會去判斷當前 Map 中是否含有該 Key 對象诚欠，內(nèi)部是先通過 key 的hashCode, 確定有相同的 hashCode 之后，再通過 equals 方法判斷是否相同漾岳。
《HashMap 的工作原理》
HashMap的工作原理是近年來常見的Java面試題。幾乎每個Java程序員都知道HashMap粉寞，都知道哪里要用HashMap尼荆，知道 Hashtable和HashMap之間的區(qū)別，那么為何這道面試題如此特殊呢唧垦？是因為這道題考察的深度很深捅儒。這題經(jīng)常出現(xiàn)在高級或中高級面試中。投資銀行更喜歡問這個問題振亮，甚至會要求你實現(xiàn)HashMap來考察你的編程能力巧还。ConcurrentHashMap和其它同步集合的引入讓這道題變得更加復雜。讓我們開始探索的旅程吧坊秸！
“你用過HashMap嗎麸祷？” “什么是HashMap？你為什么用到它褒搔？”
幾乎每個人都會回答“是的”阶牍，然后回答HashMap的一些特性，譬如HashMap可以接受null鍵值和值星瘾，而Hashtable則不能走孽；HashMap是非synchronized;HashMap很快；以及HashMap儲存的是鍵值對等等琳状。這顯示出你已經(jīng)用過HashMap磕瓷，而且對它相當?shù)氖煜ぁ５敲嬖嚬賮韨€急轉(zhuǎn)直下念逞，從此刻開始問出一些刁鉆的問題困食，關(guān)于HashMap的更多基礎(chǔ)的細節(jié)。面試官可能會問出下面的問題：
“你知道HashMap的工作原理嗎肮柜？” “你知道HashMap的get()方法的工作原理嗎陷舅？”
你也許會回答“我沒有詳查標準的Java API，你可以看看Java源代碼或者Open JDK审洞±痴觯”“我可以用Google找到答案待讳。”
但一些面試者可能可以給出答案仰剿，“HashMap是基于hashing的原理创淡，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象南吮。當我們給put()方法傳遞鍵和值時琳彩，我們先對鍵調(diào)用hashCode()方法，返回的hashCode用于找到bucket位置來儲存Entry對象部凑÷斗Γ”這里關(guān)鍵點在于指出，HashMap是在bucket中儲存鍵對象和值對象涂邀，作為Map.Entry瘟仿。這一點有助于理解獲取對象的邏輯。如果你沒有意識到這一點比勉，或者錯誤的認為僅僅只在bucket中存儲值的話劳较，你將不會回答如何從HashMap中獲取對象的邏輯。這個答案相當?shù)恼_浩聋，也顯示出面試者確實知道hashing以及HashMap的工作原理观蜗。但是這僅僅是故事的開始，當面試官加入一些Java程序員每天要碰到的實際場景的時候衣洁，錯誤的答案頻現(xiàn)墓捻。下個問題可能是關(guā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呢矢渊？：）
熱心的讀者貢獻了更多的關(guān)于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提供更強的線程安全性郁轻〕崛ⅲ看看這篇博客查看Hashtable和ConcurrentHashMap的區(qū)別。
我個人很喜歡這個問題好唯，因為這個問題的深度和廣度竭沫，也不直接的涉及到不同的概念。讓我們再來看看這些問題設(shè)計哪些知識點：
hashing的概念
HashMap中解決碰撞的方法
equals()和hashCode()的應用骑篙，以及它們在HashMap中的重要性
不可變對象的好處
HashMap多線程的條件競爭
重新調(diào)整HashMap的大小
HashMap基于hashing原理蜕提，我們通過put()和get()方法儲存和獲取對象。當我們將鍵值對傳遞給put()方法時靶端，它調(diào)用鍵對象的hashCode()方法來計算hashcode谎势，讓后找到bucket位置來儲存值對象凛膏。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對脏榆，然后返回值對象猖毫。HashMap使用鏈表來解決碰撞問題，當發(fā)生碰撞了须喂，對象將會儲存在鏈表的下一個節(jié)點中吁断。 HashMap在每個鏈表節(jié)點中儲存鍵值對對象。
當兩個不同的鍵對象的hashcode相同時會發(fā)生什么镊折？ 它們會儲存在同一個bucket位置的鏈表中胯府。鍵對象的equals()方法用來找到鍵值對。
因為HashMap的好處非常多恨胚，我曾經(jīng)在電子商務的應用中使用HashMap作為緩存骂因。因為金融領(lǐng)域非常多的運用Java，也出于性能的考慮赃泡，我們會經(jīng)常用到HashMap和ConcurrentHashMap寒波。你可以查看更多的關(guān)于HashMap的文章:
轉(zhuǎn)載自：HashMap的工作原理
其他的 HashMap 學習資料：
JDK1.8HashMap原理和源碼分析(java面試收藏)
談談ConcurrentHashMap1.7和1.8的不同實現(xiàn)
