1.介紹
Map接口定義了一個(gè)保存key-value的對象，該對象中key值是不存在重復(fù)的，每個(gè)key值至多對應(yīng)一個(gè)value
在前面幾篇的文章中分別介紹了Map的實(shí)現(xiàn)類壕鹉，如HashMap、Hashtable聋涨、TreeMap晾浴，詳細(xì)可以查看
2.類圖結(jié)構(gòu)
Map結(jié)構(gòu)
如上圖所示是實(shí)現(xiàn)Map接口的類圖結(jié)構(gòu)，主要包含了如下的類與接口：
- Map接口： 定義將鍵值映射到值的對象牍白，Map規(guī)定不能包含重復(fù)的鍵值脊凰，每個(gè)鍵最多可以映射一個(gè)值,這個(gè)接口是用來替換Dictionary類。
- SortedMap接口:定義按照key排序的Map結(jié)構(gòu)茂腥，規(guī)定key-value是根據(jù)鍵key值的自然排序進(jìn)行排序的笙各，或者根據(jù)構(gòu)造key-value時(shí)設(shè)定的構(gòu)造器進(jìn)行排序。
- NavigableMap接口： 是SortedMap接口的子接口础芍，在其基礎(chǔ)上擴(kuò)展了針對搜索目標(biāo)返回最近匹配項(xiàng)的導(dǎo)航方法杈抢，例如方法lowEntry、floorEntry仑性、ceilingEntry等惶楼，如果不存在這樣的鍵，則返回null
- AbstractMap類：提供了一個(gè)Map骨架的實(shí)現(xiàn),盡量減少了實(shí)現(xiàn)Map接口所需要的工作量
- HashMap類：HashMap是實(shí)現(xiàn)了Map接口的key-value集合诊杆，實(shí)現(xiàn)了所有map的操作歼捐，允許key和value為null,它相當(dāng)于Hashtable，與之存在的區(qū)別是hashMap不是線程安全的晨汹，HashMap允許null值豹储。
- TreeMap類：TreeMap是基于紅黑樹的實(shí)現(xiàn)，也是記錄了key-value的映射關(guān)系淘这，該映射根據(jù)key的自然排序進(jìn)行排序或者根據(jù)構(gòu)造方法中傳入的比較器進(jìn)行排序剥扣，也就是說TreeMap是有序的key-value集合
- Hashtable類：它是類似與HashMap的key-value的哈希表，不允許key-value為NULL值铝穷，另外一點(diǎn)值得注意的是Hashtable是線程安全的
- Serializable接口：實(shí)現(xiàn)了該接口標(biāo)識了類可以被序列化和反序列化钠怯，具體的 查詢序列化詳解
- Cloneable接口：實(shí)現(xiàn)了該接口的類可以顯示的調(diào)用Object.clone()方法，合法的對該類實(shí)例進(jìn)行字段復(fù)制曙聂，如果沒有實(shí)現(xiàn)Cloneable接口的實(shí)例上調(diào)用Obejct.clone()方法晦炊，會(huì)拋出CloneNotSupportException異常。正常情況下，實(shí)現(xiàn)了Cloneable接口的類會(huì)以公共方法重寫Object.clone()
3.比較
雖然HashMap断国、Hashtable贤姆、TreeMap這三個(gè)都是Map接口的實(shí)現(xiàn)，其內(nèi)部實(shí)現(xiàn)及性能等還是存在區(qū)別稳衬，下面將從區(qū)別及性能兩個(gè)方面去分析庐氮。
3.1 區(qū)別
3.1.1 基本
- HashMap：初始化容量為16，擴(kuò)容每次為2*oldCap,key-value可以為NULL值
- Hashtable：初始化容量為11宋彼，擴(kuò)容每次為2*oldCap+1,key-value不可以為NULL值
- TreeMap：初始化容量為0弄砍，內(nèi)部是紅黑樹結(jié)構(gòu)，不存在hash沖突的情況输涕，不存在擴(kuò)容的操作,key-value不可以為NULL值
3.1.2 實(shí)現(xiàn)
- HashMap：實(shí)現(xiàn)了Map接口音婶，繼承了AbstractMap類
- Hashtable：實(shí)現(xiàn)了Map接口，繼承了AbstractMap類
- TreeMap：由于TreeMap是有序的莱坎，所以其除了實(shí)現(xiàn)了Map接口衣式，還實(shí)現(xiàn)了SortedMap、NavigableMap接口
3.1.3 內(nèi)部原理
- HashMap:HashMap是散列表實(shí)現(xiàn)檐什，內(nèi)部是數(shù)組+鏈表或者紅黑樹的結(jié)構(gòu)
- Hashtable：Hashtable也是散列表實(shí)現(xiàn)碴卧，內(nèi)部是數(shù)組+鏈表的結(jié)構(gòu)
- TreeMap：TreeMap內(nèi)部是紅黑樹的結(jié)構(gòu)
3.1.4 線程安全
- HashMap：不是線程安全的，其實(shí)通過Map m = Collections.synchronizeMap(hashMap)的方式也可以使得HashMap變成線程安全的乃正，但是這樣做對程序的性能可能是噩夢住册，在后面會(huì)介紹ConcurrentHashMap，建議在多線程的情況下可以使用ConcurrentHashMap替換HashMap.
- Hashtable：是線程安全的瓮具，內(nèi)部方法使用關(guān)鍵字synchronized修飾
- TreeMap：不是線程安全的
3.2 性能
按照如下代碼對HashMap荧飞、Hashtable、TreeMap的性能進(jìn)行測試
public class HashMapProgress {
//定義用于測試的HashMap
private static HashMap<Integer,Integer> hashMap = new HashMap<>();
//定義用于測試的Hashtable
private static Hashtable<Integer,Integer> hashtable = new Hashtable<>();
//定義用于測試的TreeMap
private static TreeMap<Integer,Integer> treeMap = new TreeMap<>();
/**
* 添加元素的方法
* @param map 對應(yīng)的map
* @param count 添加個(gè)數(shù)
*/
public static void addEntry(Map<Integer,Integer> map, int count){
Long startTime = System.currentTimeMillis();
if (count <= 0){
return;
}
for (int i = 0; i < count; i++) {
map.put(i,i);
}
Long endTime = System.currentTimeMillis();
System.out.println("添加(" + count + ")個(gè)元素使用時(shí)間:" + (endTime - startTime) + "s");
}
/**
* 獲取元素的方法
* @param map
* @param count
*/
public static void getEntry(Map<Integer,Integer> map, int count){
Long startTime = System.currentTimeMillis();
if (count <= 0){
return;
}
for (int i = 0; i < count; i++) {
map.get(i);
}
Long endTime = System.currentTimeMillis();
System.out.println("獲取(" + count + ")個(gè)元素使用時(shí)間:" + (endTime - startTime) + "s");
}
public static void main(String[] args){
System.out.println("-------HashMap測試開始-----");
addEntry(hashMap,1000000);
getEntry(hashMap,1000000);
System.out.println("-------HashMap測試結(jié)束-----");
System.out.println("-------Hashtable測試開始-----");
addEntry(hashtable,1000000);
getEntry(hashtable,1000000);
System.out.println("-------Hashtable測試結(jié)束-----");
System.out.println("-------TreeMap測試開始-----");
addEntry(treeMap,1000000);
getEntry(treeMap,1000000);
System.out.println("-------TreeMap測試結(jié)束-----");
}
}
分別測試了100000,1000000,10000000個(gè)數(shù)據(jù)的情況名党，測試結(jié)果如下所示：
| 數(shù)據(jù)量 | HashMap | Hashtable | TreeMap |
|---|---|---|---|
| 100000 | 插入用時(shí)：18s 查詢用時(shí)：9s | 插入用時(shí)：14s 查詢用時(shí)：5s | 插入用時(shí)：33s 查詢用時(shí)：17s |
| 1000000 | 插入用時(shí)：98s 查詢用時(shí)：20s | 插入用時(shí)：625s 查詢用時(shí)：31s | 插入用時(shí)：242s 查詢用時(shí)： 145s |
| 10000000 | 插入用時(shí)：9773s 查詢用時(shí)：811s | 插入用時(shí)：15055s 查詢用時(shí)：3369s | 插入用時(shí)：22354s 查詢用時(shí)： 3889s |
通過上表可以看出隨著數(shù)據(jù)量的增加叹阔，時(shí)間變化差異還是很大的，而在單線程的情況下還是盡量使用HashMap传睹，相對于Hashtable耳幢、TreeMap性能更好，而針對特定的情況需視情況而論欧啤。
4.總結(jié)
本文主要是對前面介紹的HashMap睛藻、Hashtable、TreeMap這些Map接口實(shí)現(xiàn)類的一個(gè)總結(jié)堂油，主要分析這些實(shí)現(xiàn)類的一些特點(diǎn)以及存在的差異修档，最后想說的是針對不同的情況可以選擇不同的Map進(jìn)行編碼碧绞，如有問題府框，望指正。
