Map

我們都知道 Map 是鍵值對(duì)關(guān)系的集合，并且鍵唯一，鍵一對(duì)一對(duì)應(yīng)值。

關(guān)于 Map 的定義，大概就這些吧，API 文檔的定義也是醬紫。

照慣例，我們來(lái)看類(lèi)結(jié)構(gòu)圖吧~~

都是一些行為控制的方法，用過(guò) Map 集合的我們都熟悉這些方法，我就不做過(guò)多的贅述了，這里我們重點(diǎn)來(lái)看看嵌套類(lèi) Map.Entry

Map.Entry<K,V>

定義：映射項(xiàng)（鍵-值對(duì)）。Map.entrySet 方法返回映射的 collection 視圖，其中的元素屬于此類(lèi)。獲得映射項(xiàng)引用的唯一 方法是通過(guò)此 collection 視圖的迭代器來(lái)實(shí)現(xiàn)。這些 Map.Entry 對(duì)象僅 在迭代期間有效；更確切地講，如果在迭代器返回項(xiàng)之后修改了底層映射，則某些映射項(xiàng)的行為是不確定的，除了通過(guò) setValue 在映射項(xiàng)上執(zhí)行操作之外。

這里我們可以看到 Map 的泛型K,V也給 Map.Entry用了，然后根據(jù)定義，我們可以大膽的猜測(cè)這個(gè) Entry 就是用來(lái)存放 K,V 等關(guān)鍵信息的實(shí)體類(lèi)。

我們來(lái)看看 Map.Entry 定義的方法

這里的5個(gè)方法，除了 hashCode 之外，都能顧名思義。那么問(wèn)題來(lái)了，我們這里的實(shí)體類(lèi)為什么要引入 hashCode 的概念呢~~這里我們要先學(xué)習(xí)一種數(shù)據(jù)結(jié)構(gòu)---散列表。

Map 的抽象實(shí)現(xiàn)類(lèi) AbstractMap

此類(lèi)提供 Map 接口的骨干實(shí)現(xiàn)，以最大限度地減少實(shí)現(xiàn)此接口所需的工作。

要實(shí)現(xiàn)不可修改的映射，編程人員只需擴(kuò)展此類(lèi)并提供 entrySet 方法的實(shí)現(xiàn)即可，該方法將返回映射的映射關(guān)系 set 視圖。通常，返回的 set 將依次在 AbstractSet 上實(shí)現(xiàn)。此 set 不支持 add 或 remove 方法，其迭代器也不支持 remove 方法。

要實(shí)現(xiàn)可修改的映射，編程人員必須另外重寫(xiě)此類(lèi)的 put 方法（否則將拋出 UnsupportedOperationException），entrySet().iterator() 返回的迭代器也必須另外實(shí)現(xiàn)其 remove 方法。

按照 Map 接口規(guī)范中的建議，編程人員通常應(yīng)該提供一個(gè) void（無(wú)參數(shù)）構(gòu)造方法和 map 構(gòu)造方法。

此類(lèi)中每個(gè)非抽象方法的文檔詳細(xì)描述了其實(shí)現(xiàn)。如果要實(shí)現(xiàn)的映射允許更有效的實(shí)現(xiàn)，則可以重寫(xiě)所有這些方法。

HashMap

這個(gè)是最正宗的基于哈希表的 Map 接口實(shí)現(xiàn)。此實(shí)現(xiàn)提供所有可選的映射操作，并允許使用 null 值和 null 鍵。

HashMap 的實(shí)例有兩個(gè)參數(shù)影響其性能：初始容量 和加載因子。容量 是哈希表中bucketIndex（桶）的數(shù)量，初始容量只是哈希表在創(chuàng)建時(shí)的容量。加載因子 是哈希表在其容量自動(dòng)增加之前可以達(dá)到多滿(mǎn)的一種尺度。當(dāng)哈希表中的條目數(shù)超出了加載因子與當(dāng)前容量的乘積時(shí)，則要對(duì)該哈希表進(jìn)行 rehash 操作（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），從而哈希表將具有大約兩倍的桶數(shù)。

通常，默認(rèn)加載因子 (0.75) 在時(shí)間和空間成本上尋求一種折衷。加載因子過(guò)高雖然減少了空間開(kāi)銷(xiāo)，但同時(shí)也增加了查詢(xún)成本（在大多數(shù) HashMap 類(lèi)的操作中，包括 get 和 put 操作，都反映了這一點(diǎn)）。在設(shè)置初始容量時(shí)應(yīng)該考慮到映射中所需的條目數(shù)及其加載因子，以便最大限度地減少 rehash 操作次數(shù)。如果初始容量大于最大條目數(shù)除以加載因子，則不會(huì)發(fā)生 rehash 操作。

注意，此實(shí)現(xiàn)不是同步的。如果多個(gè)線(xiàn)程同時(shí)訪(fǎng)問(wèn)一個(gè)哈希映射，而其中至少一個(gè)線(xiàn)程從結(jié)構(gòu)上修改了該映射，則它必須 保持外部同步。（結(jié)構(gòu)上的修改是指添加或刪除一個(gè)或多個(gè)映射關(guān)系的任何操作；僅改變與實(shí)例已經(jīng)包含的鍵關(guān)聯(lián)的值不是結(jié)構(gòu)上的修改。）這一般通過(guò)對(duì)自然封裝該映射的對(duì)象進(jìn)行同步操作來(lái)完成。如果不存在這樣的對(duì)象，則應(yīng)該使用 Collections.synchronizedMap 方法來(lái)“包裝”該映射。最好在創(chuàng)建時(shí)完成這一操作，以防止對(duì)映射進(jìn)行意外的非同步訪(fǎng)問(wèn)，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));

我們先了解以下三個(gè)名詞，如果還不懂的話(huà)也沒(méi)事，我們一起手?jǐn)]一個(gè) HashMap就是了。

散列表

散列表，又名哈希表（Hash table）,是根據(jù)關(guān)鍵碼值（Key value）而進(jìn)行訪(fǎng)問(wèn)的數(shù)據(jù)結(jié)構(gòu)，也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪(fǎng)問(wèn)記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表

給定表M，存在函數(shù)f(key)，對(duì)任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址，則稱(chēng)表M為哈希(Hash）表，函數(shù)f(key)為哈希(Hash) 函數(shù)。

說(shuō)起來(lái)可能有點(diǎn)抽象，我給大家舉個(gè)栗子吧~~
對(duì)于一個(gè)具有 n 個(gè)元素的數(shù)組，我們需要找到其中某一個(gè)值的時(shí)間復(fù)雜度是 O(n)?，F(xiàn)在我們使用散列表來(lái)實(shí)現(xiàn)，要獲取一個(gè)元素“vaule”,我們可以通過(guò)該元素的 Key 值“key”來(lái)獲取“value”在數(shù)組中存放的位置，然后直接獲取到我們需要的元素，則獲取的時(shí)間復(fù)雜度是 O(1)。那么問(wèn)題是，怎么通過(guò)“key”來(lái)獲取呢，上面的定義有說(shuō)到。把關(guān)鍵詞“key”代入到哈希函數(shù)里面計(jì)算，計(jì)算的結(jié)果就是“value”存放的位置。key 是個(gè)泛型，要使不同類(lèi)型的數(shù)據(jù)都能帶入到哈希函數(shù)里面進(jìn)行計(jì)算，這里我們用的是對(duì)象的 hashCode 值，hashCode 值的定義這里不過(guò)多贅述，大家記得 hashCode 是 Object 的方法即可。

看到這里如果還不明白的話(huà)，那我就只能講自己的理解了：就是通過(guò)哈希函數(shù)計(jì)算一個(gè) Key 的 hash 值，得到一個(gè)bucketIndex(可以理解為數(shù)組角標(biāo))，把 Value 存放到這個(gè)bucketIndex對(duì)應(yīng)的位置。下次再取這個(gè) Vaule 的時(shí)候只需把 key 的 hash代入到哈希函數(shù)里面進(jìn)行計(jì)算得到 Value 的位置即可。

鍵唯一

上一篇我們分析 HashSet 源碼怎么實(shí)現(xiàn)集合元素不重復(fù)的時(shí)候，我挖了一個(gè)坑，現(xiàn)在來(lái)把這個(gè)坑給填上吧。

要比較兩個(gè)元素是否相等，這個(gè)在 java 里面似乎是一個(gè)比較簡(jiǎn)單的問(wèn)題，但是要把==，equals 和 hashcode 牽扯進(jìn)來(lái)，好像又有點(diǎn)講不清楚。

• 首先我們來(lái)區(qū)分“==”和 equals 的區(qū)別

"=="在比較基本數(shù)據(jù)類(lèi)型的時(shí)候比較的是值是否相等，在比較對(duì)象變量的時(shí)候比較的是兩個(gè)變量是否指向同一個(gè)對(duì)象。equals Object 的方法，用于比較兩個(gè)對(duì)象內(nèi)容是否相等。默認(rèn)是用==做比較，如果重寫(xiě)則單獨(dú)處理。

• hashCode 的約定
  • 在 Java 應(yīng)用程序執(zhí)行期間，在對(duì)同一對(duì)象多次調(diào)用 hashCode 方法時(shí)，必須一致地返回相同的整數(shù)，前提是將對(duì)象進(jìn)行 equals 比較時(shí)所用的信息沒(méi)有被修改。從某一應(yīng)用程序的一次執(zhí)行到同一應(yīng)用程序的另一次執(zhí)行，該整數(shù)無(wú)需保持一致。
  • 如果根據(jù) equals(Object) 方法，兩個(gè)對(duì)象是相等的，那么對(duì)這兩個(gè)對(duì)象中的每個(gè)對(duì)象調(diào)用 hashCode 方法都必須生成相同的整數(shù)結(jié)果。
  • 如果根據(jù) equals(java.lang.Object) 方法，兩個(gè)對(duì)象不相等，那么對(duì)這兩個(gè)對(duì)象中的任一對(duì)象上調(diào)用 hashCode 方法不 要求一定生成不同的整數(shù)結(jié)果。但是，程序員應(yīng)該意識(shí)到，為不相等的對(duì)象生成不同整數(shù)結(jié)果可以提高哈希表的性能。

好，看完這些，我們可以知道，如果兩個(gè)對(duì)象相等，那么hashCode 的值必然相等；如果兩個(gè)對(duì)象不相等，hashCode 的值也有可能相等，只是兩個(gè)不相等的對(duì)象 hashCode 值相等的話(huà)，哈希表的性能會(huì)下降。

好了，看到這里我們可以根據(jù)上面的結(jié)論，先獲取是否有 hash 相同的 key，如果有，再執(zhí)行==和 equals 操作比較，如果沒(méi)有。。。那就算鍵唯一。

鍵沖突

剛剛我們?cè)诒ＷC鍵唯一的時(shí)候有一個(gè)這樣的問(wèn)題不知道大家注意到了沒(méi)，就是不同的對(duì)象，其 hashCode的值是有可能相等的，那么當(dāng)兩個(gè)不同的 key 存入 map，而正好其key 的 hash 值相等，那該怎么辦？

這個(gè)其實(shí)是屬于散列表的問(wèn)題，但是散列表牽扯到的東西太多，所以剛剛我沒(méi)有講。但是我們剛剛在保持鍵唯一的時(shí)候又碰到了這個(gè)問(wèn)題，那么我們來(lái)簡(jiǎn)單講一下吧。

剛剛我們?cè)谥v散列表數(shù)據(jù)結(jié)構(gòu)的時(shí)候已經(jīng)說(shuō)了，其實(shí)散列表的數(shù)據(jù)存儲(chǔ)就是一個(gè)數(shù)組，哈希函數(shù)根據(jù) key計(jì)算出來(lái)的 hash 值就是 value 的存放位置，而 value 則是一個(gè)Map.Entry 的具體實(shí)現(xiàn)類(lèi)，Java 的 HashMap 在這里用了“拉鏈法”來(lái)鍵沖突。什么是拉鏈法呢？就是讓 value 變成一個(gè)鏈表，添加一個(gè)指向下一個(gè)元素的引用。

也就是說(shuō)，map 的數(shù)據(jù)存儲(chǔ)其實(shí)就是一個(gè)數(shù)組，當(dāng)我們插入一組 K,V 的時(shí)候，用 K 的 hashcode 經(jīng)過(guò) hash 函數(shù)計(jì)算得出 V 存放的位置 bucketIndex，然后如果 數(shù)組[bucketIndex]沒(méi)有元素，則創(chuàng)建 Entry 賦值給 數(shù)組[bucketIndex]。如果有1或多個(gè)元素（多個(gè)元素以鏈表的形式），則遍歷比較各組元素的key 是否和插入 key 相等，如果相等則覆蓋 value，否則new 一個(gè) Entry 插入到表頭。

HashTable

繼承自 Dictionary 類(lèi)，實(shí)現(xiàn)了 Map 接口。

Dictionary 類(lèi)是任何可將鍵映射到相應(yīng)值的類(lèi)（如 Hashtable）的抽象父類(lèi)。每個(gè)鍵和每個(gè)值都是一個(gè)對(duì)象。在任何一個(gè) Dictionary 對(duì)象中，每個(gè)鍵至多與一個(gè)值相關(guān)聯(lián)。給定一個(gè) Dictionary 和一個(gè)鍵，就可以查找所關(guān)聯(lián)的元素。任何非 null 對(duì)象都可以用作鍵或值。

基本上不會(huì)再使用的類(lèi)，K、V 都不能為 null，支持同步算是唯一的優(yōu)點(diǎn)了吧。但是 Java 推薦我們使用 Collections.synchronized*** 對(duì)各種集合進(jìn)行了同步的封裝，所以基本廢棄。

TreeMap

我們先來(lái)看看類(lèi)注釋說(shuō)明~

A Red-Black tree based NavigableMap implementation. The map is sorted according to the Comparable natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

TreeMap 是 Map 接口基于紅黑樹(shù)的實(shí)現(xiàn)，鍵值對(duì)是有序的。TreeMap 的排序方式基于Key的Comparable 接口的比較，或者在構(gòu)造方法中傳入一個(gè)Comparator.

This implementation provides guaranteed log(n) time cost for the {@code containsKey}, {@code get}, {@code put} and {@code remove} operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's <em>Introduction to Algorithms</em>.

TreeMap提供時(shí)間復(fù)雜度為log(n)的containsKey，get，put ，remove操作。

和 HashMap 的區(qū)別？

• TreeMap的元素是有序的，HashMap的元素是無(wú)序的。
• TreeMap的鍵值不能為 null。

大致的特性就這些吧，關(guān)鍵就是掌握紅黑樹(shù)。

說(shuō)回來(lái)，TreeMap 就是Java 的紅黑樹(shù)實(shí)現(xiàn)啊~~

紅黑樹(shù)

紅黑樹(shù)是一種自平衡二叉查找樹(shù)，是一種比較特別的數(shù)據(jù)結(jié)構(gòu)。

紅黑樹(shù)和 AVL 樹(shù)類(lèi)似，都是在進(jìn)行插入和刪除操作保持二叉查找樹(shù)的平衡，從而活得較高的查找性能。

紅黑樹(shù)雖然負(fù)責(zé)，但是它最壞的運(yùn)行時(shí)間也是非常良好的，并且在實(shí)踐中是高效的，它可以在 O(lon n)時(shí)間內(nèi)做查找、插入和刪除，這里的 n 指樹(shù)種元素的數(shù)目。

額、如果對(duì)樹(shù)以及二叉樹(shù)不了解的同學(xué)可以跳過(guò)這一段。

五大特性

• 節(jié)點(diǎn)是紅色或者黑色
• 根是黑色
• 所有的葉子都是黑色的（葉子是 NIL 節(jié)點(diǎn)）
• 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
• 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑 都包含相同數(shù)目的黑色節(jié)點(diǎn)。

我們來(lái)對(duì)著下面這張圖來(lái)理解一下這五大特征。

1.節(jié)點(diǎn)都是紅色或者黑色——沒(méi)毛病
2.根節(jié)點(diǎn)是黑色——沒(méi)毛病
3.所有的葉子節(jié)點(diǎn)都是黑色——可以理解成最外層的節(jié)點(diǎn)都會(huì)有一個(gè) NIL 的黑色節(jié)點(diǎn)，實(shí)際數(shù)據(jù)結(jié)構(gòu)中就是 null
4.每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色——注意不能反過(guò)來(lái)，這是為了保證不會(huì)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)。
5.保證黑色節(jié)點(diǎn)數(shù)相同，也就是保證了從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)最短的路徑*2>=最長(zhǎng)的路徑

樹(shù)的旋轉(zhuǎn)
當(dāng)我們?cè)诙鸭t黑樹(shù)進(jìn)行插入和刪除等操作時(shí)，對(duì)樹(shù)做了修改，那么可能會(huì)違背紅黑樹(shù)的性質(zhì)。

為了保持紅黑樹(shù)的性質(zhì)，我們可以通過(guò)對(duì)樹(shù)進(jìn)行旋轉(zhuǎn)操作，即修改樹(shù)種某些節(jié)點(diǎn)的顏色及指針結(jié)構(gòu)，已達(dá)到對(duì)紅黑樹(shù)進(jìn)行插入、刪除節(jié)點(diǎn)等操作時(shí)，紅黑樹(shù)依然能保持它特有的性質(zhì)。

說(shuō)白了，就是增刪節(jié)點(diǎn)的時(shí)候會(huì)破壞樹(shù)的性質(zhì)，所以通過(guò)旋轉(zhuǎn)來(lái)保持。

怎樣旋轉(zhuǎn)？為什么旋轉(zhuǎn)可以保持紅黑樹(shù)性質(zhì)？
這個(gè)~~旋轉(zhuǎn)是一門(mén)玄學(xué)，一般看運(yùn)氣才能正確的做出旋轉(zhuǎn)操作。
至于為什么旋轉(zhuǎn)可以保持樹(shù)的性質(zhì)，這個(gè)……你可以暫且把這個(gè)旋轉(zhuǎn)理解成是一個(gè)“定理”吧。

定理：是經(jīng)過(guò)受邏輯限制的證明為真的陳述

好了，別糾結(jié)了，你記住旋轉(zhuǎn)可以保持樹(shù)的性質(zhì)就行了。

樹(shù)的插入
樹(shù)的插入很簡(jiǎn)單，只能插入到葉子節(jié)點(diǎn)上（如果插入的 key 在樹(shù)上已存在，則覆蓋 Value），根據(jù)左節(jié)點(diǎn)小又節(jié)點(diǎn)大的性質(zhì)，找到對(duì)應(yīng)的葉節(jié)點(diǎn)插入即可，注意插入的節(jié)點(diǎn)默認(rèn)只能是紅色。如果插入的葉子節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，則違背了特性4，這時(shí)候就需要通過(guò)旋轉(zhuǎn)來(lái)穩(wěn)定樹(shù)的性質(zhì)。

怎樣旋轉(zhuǎn)

旋轉(zhuǎn)分了左右旋轉(zhuǎn)，左旋操作有如下幾步
1.把跟節(jié)點(diǎn) a 的右孩子 c 作為根節(jié)點(diǎn)
2.把舊的根節(jié)點(diǎn) a 作為新的根節(jié)點(diǎn) c 的左孩子
3.把新的跟節(jié)點(diǎn) c 的左孩子作為 a 節(jié)點(diǎn)的右孩子

右旋就簡(jiǎn)單了，把上面步驟的左右對(duì)調(diào)就行了。

好了，旋轉(zhuǎn)就這樣，很簡(jiǎn)單，但是一定要用紙和筆在紙上畫(huà)一畫(huà)才能掌握哦~~

什么時(shí)候旋轉(zhuǎn)？做什么旋轉(zhuǎn)？

mmp，這個(gè)問(wèn)題我操蛋了好久好久，我怎么知道怎樣旋轉(zhuǎn)。去搜別人寫(xiě)的 blog 。。。。。

然后搜到了各種圖解，看了幾篇還是半懂不懂的，索性自己去分析源碼。。。。

在 Treemap 里面 put 插入了一個(gè)節(jié)點(diǎn)之后有個(gè)fixAfterInsertion()操作。看名字我們就知道是插入后修復(fù)。

源碼就不帶著大家一起讀了，后面我手?jǐn)] RBTree的時(shí)候會(huì)一步一步講解。

我用文字表述一下fixAfterInsertion(x)里面的邏輯。

首先把 x 節(jié)點(diǎn)設(shè)為紅色，這里的 x 節(jié)點(diǎn)就是新插入的節(jié)點(diǎn)。

當(dāng) x 節(jié)點(diǎn)不為空，x 節(jié)點(diǎn)不為跟節(jié)點(diǎn)，x 的父節(jié)點(diǎn)是紅色的時(shí)候，while 以下操作。

敲黑板，這里邏輯比較復(fù)雜，里面各種 if else 邏輯，注意了?。?！

為了避免有人說(shuō)我嚇唬小朋友，我還是貼一下代碼吧~~

while (x != null && x != root && x.parent.color == RED) {
        if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == rightOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateLeft(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateRight(parentOf(parentOf(x)));
            }
        } else {
            TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));
            if (colorOf(y) == RED) {
                setColor(parentOf(x), BLACK);
                setColor(y, BLACK);
                setColor(parentOf(parentOf(x)), RED);
                x = parentOf(parentOf(x));
            } else {
                if (x == leftOf(parentOf(x))) {
                    x = parentOf(x);
                    rotateRight(x);
                }
                setColor(parentOf(x), BLACK);
                setColor(parentOf(parentOf(x)), RED);
                rotateLeft(parentOf(parentOf(x)));
            }
        }
    }

邏輯還是蠻復(fù)雜的，其實(shí)總結(jié)清楚了之后，就只有以下三種情況。

• case 1：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)（這個(gè)名詞能理解吧，不能理解我也沒(méi)辦法了）也是紅色。
  1. 將父節(jié)點(diǎn)設(shè)為黑色
  2. 將叔叔節(jié)點(diǎn)設(shè)為黑色
  3. 將祖父節(jié)點(diǎn)設(shè)為紅色
  4. 將祖父節(jié)點(diǎn)設(shè)為當(dāng)前節(jié)點(diǎn)， case 結(jié)束，可能會(huì)重新走第二輪 while
• case 2：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子
  1. 將父節(jié)點(diǎn)作為新的當(dāng)前節(jié)點(diǎn)
  2. 以新的當(dāng)前節(jié)點(diǎn)作為支點(diǎn)左旋
• case 3：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色，叔叔節(jié)點(diǎn)是黑色，且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子
  1. 將父節(jié)點(diǎn)設(shè)為黑色
  2. 將祖父節(jié)點(diǎn)設(shè)為紅色
  3. 以祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
• case 4：啥？不是只有3種情況么？當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色
  1. 不用修復(fù)，樹(shù)穩(wěn)定。

樹(shù)的刪除操作
這他喵的也是一段很鬧騰的代碼。

刪除就是根據(jù) key 找到對(duì)應(yīng)的節(jié)點(diǎn)，并執(zhí)行刪除操作，刪除之后為了保證樹(shù)的穩(wěn)定性，需要根據(jù)節(jié)點(diǎn)的一些屬性進(jìn)行調(diào)整。

這里主要處理兩個(gè)問(wèn)題：

• 如何刪除
• 刪除后如何調(diào)整

刪除節(jié)點(diǎn)分三種情況
1.沒(méi)有兒子的節(jié)點(diǎn)
直接刪除即可
2.有一個(gè)兒子的節(jié)點(diǎn)，把父節(jié)點(diǎn)的兒子指針指向自己的兒子，再刪除即可（就像鏈表中刪除一個(gè)元素）
3.有兩個(gè)兒子的節(jié)點(diǎn)，首先找到右兒子最左邊的葉節(jié)點(diǎn)或者左兒子最右邊的葉子節(jié)點(diǎn)a，再把 a 賦值給自己，然后刪除 a 節(jié)點(diǎn)。

這個(gè)比較容易，應(yīng)該能理解吧。。。。。。理解不了自己去畫(huà)畫(huà)圖~

刪除后如何修復(fù)，我們?cè)賮?lái)根據(jù)剛剛刪除節(jié)點(diǎn)的三種情況分析

1.1 沒(méi)有兒子的節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)為紅色。直接刪除即可，不影響樹(shù)的性質(zhì)
1.2 沒(méi)有兒子的節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)為黑色。執(zhí)行刪除后修復(fù)操作，傳參是被刪除的節(jié)點(diǎn)
2.1 有一個(gè)兒子節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)為紅色。直接刪除即可，不影響樹(shù)的性質(zhì)
2.2 有一個(gè)兒子節(jié)點(diǎn)，且當(dāng)前節(jié)點(diǎn)為黑色。執(zhí)行刪除后修復(fù)操作，傳參是被刪除節(jié)點(diǎn)的子節(jié)點(diǎn)
3.1 有兩個(gè)兒子節(jié)點(diǎn)，且找到的后備葉子節(jié)點(diǎn)是紅色。直接刪除即可，不影響樹(shù)的性質(zhì)
3.2 有兩個(gè)兒子節(jié)點(diǎn)，且找到的后備葉子節(jié)點(diǎn)是黑色。執(zhí)行刪除后修復(fù)操作，傳參是被刪除的葉子節(jié)點(diǎn)

好了，刪除的邏輯我們看完了，反正就是傳一個(gè)指定的節(jié)點(diǎn) x 到fixAfterDeletion(x)到這個(gè)方法里面執(zhí)行修復(fù)操作。

接下來(lái)，我們就來(lái)看看怎樣修復(fù)吧~
已知修復(fù)是根據(jù)傳參的節(jié)點(diǎn)來(lái)判斷的，然后里面也有很多 if else 等語(yǔ)句，邏輯和插入修復(fù)差不多，也很復(fù)雜。這里我先給大家總結(jié)一下方法里面的邏輯 case

• case 1：x 的兄弟節(jié)點(diǎn)是紅色
  1. 將 x 的兄弟節(jié)點(diǎn)設(shè)為黑色
  2. 將 x 的父節(jié)點(diǎn)設(shè)為紅色
  3. 以 x 的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
  4. 后續(xù)邏輯為 case 2、3、4隨機(jī)一種
• case 2：x 的兄弟節(jié)點(diǎn)是黑色，且兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
  1. 將 x 的兄弟節(jié)點(diǎn)設(shè)為紅色
  2. x 指向 x 的父節(jié)點(diǎn)，繼續(xù) while 循環(huán)
• case 3：x 的兄弟節(jié)點(diǎn)是黑色，且兄弟的左孩子是紅色、右孩子是黑色
  1. 將 x 的兄弟節(jié)點(diǎn)設(shè)為紅色
  2. 將 x 的兄弟節(jié)點(diǎn)左孩子設(shè)為黑色
  3. 以 x 的兄弟節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋
  4. 執(zhí)行 case 4
• case 4：x 的兄弟節(jié)點(diǎn)是黑色，且兄弟的左孩子是黑色、右孩子是紅色
  1. 將 x 的父節(jié)點(diǎn)顏色賦值給 x 的兄弟節(jié)點(diǎn)顏色
  2. 將 x 的父節(jié)點(diǎn)設(shè)為黑色
  3. 將 x 的右孩子設(shè)為黑色
  4. 以 x 的父節(jié)點(diǎn)為支點(diǎn)進(jìn)行左旋
• case 5：如果 x 是左孩子，以上4個(gè) case 的操作均沒(méi)毛病，如果 x 的右孩子，以上左右取反。

    private void fixAfterDeletion(Entry<K,V> x) {  
    // 刪除節(jié)點(diǎn)需要一直迭代，知道 直到 x 不是根節(jié)點(diǎn)，且 x 的顏色是黑色  
    while (x != root && colorOf(x) == BLACK) {  
        if (x == leftOf(parentOf(x))) {      //若X節(jié)點(diǎn)為左節(jié)點(diǎn)  
            //獲取其兄弟節(jié)點(diǎn)  
            Entry<K,V> sib = rightOf(parentOf(x));  

            /* 
             * 如果兄弟節(jié)點(diǎn)為紅色----（case 1） 
             */  
            if (colorOf(sib) == RED) {       
                setColor(sib, BLACK);       
                setColor(parentOf(x), RED);    
                rotateLeft(parentOf(x));  
                sib = rightOf(parentOf(x));  
            }  

            /* 
             * 若兄弟節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都為黑色----（case 2） 
             */  
            if (colorOf(leftOf(sib))  == BLACK &&  
                colorOf(rightOf(sib)) == BLACK) {  
                setColor(sib, RED);  
                x = parentOf(x);  
            }   
            else {  
                /* 
                 * 如果兄弟節(jié)點(diǎn)只有右子樹(shù)為黑色----（case 3）  
                 * 這時(shí)情況會(huì)轉(zhuǎn)變?yōu)閏ase 4 
                 */  
                if (colorOf(rightOf(sib)) == BLACK) {  
                    setColor(leftOf(sib), BLACK);  
                    setColor(sib, RED);  
                    rotateRight(sib);  
                    sib = rightOf(parentOf(x));  
                }  
                /* 
                 *case 4 
                 */  
                setColor(sib, colorOf(parentOf(x)));  
                setColor(parentOf(x), BLACK);  
                setColor(rightOf(sib), BLACK);  
                rotateLeft(parentOf(x));  
                x = root;  
            }  
        }   
          
        /** 
         * case 5
         */  
        else {  
            Entry<K,V> sib = leftOf(parentOf(x));  

            if (colorOf(sib) == RED) {  
                setColor(sib, BLACK);  
                setColor(parentOf(x), RED);  
                rotateRight(parentOf(x));  
                sib = leftOf(parentOf(x));  
            }  

            if (colorOf(rightOf(sib)) == BLACK &&  
                colorOf(leftOf(sib)) == BLACK) {  
                setColor(sib, RED);  
                x = parentOf(x);  
            } else {  
                if (colorOf(leftOf(sib)) == BLACK) {  
                    setColor(rightOf(sib), BLACK);  
                    setColor(sib, RED);  
                    rotateLeft(sib);  
                    sib = leftOf(parentOf(x));  
                }  
                setColor(sib, colorOf(parentOf(x)));  
                setColor(parentOf(x), BLACK);  
                setColor(leftOf(sib), BLACK);  
                rotateRight(parentOf(x));  
                x = root;  
            }  
        }  
    }  

    setColor(x, BLACK);  
    }  

WeakHashMap

可能很多同學(xué)沒(méi)用過(guò)這個(gè)類(lèi)，沒(méi)吃過(guò)豬肉，應(yīng)該見(jiàn)過(guò)豬跑吧，根據(jù)名字猜測(cè)，大致能知道這是一個(gè)跟弱引用有關(guān)系的 HashMap。
我們來(lái)看看官方文檔的定義

以弱鍵 實(shí)現(xiàn)的基于哈希表的 Map。在 WeakHashMap 中，當(dāng)某個(gè)鍵不再正常使用時(shí)，將自動(dòng)移除其條目。更精確地說(shuō)，對(duì)于一個(gè)給定的鍵，其映射的存在并不阻止垃圾回收器對(duì)該鍵的丟棄，這就使該鍵成為可終止的，被終止，然后被回收。丟棄某個(gè)鍵時(shí)，其條目從映射中有效地移除，因此，該類(lèi)的行為與其他的 Map 實(shí)現(xiàn)有所不同。

嗯~~大致就是告訴我們，key 除了被 HashMap 引用之外沒(méi)有任何引用，就會(huì)自動(dòng)刪掉這個(gè) key 以及 value。

弱引用的概念：弱引用是用來(lái)描述非必需對(duì)象的，被弱引用關(guān)聯(lián)的對(duì)象只能生存到下一次垃圾收集發(fā)生之前，當(dāng)垃圾收集器工作時(shí)，無(wú)論當(dāng)前內(nèi)存是否足夠，都會(huì)回收掉只被弱引用關(guān)聯(lián)的對(duì)象。

大致我們也知道了這是怎么回事，就是控制 key 的外部引用，可以控制 HashMap 里面保存數(shù)據(jù)的存留，在大量數(shù)據(jù)的讀取刪除的時(shí)候，我們可以考慮使用 HashMap。

接下來(lái)我們通過(guò)一段代碼來(lái)學(xué)習(xí)怎么控制弱引用。

Map<String, String> weak = new WeakHashMap<String, String>();
weak.put(new String("1"), "1");
weak.put(new String("2"), "2");
weak.put(new String("3"), "3");
weak.put(new String("4"), "4");
weak.put(new String("5"), "5");
weak.put(new String("6"), "6");
Log.e("weak1:",weak.size()+"");//6
Runtime.getRuntime().gc();  //手動(dòng)觸發(fā) Full GC
try {
     Thread.sleep(50); //我的測(cè)試中發(fā)現(xiàn)必須sleep一下才能看到不一樣的結(jié)果
    } catch (InterruptedException e) {
     e.printStackTrace();
    }
Log.e("weak2:",weak.size()+"");//0

Map<String, String> weak2 = new WeakHashMap<String, String>();
weak2.put("1", "1");
weak2.put("2", "2");
weak2.put("3", "3");
weak2.put("4", "4");
weak2.put("5", "5");
weak2.put("6", "6");
Log.e("weak3:",weak2.size()+"");//6
Runtime.getRuntime().gc();
try {
    Thread.sleep(50);
    } catch (InterruptedException e) {
    e.printStackTrace();
}
Log.e("weak4:",weak2.size()+"");//6

打印結(jié)果在代碼后面的注釋里面，從這里我們可以看到。weak里面的 key 值只有weak 對(duì)其持有引用，所以在調(diào)用 gc 之后，weak的 size 就變成了0.這里有兩點(diǎn)需要注意，一是調(diào)用 gc 不能用 System.gc()，而要用Runtime.getRuntime().gc()。二是要分得清new String("1")和“1”的區(qū)別。

接下來(lái)，我們就來(lái)看看key 弱引用是如何關(guān)聯(lián)的。

查看源碼我們能看到，幾乎所有的方法都直接或者間接的調(diào)用了expungeStaleEntries()方法，我們來(lái)看看這個(gè)方法。

/**
 * Expunges stale entries from the table.
 */
private void expungeStaleEntries() {
    for (Object x; (x = queue.poll()) != null; ) {
        synchronized (queue) {
            @SuppressWarnings("unchecked")
                Entry<K,V> e = (Entry<K,V>) x;
            int i = indexFor(e.hash, table.length);

            Entry<K,V> prev = table[i];
            Entry<K,V> p = prev;
            while (p != null) {
                Entry<K,V> next = p.next;
                if (p == e) {
                    if (prev == e)
                        table[i] = next;
                    else
                        prev.next = next;
                    // Must not null out e.next;
                    // stale entries may be in use by a HashIterator
                    e.value = null; // Help GC
                    size--;
                    break;
                }
                prev = p;
                p = next;
            }
        }
    }
}

方法名已經(jīng)方法注釋都告訴了我們，這個(gè)方法是在清除 tab 里面過(guò)期的元素。但是我找遍了整個(gè) WeakHashMap 的源碼，都沒(méi)有找到任何 queue.add()的操作，mmp，這特么幾個(gè)意思。最后，細(xì)心的我在 WeakHashMap 的 put 方法里面找到了這樣以后代碼 tab[i] = new Entry<>(k, value, queue, h, e);
不多說(shuō)了，直接去看Entry的構(gòu)造方法。

private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
V value;
int hash;
Entry<K,V> next;

/**
 * Creates new entry.
 */
Entry(Object key, V value,
      ReferenceQueue<Object> queue,
      int hash, Entry<K,V> next) {
    super(key, queue);
    this.value = value;
    this.hash  = hash;
    this.next  = next;
}
...

我們可以看到Entry 繼承自WeakReference，然后把key 和queue 傳到了WeakReference 的構(gòu)造方法中,然后調(diào)用了父類(lèi)Reference 的方法。

好了，到這里就不用太糾結(jié)了，就是在Reference 里面做的操作。大致的流程是這樣的：JVM計(jì)算對(duì)象key 的可達(dá)性后，發(fā)現(xiàn)沒(méi)有該key 對(duì)象的引用，那么就會(huì)把該對(duì)象關(guān)聯(lián)的Entry<K,V>添加到pending中，所以每次垃圾回收時(shí)發(fā)現(xiàn)弱引用對(duì)象沒(méi)有被引用時(shí)，就會(huì)將該對(duì)象放入待清除隊(duì)列中，最后由應(yīng)用程序來(lái)完成清除，WeakHashMap中就負(fù)責(zé)由方法expungeStaleEntries()來(lái)完成清除。

其實(shí)這里關(guān)于Reference 我自己也沒(méi)有弄得很清楚，下次找個(gè)時(shí)間單獨(dú)學(xué)Reference 機(jī)制。

ConCurrentMap

并發(fā)集合類(lèi)，以后在并發(fā)的時(shí)候再看吧。
挺重要的一個(gè)冷門(mén)知識(shí)點(diǎn)，Android 幾乎用不上高并發(fā)，剛剛問(wèn)了 Java 后端的同學(xué)，他們也說(shuō)沒(méi)用過(guò)。。。。是因?yàn)槲覜](méi)去過(guò)大廠(chǎng)的原因么~~~
據(jù)說(shuō)大廠(chǎng)面試經(jīng)常會(huì)問(wèn)這個(gè)知識(shí)點(diǎn)。
同樣遺漏的還有 BlockingQueue.

IdentityHashMap

一個(gè) Key 值可以重復(fù)的 map.

此類(lèi)利用哈希表實(shí)現(xiàn) Map 接口，比較鍵（和值）時(shí)使用引用相等性代替對(duì)象相等性。換句話(huà)說(shuō)，在 IdentityHashMap 中，當(dāng)且僅當(dāng) (k1= =k2) 時(shí)，才認(rèn)為兩個(gè)鍵 k1 和 k2 相等（在正常 Map 實(shí)現(xiàn)（如 HashMap）中，當(dāng)且僅當(dāng)滿(mǎn)足下列條件時(shí)才認(rèn)為兩個(gè)鍵 k1 和 k2 相等：(k1= =null ? k2= =null : e1.equals(e2))

也就是說(shuō)，只有當(dāng) 兩個(gè) key 指向同一引用的時(shí)候，才會(huì)執(zhí)行覆蓋操作。

用途？舉個(gè)例子，jvm 中所有的對(duì)象都是獨(dú)一無(wú)二的，哪怕兩個(gè)對(duì)象是同一個(gè) class 的對(duì)象，而且兩個(gè)對(duì)象的數(shù)據(jù)完全相同，對(duì)于 jvm 來(lái)說(shuō)，他們也是完全不相同的，如果要用一個(gè) map 來(lái)記錄這樣jvm 中的對(duì)象，就需要用到 IdentityHashMap。

具體我也沒(méi)用過(guò)~~??

結(jié)束語(yǔ)

集合篇到這里就差不多結(jié)束了，總的來(lái)說(shuō)，只分析了框架，但并不是知道了框架設(shè)計(jì)，捋清了實(shí)現(xiàn)思路，就一定能手?jǐn)]出來(lái)，要想深入掌握，還得自己跟著思路去手?jǐn)]一遍。接下來(lái)再花一天的時(shí)間手?jǐn)] ArrayList、HashMap、TreeMap，就正式開(kāi)始 I/O流的學(xué)習(xí)吧。