HashMap和Hashtable的比較是Java面試中的常見問題吊档，用來考驗程序員是否能夠正確使用集合類以及是否可以隨機(jī)應(yīng)變使用多種思路解決問題秒拔。HashMap的工作原理穷娱、ArrayList與Vector的比較以及這個問題是有關(guān)Java 集合框架的最經(jīng)典的問題谷市。Hashtable是個過時的集合類亡嫌，存在于Java API中很久了嚎于。在Java 4中被重寫了，實現(xiàn)了Map接口挟冠，所以自此以后也成了Java集合框架中的一部分于购。Hashtable和HashMap在Java面試中相當(dāng)容易被問到，甚至成為了集合框架面試題中最常被考的問題知染，所以在參加任何Java面試之前肋僧，都不要忘了準(zhǔn)備這一題。
這篇文章中控淡，我們不僅將會看到HashMap和Hashtable的區(qū)別嫌吠，還將看到它們之間的相似之處。
HashMap和Hashtable的區(qū)別
HashMap和Hashtable都實現(xiàn)了Map接口掺炭，但決定用哪一個之前先要弄清楚它們之間的分別辫诅。主要的區(qū)別有：線程安全性，同步(synchronization)涧狮，以及速度炕矮。
繼承的父類不同
Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類勋篓。但二者都實現(xiàn)了Map接口吧享。對null對象的支持不同
HashMap是支持null鍵和null值的魏割，而HashTable在遇到null時譬嚣，會拋出NullPointerException異常。這并不是因為HashTable有什么特殊的實現(xiàn)層面的原因?qū)е虏荒苤С謓ull鍵和null值钞它，這僅僅是因為HashMap在實現(xiàn)時對null做了特殊處理拜银，將null的hashCode值定為了0，從而將其存放在哈希表的第0個bucket中遭垛。容量大小及擴(kuò)容方式不同
HashMap和HashTable都使用哈希表來存儲鍵值對尼桶。在數(shù)據(jù)結(jié)構(gòu)上是基本相同的，都創(chuàng)建了一個繼承自Map.Entry的私有的內(nèi)部類Entry锯仪，每一個Entry對象表示存儲在哈希表中的一個鍵值對泵督。
Entry對象唯一表示一個鍵值對，有四個屬性：
-K key 鍵對象
-V value 值對象
-int hash 鍵對象的hash值
-Entry entry 指向鏈表中下一個Entry對象庶喜，可為null小腊，表示當(dāng)前Entry對象在鏈表尾部救鲤。
HashMap/HashTable內(nèi)部用Entry數(shù)組實現(xiàn)哈希表，而對于映射到同一個哈希桶（數(shù)組的同一個位置）的鍵值對秩冈，使用Entry鏈表來存儲本缠。
HashMap/HashTable初始容量大小和每次擴(kuò)充容量大小的不同：HashTable默認(rèn)的初始大小為11，之后每次擴(kuò)充為原來的2n+1入问。HashMap默認(rèn)的初始化大小為16丹锹，之后每次擴(kuò)充為原來的2倍。如果在創(chuàng)建時給定了初始化大小芬失，那么HashTable會直接使用你給定的大小楣黍，而HashMap會將其擴(kuò)充為2的冪次方大小。線程安全性不同
HashTable是同步的（原因：公開的方法比如get都使用了synchronized描述符麸折。而遍歷視圖比如keySet都使用了Collections.synchronizedXXX進(jìn)行了同步包裝）锡凝，HashMap不是，也就是說HashTable在多線程使用的情況下垢啼，不需要做額外的同步窜锯，而HashMap則不行。
由于Hashtable是線程安全的也是synchronized芭析，所以在單線程環(huán)境下它比HashMap速度要慢锚扎。
如果要保持線程安全可以選用ConcurrentHashMap，ConcurrentHashMap引入了分割(segmentation)馁启，不論它變得多么大驾孔，僅僅需要鎖定map的某個部分，而其它的線程不需要等到迭代完成才能訪問map惯疙。Hashtable則會鎖定整個map翠勉，Hashtable的大小增加到一定的時候，性能會急劇下降霉颠，因為迭代時需要被鎖定很長的時間对碌。簡而言之，在迭代的過程中蒿偎，ConcurrentHashMap僅僅鎖定map的某個部分朽们，而Hashtable則會鎖定整個map，ConcurrentHashMap比Hashtable高效诉位。Hash值不同
Hashtable計算hash值骑脱，直接用key的hashCode()，而HashMap重新計算了key的hash值苍糠，Hashtable在求hash值對應(yīng)的位置索引時叁丧，用取模運(yùn)算，而HashMap在求位置索引時，則用與運(yùn)算拥娄，且這里一般先用hash&0x7FFFFFFF后坷衍，再對length取模，&0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值条舔，因為hash值有可能為負(fù)數(shù)枫耳，而&0x7FFFFFFF后，只有符號位改變孟抗，而后面的位都不變迁杨。迭代器不同
HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的凄硼。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素）铅协，將會拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會拋出ConcurrentModificationException異常摊沉。但這并不是一個一定發(fā)生的行為狐史，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別说墨。
由于Hashtable是線程安全的也是synchronized骏全，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步尼斧，只需要單一線程姜贡，那么使用HashMap性能要好過Hashtable。
HashMap不能保證隨著時間的推移Map中的元素次序是不變的棺棵。
要注意的一些重要術(shù)語：
sychronized意味著在一次僅有一個線程能夠更改Hashtable楼咳。就是說任何線程要更新Hashtable時要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable烛恤。
Fail-safe和iterator迭代器相關(guān)母怜。如果某個集合對象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對象缚柏，將會拋出ConcurrentModificationException異常苹熏。但其它線程可以通過set()方法更改集合對象是允許的，因為這并沒有從“結(jié)構(gòu)上”更改集合船惨。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改柜裸，再調(diào)用set()方法缕陕，將會拋出IllegalArgumentException異常粱锐。
結(jié)構(gòu)上的更改指的是刪除或者插入一個元素，這樣會影響到map的結(jié)構(gòu)扛邑。
Fail-fast與Fail-safe比較
什么是 fail-fast 機(jī)制?
fail-fast機(jī)制在遍歷一個集合時怜浅，當(dāng)集合結(jié)構(gòu)被修改，會拋出Concurrent Modification Exception。
fail-fast會在以下兩種情況下拋出ConcurrentModificationException
- 單線程環(huán)境
集合被創(chuàng)建后恶座，在遍歷它的過程中修改了結(jié)構(gòu)搀暑。
注意 remove()方法會讓expectModcount和modcount 相等，所以是不會拋出這個異常跨琳。
- 多線程環(huán)境
當(dāng)一個線程在遍歷這個集合自点，而另一個線程對這個集合的結(jié)構(gòu)進(jìn)行了修改。
注意脉让，迭代器的快速失敗行為無法得到保證桂敛，因為一般來說，不可能對是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證溅潜∈趸＃快速失敗迭代器會盡最大努力拋出 ConcurrentModificationException。因此滚澜，為提高這類迭代器的正確性而編寫一個依賴于此異常的程序是錯誤的做法：迭代器的快速失敗行為應(yīng)該僅用于檢測 bug粗仓。
fail-fast機(jī)制是如何檢測的？
迭代器在遍歷過程中是直接訪問內(nèi)部數(shù)據(jù)的设捐，因此內(nèi)部的數(shù)據(jù)在遍歷的過程中無法被修改借浊。為了保證不被修改，迭代器內(nèi)部維護(hù)了一個標(biāo)記 “mode” 萝招，當(dāng)集合結(jié)構(gòu)改變（添加刪除或者修改）巴碗，標(biāo)記"mode"會被修改，而迭代器每次的hasNext()和next()方法都會檢查該"mode"是否被改變即寒，當(dāng)檢測到被修改時橡淆，拋出Concurrent Modification Exception。
下面看看ArrayList迭代器部分的源碼母赵。
private class Itr implements Iterator<E> {
int cursor;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return (this.cursor != ArrayList.this.size);
}
public E next() {
checkForComodification();
/** 省略此處代碼 */
}
public void remove() {
if (this.lastRet < 0)
throw new IllegalStateException();
checkForComodification();
/** 省略此處代碼 */
}
final void checkForComodification() {
if (ArrayList.this.modCount == this.expectedModCount)
return;
throw new ConcurrentModificationException();
}
}
可以看到它的標(biāo)記“mode”為 expectedModeCount逸爵。
fail-safe機(jī)制
fail-safe任何對集合結(jié)構(gòu)的修改都會在一個復(fù)制的集合上進(jìn)行修改，因此不會拋出ConcurrentModificationException凹嘲。
fail-safe機(jī)制有兩個問題
需要復(fù)制集合师倔，產(chǎn)生大量的無效對象，開銷大周蹭。
無法保證讀取的數(shù)據(jù)是目前原始數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)趋艘。
fail-fast和 fail-safe 的區(qū)別
| 區(qū)別 | Fail Fast Iterator | Fail Safe Iterator | Enumeration |
|---|---|---|---|
| Throw ConcurrentModification Exception | Yes | No | No |
| Clone object | No | Yes | Yes |
| Memory Overhead | No | Yes | Yes |
| Examples | HashMap,Vector,ArrayList,HashSet | CopyOnWriteArrayList,ConcurrentHashMap | Vector,Hashtable |
Iterator和 Enumeration 的區(qū)別
- 函數(shù)接口不同
Enumeration只有2個函數(shù)接口。通過Enumeration凶朗，我們只能讀取集合的數(shù)據(jù)瓷胧，而不能對數(shù)據(jù)進(jìn)行修改。
Iterator只有3個函數(shù)接口棚愤。Iterator除了能讀取集合的數(shù)據(jù)之外搓萧，也能數(shù)據(jù)進(jìn)行刪除操作杂数。 - Iterator支持fail-fast機(jī)制，而Enumeration不支持瘸洛。
Enumeration 是JDK 1.0添加的接口揍移。使用到它的函數(shù)包括Vector、Hashtable等類反肋，這些類都是JDK 1.0中加入的那伐，Enumeration存在的目的就是為它們提供遍歷接口。Enumeration本身并沒有支持同步石蔗，而在Vector喧锦、Hashtable實現(xiàn)Enumeration時，添加了同步抓督。
而Iterator 是JDK 1.2才添加的接口燃少，它也是為了HashMap、ArrayList等集合提供遍歷接口铃在。Iterator是支持fail-fast機(jī)制的：當(dāng)多個線程對同一個集合的內(nèi)容進(jìn)行操作時阵具，就可能會產(chǎn)生fail-fast事件。
我們能否讓HashMap同步定铜？
HashMap可以通過下面的語句進(jìn)行同步：
Map m = Collections.synchronizeMap(hashMap);
結(jié)論
Hashtable和HashMap有幾個主要的不同：線程安全以及速度阳液。僅在你需要完全的線程安全的時候使用Hashtable，而如果你使用Java 5或以上的話揣炕，請使用ConcurrentHashMap吧帘皿。
