概述
- (01) Map 是“鍵值對(duì)”映射的抽象接口。
- (02) AbstractMap 實(shí)現(xiàn)了Map中的絕大部分函數(shù)接口。它減少了“Map的實(shí)現(xiàn)類”的重復(fù)編碼。
- (03) SortedMap 有序的“鍵值對(duì)”映射接口。
- (04) NavigableMap 是繼承于SortedMap的，支持導(dǎo)航函數(shù)的接口。
- (05) HashMap, Hashtable, TreeMap, WeakHashMap這4個(gè)類是“鍵值對(duì)”映射的實(shí)現(xiàn)類。它們各有區(qū)別！
HashMap是基于“拉鏈法”實(shí)現(xiàn)的散列表。一般用于單線程程序中。
Hashtable也是基于“拉鏈法”實(shí)現(xiàn)的散列表。它一般用于多線程程序中。
WeakHashMap也是基于“拉鏈法”實(shí)現(xiàn)的散列表，它一般也用于單線程程序中。相比HashMap，WeakHashMap中的鍵是“弱鍵”，當(dāng)“弱鍵”被GC回收時(shí)，它對(duì)應(yīng)的鍵值對(duì)也會(huì)被從WeakHashMap中刪除；而HashMap中的鍵是強(qiáng)鍵。
TreeMap是有序的散列表，它是通過紅黑樹實(shí)現(xiàn)的。它一般用于單線程中存儲(chǔ)有序的映射。
HashMap Vs Hashtable
第2.1部分 HashMap和Hashtable的相同點(diǎn)
HashMap和Hashtable都是存儲(chǔ)“鍵值對(duì)(key-value)”的散列表，而且都是采用拉鏈法實(shí)現(xiàn)的。
存儲(chǔ)的思想都是：通過table數(shù)組存儲(chǔ)，數(shù)組的每一個(gè)元素都是一個(gè)Entry；而一個(gè)Entry就是一個(gè)單向鏈表，Entry鏈表中的每一個(gè)節(jié)點(diǎn)就保存了key-value鍵值對(duì)數(shù)據(jù)。
- 添加key-value鍵值對(duì)：首先，根據(jù)key值計(jì)算出哈希值，再計(jì)算出數(shù)組索引(即，該key-value在table中的索引)。然后，根據(jù)數(shù)組索引找到Entry(即，單向鏈表)，再遍歷單向鏈表，將key和鏈表中的每一個(gè)節(jié)點(diǎn)的key進(jìn)行對(duì)比。若key已經(jīng)存在Entry鏈表中，則用該value值取代舊的value值；若key不存在Entry鏈表中，則新建一個(gè)key-value節(jié)點(diǎn)，并將該節(jié)點(diǎn)插入Entry鏈表的表頭位置。
- 刪除key-value鍵值對(duì)：刪除鍵值對(duì)，相比于“添加鍵值對(duì)”來說，簡(jiǎn)單很多。首先，還是根據(jù)key計(jì)算出哈希值，再計(jì)算出數(shù)組索引(即，該key-value在table中的索引)。然后，根據(jù)索引找出Entry(即，單向鏈表)。若節(jié)點(diǎn)key-value存在與鏈表Entry中，則刪除鏈表中的節(jié)點(diǎn)即可。
第2.2部分 HashMap和Hashtable的不同點(diǎn)
1 繼承和實(shí)現(xiàn)方式不同
HashMap 繼承于AbstractMap，實(shí)現(xiàn)了Map、Cloneable、java.io.Serializable接口。AbstractMap是一個(gè)抽象類，它實(shí)現(xiàn)了Map接口的絕大部分API函數(shù)；為Map的具體實(shí)現(xiàn)類提供了極大的便利。
Hashtable 繼承于Dictionary，實(shí)現(xiàn)了Map、Cloneable、java.io.Serializable接口。Dictionary是一個(gè)抽象類，它直接繼承于Object類，沒有實(shí)現(xiàn)任何接口。
2 線程安全不同
Hashtable的幾乎所有函數(shù)都是同步的，即它是線程安全的，支持多線程。
而HashMap的函數(shù)則是非同步的，它不是線程安全的。若要在多線程中使用HashMap，需要我們額外的進(jìn)行同步處理。 對(duì)HashMap的同步處理可以使用Collections類提供的synchronizedMap靜態(tài)方法，或者直接使用JDK 5.0之后提供的java.util.concurrent包里的ConcurrentHashMap類。
3 對(duì)null值的處理不同
HashMap的key、value都可以為null。 當(dāng)HashMap的key為null時(shí)，HashMap會(huì)將其固定的插入table[0]位置(即HashMap散列表的第一個(gè)位置)；而且table[0]處只會(huì)容納一個(gè)key為null的值，當(dāng)有多個(gè)key為null的值插入的時(shí)候，table[0]會(huì)保留最后插入的value。
Hashtable的key、value都不可以為null。否則，會(huì)拋出異常NullPointerException。
4 支持的遍歷種類不同
HashMap只支持Iterator(迭代器)遍歷。
而Hashtable支持Iterator(迭代器)和Enumeration(枚舉器)兩種方式遍歷。
Enumeration 是JDK 1.0添加的接口，只有hasMoreElements(), nextElement() 兩個(gè)API接口，不能通過Enumeration()對(duì)元素進(jìn)行修改 。
5 通過Iterator迭代器遍歷時(shí)，遍歷的順序不同
HashMap是“從前向后”的遍歷數(shù)組；再對(duì)數(shù)組具體某一項(xiàng)對(duì)應(yīng)的鏈表，從表頭開始進(jìn)行遍歷。
Hashtabl是“從后往前”的遍歷數(shù)組；再對(duì)數(shù)組具體某一項(xiàng)對(duì)應(yīng)的鏈表，從表頭開始進(jìn)行遍歷。
HashMap和Hashtable都實(shí)現(xiàn)Map接口，所以支持獲取它們“key的集合”、“value的集合”、“key-value的集合”，然后通過Iterator對(duì)這些集合進(jìn)行遍歷。
HashMap 和Hashtable 遍歷"key-value集合"的方式是：(01) 通過entrySet()獲取“Map.Entry集合”。 (02) 通過iterator()獲取“Map.Entry集合”的迭代器，再進(jìn)行遍歷。
HashMap的實(shí)現(xiàn)方式：先“從前向后”的遍歷數(shù)組；對(duì)數(shù)組具體某一項(xiàng)對(duì)應(yīng)的鏈表，則從表頭開始往后遍歷。
6 容量的初始值 和 增加方式都不一樣
HashMap默認(rèn)的容量大小是16；增加容量時(shí)，每次將容量變?yōu)椤霸既萘縳2”。
Hashtable默認(rèn)的容量大小是11；增加容量時(shí)，每次將容量變?yōu)椤霸既萘縳2 + 1”。
HashMap默認(rèn)的“加載因子”是0.75, 默認(rèn)的容量大小是16。
當(dāng)HashMap的 “實(shí)際容量” >= “閾值”時(shí)，(閾值 = 總的容量 * 加載因子)，就將HashMap的容量翻倍。
Hashtable默認(rèn)的“加載因子”是0.75, 默認(rèn)的容量大小是11。
當(dāng)Hashtable的 “實(shí)際容量” >= “閾值”時(shí)，(閾值 = 總的容量 x 加載因子)，就將變?yōu)椤霸既萘縳2 + 1”。
7 添加key-value時(shí)的hash值算法不同
HashMap添加元素時(shí)，是使用自定義的哈希算法。
Hashtable沒有自定義哈希算法，而直接采用的key的hashCode()。
8 部分API不同
Hashtable支持contains(Object value)方法，而且重寫了toString()方法；
而HashMap不支持contains(Object value)方法，沒有重寫toString()方法。
- 最后，再說說“HashMap和Hashtable”使用的情景。
其實(shí)，若了解它們之間的不同之處后，可以很容易的區(qū)分根據(jù)情況進(jìn)行取舍。例如：(01) 若在單線程中，我們往往會(huì)選擇HashMap；而在多線程中，則會(huì)選擇Hashtable。(02)，若不能插入null元素，則選擇Hashtable；否則，可以選擇HashMap。 - 但這個(gè)不是絕對(duì)的標(biāo)準(zhǔn)。例如，在多線程中，我們可以自己對(duì)HashMap進(jìn)行同步，也可以選擇ConcurrentHashMap。當(dāng)HashMap和Hashtable都不能滿足自己的需求時(shí)，還可以考慮新定義一個(gè)類，繼承或重新實(shí)現(xiàn)散列表；當(dāng)然，一般情況下是不需要的了。
