JCF中的Map集合

JCF中的Map集合和Set集合之間存在非常密切的關(guān)聯(lián)關(guān)系，從相應(yīng)集合的命名可以看出來，如HashMap集合和HashSet集合、TreeMap集合和TreeSet集合、LinkedHashMap集合和LinkedHashSet集合、ConcurrentSkipListSet集合和ConcurrentSkipListMap集合。因此，如果搞清楚了JCF中的Map集合結(jié)構(gòu)，就基本搞清楚了JCF中的Set集合結(jié)構(gòu)。本書首先介紹JCF中具有代表性的Map集合，然后在此基礎(chǔ)上針對性地介紹Set集合。

Map集合概述

Map 集 合 屬 于 JCF 的 知 識 范 疇 ， 但 是 代 表 Map 集 合 的 頂 級 接 口java.util.Map并沒有繼承JCF的頂級接口java.util.Collection。這是因為Map集合結(jié)構(gòu)屬于映射式結(jié)構(gòu)，即一個Key鍵對應(yīng)一個Value值（簡稱K-V鍵值對），并且同一個集合中不能出現(xiàn)兩個相同的Key鍵信息。

JCF原生的一些重要的Map集合的主要繼承體系如圖3-1所示。

本節(jié)會重點介紹TreeMap集合、HashMap集合和LinkedHashMap集合，其中TreeMap集合是基于紅黑樹結(jié)構(gòu)構(gòu)造的，HashMap集合和LinkedHashMap集合是基于數(shù)組+鏈表+紅黑樹的復(fù)合結(jié)構(gòu)構(gòu)造的，這兩種集合的區(qū)別僅體現(xiàn)在LinkedHashMap集合中增加了一個虛擬的鏈表結(jié)構(gòu)。ConcurrentHashMap集合和ConcurrentSkipListMap集合也是Map集合體系中重要的線程安全的集合，本書會在介紹完JUC的必要知識后，介紹ConcurrentHashMap集合的相關(guān)結(jié)構(gòu)。

K-V鍵值對節(jié)點定義——Entry

Map集合中存儲的是K-V鍵值對節(jié)點，即用一個Key鍵信息和一個Value值信息映射關(guān)聯(lián)后的對象描述。Map集合中可以有成千上萬個K-V鍵值對節(jié)點，每一個K-V鍵值對都使用實現(xiàn)了Map.Entry<K,V>接口的類的對象進(jìn)行描述——也就是說，一個Map集合中可以有成千上萬個Map.Entry<K,V>接口的實例化對象，如圖3-2所示。

Map.Entry<K, V>接口的主要源碼如下。

實際上，從JDK 1.8開始，Map.Entry<K, V>接口中增加了一些其他定義，這里暫時不予介紹。在一般情況下，實現(xiàn)了Map.Entry<K, V>接口的具體類，都會根據(jù)自己的結(jié)構(gòu)特點實現(xiàn)Map.Entry<K, V>接口中的方法。例如，AbstractMap類中的AbstractMap.SimpleEntry類實現(xiàn)了Map.Entry<K, V>接口，HashMap類中的HashMap.Node類實現(xiàn)Map.Entry<K, V>接口，TreeMap類中的TreeMap.Entry類實現(xiàn)Map.Entry<K, V>接口，這些Map.Entry<K, V>接口的具體實現(xiàn)類，都根據(jù)自己存儲K-V鍵值對節(jié)點的特性做了不同的擴(kuò)展或調(diào)整。

下面以TreeMap集合為例，看一下TreeMap.Entry<K, V>類的定義（TreeMap集合中對K-V鍵值對節(jié)點的定義），源碼如下。

使用K-V鍵值對節(jié)點存儲數(shù)據(jù)對象的java.util.TreeMap集合，內(nèi)部所有的K-V鍵值對節(jié)點構(gòu)成一棵紅黑樹。也就是說，代表K-V鍵值對節(jié)點的TreeMap.Entry對象需要記錄當(dāng)前樹節(jié)點的雙親節(jié)點（父節(jié)點）、左兒子節(jié)點、右兒子節(jié)點及當(dāng)前樹節(jié)點的顏色。