JCF中的Map集合

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

Map集合概述

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

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

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

K-V鍵值對(duì)節(jié)點(diǎn)定義——Entry

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

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

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

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

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