摘要：并且，我們的底層都是紅黑樹(shù)來(lái)實(shí)現(xiàn)的。紅黑樹(shù)是一種平衡二叉樹(shù)因此它沒(méi)有節(jié)點(diǎn)。

聲明，本文用得是jdk1.8

前面已經(jīng)講了Collection的總覽和剖析List集合：

Collection總覽

List集合就這么簡(jiǎn)單【源碼剖析】

原本我是打算繼續(xù)將Collection下的Set集合的，結(jié)果看了源碼發(fā)現(xiàn)：Set集合實(shí)際上就是HashMap來(lái)構(gòu)建的！

所以，就先介紹Map集合、散列表和紅黑樹(shù)吧！

看這篇文章之前最好是有點(diǎn)數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)：

Java實(shí)現(xiàn)單向鏈表

棧和隊(duì)列就是這么簡(jiǎn)單

二叉樹(shù)就這么簡(jiǎn)單

當(dāng)然了，如果講得有錯(cuò)的地方還請(qǐng)大家多多包涵并不吝在評(píng)論去指正～

前面我們學(xué)習(xí)的Collection叫做集合，它可以快速查找現(xiàn)有的元素。

而Map在《Core Java》中稱之為-->映射..

映射的模型圖是這樣的：

那為什么我們需要這種數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)呢？？？舉個(gè)例子

作為學(xué)生來(lái)說(shuō)，我們是根據(jù)學(xué)號(hào)來(lái)區(qū)分不同的學(xué)生。只要我們知道學(xué)號(hào)，就可以獲取對(duì)應(yīng)的學(xué)生信息。這就是Map映射的作用！

生活中還有很多這樣的例子：只要你掏出身份證(key)，那就可以證明是你自己(value)

下面我們來(lái)看看Map的源碼：

簡(jiǎn)單常用的Map功能有這么一些：

下面用紅色框框圈住的就是Map值得關(guān)注的子類：

無(wú)論是Set還是Map，我們會(huì)發(fā)現(xiàn)都會(huì)有對(duì)應(yīng)的-->HashSet,HashMap

首先我們也先得回顧一下數(shù)據(jù)和鏈表：

鏈表和數(shù)組都可以按照人們的意愿來(lái)排列元素的次序，他們可以說(shuō)是有序的(存儲(chǔ)的順序和取出的順序是一致的)

但同時(shí)，這會(huì)帶來(lái)缺點(diǎn)：想要獲取某個(gè)元素，就要訪問(wèn)所有的元素，直到找到為止。

這會(huì)讓我們消耗很多的時(shí)間在里邊，遍歷訪問(wèn)元素~

而還有另外的一些存儲(chǔ)結(jié)構(gòu)：不在意元素的順序，能夠快速的查找元素的數(shù)據(jù)

其中就有一種非常常見(jiàn)的：散列表

散列表為每個(gè)對(duì)象計(jì)算出一個(gè)整數(shù)，稱為散列碼。根據(jù)這些計(jì)算出來(lái)的整數(shù)(散列碼)保存在對(duì)應(yīng)的位置上！

在Java中，散列表用的是鏈表數(shù)組實(shí)現(xiàn)的，每個(gè)列表稱之為桶。【之前也寫(xiě)過(guò)桶排序就這么簡(jiǎn)單，可以回顧回顧】

一個(gè)桶上可能會(huì)遇到被占用的情況(hashCode散列碼相同，就存儲(chǔ)在同一個(gè)位置上)，這種情況是無(wú)法避免的，這種現(xiàn)象稱之為：散列沖突

此時(shí)需要用該對(duì)象與桶上的對(duì)象進(jìn)行比較，看看該對(duì)象是否存在桶子上了~如果存在，就不添加了，如果不存在則添加到桶子上

當(dāng)然了，如果hashcode函數(shù)設(shè)計(jì)得足夠好，桶的數(shù)目也足夠，這種比較是很少的~

在JDK1.8中，桶滿時(shí)會(huì)從鏈表變成平衡二叉樹(shù)

如果散列表太滿，是需要對(duì)散列表再散列，創(chuàng)建一個(gè)桶數(shù)更多的散列表，并將原有的元素插入到新表中，丟棄原來(lái)的表~

裝填因子(load factor)決定了何時(shí)對(duì)散列表再散列~

裝填因子默認(rèn)為0.75，如果表中超過(guò)了75%的位置已經(jīng)填入了元素，那么這個(gè)表就會(huì)用雙倍的桶數(shù)自動(dòng)進(jìn)行再散列

當(dāng)然了， 在后面閱讀源碼的時(shí)候會(huì)繼續(xù)說(shuō)明的，現(xiàn)在簡(jiǎn)單了解一下即可~

擴(kuò)展閱讀：

https://www.cnblogs.com/s-b-b/p/6208565.html

https://www.cnblogs.com/chinajava/p/5808416.html

上面散列表中已經(jīng)提過(guò)了：如果桶數(shù)滿的時(shí)候，JDK8是將鏈表轉(zhuǎn)成紅黑樹(shù)的~。并且，我們的TreeSet、TreeMap底層都是紅黑樹(shù)來(lái)實(shí)現(xiàn)的。

所以，在這里學(xué)習(xí)一波紅黑樹(shù)到底是啥玩意。

之前涉及過(guò)二叉樹(shù)的文章：

二叉樹(shù)就這么簡(jiǎn)單

堆排序就這么簡(jiǎn)單

在未學(xué)習(xí)之前，我們可能是聽(tīng)過(guò)紅黑樹(shù)這么一個(gè)數(shù)據(jù)結(jié)構(gòu)類型的，還有其他什么B/B+樹(shù)等等，反正是比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)了~~~

各種常見(jiàn)的樹(shù)的用途：

來(lái)源：
https://www.zhihu.com/question/30527705/answer/52527887

首先我們來(lái)回顧一下：利用二叉查找樹(shù)的特性，我們一般來(lái)說(shuō)可以很快地查找出對(duì)應(yīng)的元素。

二叉樹(shù)就這么簡(jiǎn)單

可是二叉查找樹(shù)也有個(gè)例(最壞)的情況(線性)：

上面符合二叉樹(shù)的特性，但是它是線性的，完全沒(méi)樹(shù)的用處~

樹(shù)是要“均衡”才能將它的優(yōu)點(diǎn)展示出來(lái)的~，比如下面這種：

因此，就有了平衡樹(shù)這么一個(gè)概念~紅黑樹(shù)就是一種平衡樹(shù)，它可以保證二叉樹(shù)基本符合矮矮胖胖(均衡)的結(jié)構(gòu)

講到了平衡樹(shù)就不得不說(shuō)最基礎(chǔ)的2-3樹(shù)，2-3樹(shù)長(zhǎng)的是這個(gè)樣子：

在二叉查找樹(shù)上，我們插入節(jié)點(diǎn)的過(guò)程是這樣的：小于節(jié)點(diǎn)值往右繼續(xù)與左子節(jié)點(diǎn)比，大于則繼續(xù)與右子節(jié)點(diǎn)比，直到某節(jié)點(diǎn)左或右子節(jié)點(diǎn)為空，把值插入進(jìn)去。這樣無(wú)法避免偏向問(wèn)題

而2-3樹(shù)不一樣：它插入的時(shí)候可以保持樹(shù)的平衡！

在2-3樹(shù)插入的時(shí)可以簡(jiǎn)單總結(jié)為兩個(gè)操作：

合并2-節(jié)點(diǎn)為3-節(jié)點(diǎn)，擴(kuò)充將3-節(jié)點(diǎn)擴(kuò)充為一個(gè)4-節(jié)點(diǎn)

分解4-節(jié)點(diǎn)為3-節(jié)點(diǎn)，節(jié)點(diǎn)3-節(jié)點(diǎn)為2-節(jié)點(diǎn)

........至使得樹(shù)平衡~

合并分解的操作還是比較復(fù)雜的，要分好幾種情況，代碼量很大~這里我就不介紹了，因?yàn)橐獙W(xué)起來(lái)是一大堆的，很麻煩~

由于2-3樹(shù)為了保持平衡性，在維護(hù)的時(shí)候是需要大量的節(jié)點(diǎn)交換的！這些變換在實(shí)際代碼中是很復(fù)雜的，大佬們在2-3樹(shù)的理論基礎(chǔ)上發(fā)明了紅黑樹(shù)(2-3-4樹(shù)也是同樣的道理，只是2-3樹(shù)是最簡(jiǎn)單的一種情況，所以我就不說(shuō)2-3-4樹(shù)了)。

紅黑樹(shù)是對(duì)2-3查找樹(shù)的改進(jìn)，它能用一種統(tǒng)一的方式完成所有變換。

紅黑樹(shù)是一種平衡二叉樹(shù),因此它沒(méi)有3-節(jié)點(diǎn)。那紅黑樹(shù)是怎么將3-節(jié)點(diǎn)來(lái)改進(jìn)成全都是二叉樹(shù)呢？

紅黑樹(shù)就字面上的意思，有紅色的節(jié)點(diǎn)，有黑色的節(jié)點(diǎn)：

我們可以將紅色節(jié)點(diǎn)的左鏈接畫(huà)平看看：

一顆典型的二叉樹(shù)：

將紅色節(jié)點(diǎn)的左鏈接畫(huà)平之后：得到2-3平衡樹(shù):

前面已經(jīng)說(shuō)了，紅黑樹(shù)是在2-3的基礎(chǔ)上實(shí)現(xiàn)的一種樹(shù)，它能夠用統(tǒng)一的方式完成所有變換。很好理解：紅黑樹(shù)也是平衡樹(shù)的一種，在插入元素的時(shí)候它也得保持樹(shù)的平衡，那紅黑樹(shù)是以什么的方式來(lái)保持樹(shù)的平衡的呢？

紅黑樹(shù)用的是也是兩種方式來(lái)替代2-3樹(shù)不斷的節(jié)點(diǎn)交換操作：

旋轉(zhuǎn)：順時(shí)針旋轉(zhuǎn)和逆時(shí)針旋轉(zhuǎn)

反色：交換紅黑的顏色

這個(gè)兩個(gè)實(shí)現(xiàn)比2-3樹(shù)交換的節(jié)點(diǎn)(合并，分解)要方便一些

紅黑樹(shù)為了保持平衡，還有制定一些約束，遵守這些約束的才能叫做紅黑樹(shù)：

紅黑樹(shù)是二叉搜索樹(shù)。

根節(jié)點(diǎn)是黑色。

每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(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è)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)(每一條樹(shù)鏈上的黑色節(jié)點(diǎn)數(shù)量（稱之為“黑高”）必須相等)。

紅黑樹(shù)可以說(shuō)是十分復(fù)雜的，我在學(xué)習(xí)的時(shí)候并沒(méi)有去認(rèn)真細(xì)看當(dāng)中的處理細(xì)節(jié)，只是大概的過(guò)了一遍，知道了整體~

有了前輩很多優(yōu)質(zhì)的資料，相信要等到想要理解其中的細(xì)節(jié)，花點(diǎn)力氣和時(shí)間還是可以掌握一二的。

紅黑樹(shù)參考資料：

https://blog.csdn.net/chen_zhang_yu/article/details/52415077

https://riteme.github.io/blog/2016-3-12/2-3-tree-and-red-black-tree.html#fn:red-is-left

http://www.sohu.com/a/201923614_466939

https://www.jianshu.com/p/37c845a5add6

https://www.cnblogs.com/nullzx/p/6111175.html

https://blog.csdn.net/fei33423/article/details/79132930

這篇主要介紹了Map集合的基礎(chǔ)知識(shí)，了解Map的常用子類~

簡(jiǎn)單介紹了散列表和紅黑樹(shù)，他倆作為Hashxxx和Treexxx的底層，了解其整體思想和相關(guān)基礎(chǔ)在后續(xù)看源碼也不至于那么懵~

后續(xù)會(huì)去看Map常用子類的源碼，文章敬請(qǐng)期待~~~~

文章的目錄導(dǎo)航：https://zhongfucheng.bitcron.com/post/shou-ji/gong-zhong-hao-wen-zhang-zheng-li

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y。為了大家方便，剛新建了一下qq群：742919422，大家也可以去交流交流。謝謝支持了！希望能多介紹給其他有需要的朋友

參考資料：

《Core Java》