HashMap和Hashtable的比較是Java面試中的常見問題，用來(lái)考驗(yàn)程序員是否能夠正確使用集合類以及是否可以隨機(jī)應(yīng)變使用多種思路解決問題。HashMap的工作原理、ArrayList與Vector的比較以及這個(gè)問題是有關(guān)Java 集合框架的最經(jīng)典的問題。Hashtable是個(gè)過時(shí)的集合類，存在于Java API中很久了。在Java 4中被重寫了，實(shí)現(xiàn)了Map接口，所以自此以后也成了Java集合框架中的一部分。Hashtable和HashMap在Java面試中相當(dāng)容易被問到，甚至成為了集合框架面試題中最常被考的問題，所以在參加任何Java面試之前，都不要忘了準(zhǔn)備這一題。

這篇文章中，我們不僅將會(huì)看到HashMap和Hashtable的區(qū)別，還將看到它們之間的相似之處。

HashMap和Hashtable的區(qū)別

HashMap和Hashtable都實(shí)現(xiàn)了Map接口，但決定用哪一個(gè)之前先要弄清楚它們之間的分別。主要的區(qū)別有：線程安全性，同步(synchronization)，以及速度。

• 繼承的父類不同
  Hashtable繼承自Dictionary類，而HashMap繼承自AbstractMap類。但二者都實(shí)現(xiàn)了Map接口。

• 對(duì)null對(duì)象的支持不同
  HashMap是支持null鍵和null值的，而HashTable在遇到null時(shí)，會(huì)拋出NullPointerException異常。這并不是因?yàn)镠ashTable有什么特殊的實(shí)現(xiàn)層面的原因?qū)е虏荒苤С謓ull鍵和null值，這僅僅是因?yàn)镠ashMap在實(shí)現(xiàn)時(shí)對(duì)null做了特殊處理，將null的hashCode值定為了0，從而將其存放在哈希表的第0個(gè)bucket中。

• 容量大小及擴(kuò)容方式不同
  HashMap和HashTable都使用哈希表來(lái)存儲(chǔ)鍵值對(duì)。在數(shù)據(jù)結(jié)構(gòu)上是基本相同的，都創(chuàng)建了一個(gè)繼承自Map.Entry的私有的內(nèi)部類Entry，每一個(gè)Entry對(duì)象表示存儲(chǔ)在哈希表中的一個(gè)鍵值對(duì)。
  Entry對(duì)象唯一表示一個(gè)鍵值對(duì)，有四個(gè)屬性：
  -K key 鍵對(duì)象
  -V value 值對(duì)象
  -int hash 鍵對(duì)象的hash值
  -Entry entry 指向鏈表中下一個(gè)Entry對(duì)象，可為null，表示當(dāng)前Entry對(duì)象在鏈表尾部。
  HashMap/HashTable內(nèi)部用Entry數(shù)組實(shí)現(xiàn)哈希表，而對(duì)于映射到同一個(gè)哈希桶（數(shù)組的同一個(gè)位置）的鍵值對(duì)，使用Entry鏈表來(lái)存儲(chǔ)。
  HashMap/HashTable初始容量大小和每次擴(kuò)充容量大小的不同：HashTable默認(rèn)的初始大小為11，之后每次擴(kuò)充為原來(lái)的2n+1。HashMap默認(rèn)的初始化大小為16，之后每次擴(kuò)充為原來(lái)的2倍。如果在創(chuàng)建時(shí)給定了初始化大小，那么HashTable會(huì)直接使用你給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大小。

• 線程安全性不同
  HashTable是同步的（原因：公開的方法比如get都使用了synchronized描述符。而遍歷視圖比如keySet都使用了Collections.synchronizedXXX進(jìn)行了同步包裝），HashMap不是，也就是說(shuō)HashTable在多線程使用的情況下，不需要做額外的同步，而HashMap則不行。
  由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap速度要慢。
  如果要保持線程安全可以選用ConcurrentHashMap，ConcurrentHashMap引入了分割(segmentation)，不論它變得多么大，僅僅需要鎖定map的某個(gè)部分，而其它的線程不需要等到迭代完成才能訪問map。Hashtable則會(huì)鎖定整個(gè)map，Hashtable的大小增加到一定的時(shí)候，性能會(huì)急劇下降，因?yàn)榈鷷r(shí)需要被鎖定很長(zhǎng)的時(shí)間。簡(jiǎn)而言之，在迭代的過程中，ConcurrentHashMap僅僅鎖定map的某個(gè)部分，而Hashtable則會(huì)鎖定整個(gè)map，ConcurrentHashMap比Hashtable高效。

• Hash值不同
  Hashtable計(jì)算hash值，直接用key的hashCode()，而HashMap重新計(jì)算了key的hash值，Hashtable在求hash值對(duì)應(yīng)的位置索引時(shí)，用取模運(yùn)算，而HashMap在求位置索引時(shí)，則用與運(yùn)算，且這里一般先用hash&0x7FFFFFFF后，再對(duì)length取模，&0x7FFFFFFF的目的是為了將負(fù)的hash值轉(zhuǎn)化為正值，因?yàn)閔ash值有可能為負(fù)數(shù)，而&0x7FFFFFFF后，只有符號(hào)位改變，而后面的位都不變。

• 迭代器不同
  HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。所以當(dāng)有其它線程改變了HashMap的結(jié)構(gòu)（增加或者移除元素），將會(huì)拋出ConcurrentModificationException，但迭代器本身的remove()方法移除元素則不會(huì)拋出ConcurrentModificationException異常。但這并不是一個(gè)一定發(fā)生的行為，要看JVM。這條同樣也是Enumeration和Iterator的區(qū)別。

由于Hashtable是線程安全的也是synchronized，所以在單線程環(huán)境下它比HashMap要慢。如果你不需要同步，只需要單一線程，那么使用HashMap性能要好過Hashtable。
HashMap不能保證隨著時(shí)間的推移Map中的元素次序是不變的。

要注意的一些重要術(shù)語(yǔ)：

• sychronized意味著在一次僅有一個(gè)線程能夠更改Hashtable。就是說(shuō)任何線程要更新Hashtable時(shí)要首先獲得同步鎖，其它線程要等到同步鎖被釋放之后才能再次獲得同步鎖更新Hashtable。

• Fail-safe和iterator迭代器相關(guān)。如果某個(gè)集合對(duì)象創(chuàng)建了Iterator或者ListIterator，然后其它的線程試圖“結(jié)構(gòu)上”更改集合對(duì)象，將會(huì)拋出ConcurrentModificationException異常。但其它線程可以通過set()方法更改集合對(duì)象是允許的，因?yàn)檫@并沒有從“結(jié)構(gòu)上”更改集合。但是假如已經(jīng)從結(jié)構(gòu)上進(jìn)行了更改，再調(diào)用set()方法，將會(huì)拋出IllegalArgumentException異常。

• 結(jié)構(gòu)上的更改指的是刪除或者插入一個(gè)元素，這樣會(huì)影響到map的結(jié)構(gòu)。

Fail-fast與Fail-safe比較

什么是 fail-fast 機(jī)制?

fail-fast機(jī)制在遍歷一個(gè)集合時(shí)，當(dāng)集合結(jié)構(gòu)被修改，會(huì)拋出Concurrent Modification Exception。

fail-fast會(huì)在以下兩種情況下拋出ConcurrentModificationException

• 單線程環(huán)境

集合被創(chuàng)建后，在遍歷它的過程中修改了結(jié)構(gòu)。

注意 remove()方法會(huì)讓expectModcount和modcount 相等，所以是不會(huì)拋出這個(gè)異常。

• 多線程環(huán)境

當(dāng)一個(gè)線程在遍歷這個(gè)集合，而另一個(gè)線程對(duì)這個(gè)集合的結(jié)構(gòu)進(jìn)行了修改。

注意，迭代器的快速失敗行為無(wú)法得到保證，因?yàn)橐话銇?lái)說(shuō)，不可能對(duì)是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證?？焖偈〉鲿?huì)盡最大努力拋出 ConcurrentModificationException。因此，為提高這類迭代器的正確性而編寫一個(gè)依賴于此異常的程序是錯(cuò)誤的做法：迭代器的快速失敗行為應(yīng)該僅用于檢測(cè) bug。

fail-fast機(jī)制是如何檢測(cè)的？

迭代器在遍歷過程中是直接訪問內(nèi)部數(shù)據(jù)的，因此內(nèi)部的數(shù)據(jù)在遍歷的過程中無(wú)法被修改。為了保證不被修改，迭代器內(nèi)部維護(hù)了一個(gè)標(biāo)記 “mode” ，當(dāng)集合結(jié)構(gòu)改變（添加刪除或者修改），標(biāo)記"mode"會(huì)被修改，而迭代器每次的hasNext()和next()方法都會(huì)檢查該"mode"是否被改變，當(dāng)檢測(cè)到被修改時(shí)，拋出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任何對(duì)集合結(jié)構(gòu)的修改都會(huì)在一個(gè)復(fù)制的集合上進(jìn)行修改，因此不會(huì)拋出ConcurrentModificationException。

fail-safe機(jī)制有兩個(gè)問題

• 需要復(fù)制集合，產(chǎn)生大量的無(wú)效對(duì)象，開銷大。

• 無(wú)法保證讀取的數(shù)據(jù)是目前原始數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)。

fail-fast和 fail-safe 的區(qū)別

Iterator和 Enumeration 的區(qū)別

• 函數(shù)接口不同
  Enumeration只有2個(gè)函數(shù)接口。通過Enumeration，我們只能讀取集合的數(shù)據(jù)，而不能對(duì)數(shù)據(jù)進(jìn)行修改。
  Iterator只有3個(gè)函數(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實(shí)現(xiàn)Enumeration時(shí)，添加了同步。
  而Iterator 是JDK 1.2才添加的接口，它也是為了HashMap、ArrayList等集合提供遍歷接口。Iterator是支持fail-fast機(jī)制的：當(dāng)多個(gè)線程對(duì)同一個(gè)集合的內(nèi)容進(jìn)行操作時(shí)，就可能會(huì)產(chǎn)生fail-fast事件。

我們能否讓HashMap同步？

HashMap可以通過下面的語(yǔ)句進(jìn)行同步：
Map m = Collections.synchronizeMap(hashMap);

結(jié)論

Hashtable和HashMap有幾個(gè)主要的不同：線程安全以及速度。僅在你需要完全的線程安全的時(shí)候使用Hashtable，而如果你使用Java 5或以上的話，請(qǐng)使用ConcurrentHashMap吧。