聲明唱逢，本文用得是jdk1.8
一吴侦、Map介紹
1.1為什么需要Map
前面我們學(xué)習(xí)的Collection叫做集合，它可以快速查找現(xiàn)有的元素坞古。
而Map在《Core Java》中稱之為-->映射..
映射的模型圖是這樣的：
那為什么我們需要這種數(shù)據(jù)存儲結(jié)構(gòu)呢备韧？？痪枫？舉個例子
作為學(xué)生來說织堂，我們是根據(jù)學(xué)號來區(qū)分不同的學(xué)生。只要我們知道學(xué)號奶陈，就可以獲取對應(yīng)的學(xué)生信息易阳。這就是Map映射的作用！
生活中還有很多這樣的例子：只要你掏出身份證(key)吃粒，那就可以證明是你自己(value)
1.2Map與Collection的區(qū)別
1.3Map的功能
下面我們來看看Map的源碼：
簡單常用的Map功能有這么一些：
下面用紅色框框圈住的就是Map值得關(guān)注的子類：
二潦俺、散列表介紹
無論是Set還是Map，我們會發(fā)現(xiàn)都會有對應(yīng)的-->HashSet,HashMap
首先我們也先得回顧一下數(shù)據(jù)和鏈表：
鏈表和數(shù)組都可以按照人們的意愿來排列元素的次序声搁，他們可以說是有序的(存儲的順序和取出的順序是一致的)
但同時黑竞，這會帶來缺點：想要獲取某個元素，就要訪問所有的元素疏旨，直到找到為止很魂。
這會讓我們消耗很多的時間在里邊，遍歷訪問元素~
而還有另外的一些存儲結(jié)構(gòu)：不在意元素的順序檐涝，能夠快速的查找元素的數(shù)據(jù)
其中就有一種非常常見的：散列表
2.1散列表工作原理
散列表為每個對象計算出一個整數(shù)遏匆，稱為散列碼。根據(jù)這些計算出來的整數(shù)(散列碼)保存在對應(yīng)的位置上谁榜！
在Java中幅聘，散列表用的是鏈表數(shù)組實現(xiàn)的，每個列表稱之為桶窃植。【之前也寫過桶排序就這么簡單帝蒿，可以回顧回顧】
一個桶上可能會遇到被占用的情況(hashCode散列碼相同，就存儲在同一個位置上)巷怜，這種情況是無法避免的葛超，這種現(xiàn)象稱之為：散列沖突
此時需要用該對象與桶上的對象進行比較，看看該對象是否存在桶子上了~如果存在延塑，就不添加了绣张，如果不存在則添加到桶子上
當(dāng)然了，如果hashcode函數(shù)設(shè)計得足夠好关带，桶的數(shù)目也足夠侥涵，這種比較是很少的~
在JDK1.8中，桶滿時會從鏈表變成平衡二叉樹
如果散列表太滿，是需要對散列表再散列芜飘，創(chuàng)建一個桶數(shù)更多的散列表务豺，并將原有的元素插入到新表中，丟棄原來的表~
裝填因子(load factor)決定了何時對散列表再散列~
裝填因子默認(rèn)為0.75嗦明，如果表中超過了75%的位置已經(jīng)填入了元素冲呢，那么這個表就會用雙倍的桶數(shù)自動進行再散列
當(dāng)然了， 在后面閱讀源碼的時候會繼續(xù)說明的招狸，現(xiàn)在簡單了解一下即可~
擴展閱讀：
https://www.cnblogs.com/s-b-b/p/6208565.html
https://www.cnblogs.com/chinajava/p/5808416.html
三、紅黑樹介紹
上面散列表中已經(jīng)提過了：如果桶數(shù)滿的時候邻薯，JDK8是將鏈表轉(zhuǎn)成紅黑樹的~裙戏。并且，我們的TreeSet厕诡、TreeMap底層都是紅黑樹來實現(xiàn)的累榜。
所以，在這里學(xué)習(xí)一波紅黑樹到底是啥玩意灵嫌。
在未學(xué)習(xí)之前壹罚，我們可能是聽過紅黑樹這么一個數(shù)據(jù)結(jié)構(gòu)類型的，還有其他什么B/B+樹等等寿羞，反正是比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)了~~~
各種常見的樹的用途：
來源：
https://www.zhihu.com/question/30527705/answer/52527887
3.1回顧二叉查找樹
二叉查找樹也有個例(最壞)的情況(線性)：
上面符合二叉樹的特性猖凛，但是它是線性的，完全沒樹的用處~
樹是要“均衡”才能將它的優(yōu)點展示出來的~绪穆，比如下面這種：
因此辨泳，就有了平衡樹這么一個概念~紅黑樹就是一種平衡樹，它可以保證二叉樹基本符合矮矮胖胖(均衡)的結(jié)構(gòu)
3.2知新2-3樹
講到了平衡樹就不得不說最基礎(chǔ)的2-3樹玖院，2-3樹長的是這個樣子：
在二叉查找樹上菠红，我們插入節(jié)點的過程是這樣的：小于節(jié)點值往右繼續(xù)與左子節(jié)點比，大于則繼續(xù)與右子節(jié)點比难菌，直到某節(jié)點左或右子節(jié)點為空试溯，把值插入進去。這樣無法避免偏向問題
而2-3樹不一樣：它插入的時候可以保持樹的平衡郊酒！
在2-3樹插入的時可以簡單總結(jié)為兩個操作：
合并2-節(jié)點為3-節(jié)點遇绞，擴充將3-節(jié)點擴充為一個4-節(jié)點
分解4-節(jié)點為3-節(jié)點，節(jié)點3-節(jié)點為2-節(jié)點
……..至使得樹平衡~
合并分解的操作還是比較復(fù)雜的猎塞，要分好幾種情況试读，代碼量很大~這里我就不介紹了，因為要學(xué)起來是一大堆的荠耽，很麻煩~
3.3從2-3樹到紅黑樹
由于2-3樹為了保持平衡性钩骇，在維護的時候是需要大量的節(jié)點交換的！這些變換在實際代碼中是很復(fù)雜的，大佬們在2-3樹的理論基礎(chǔ)上發(fā)明了紅黑樹(2-3-4樹也是同樣的道理倘屹，只是2-3樹是最簡單的一種情況银亲，所以我就不說2-3-4樹了)。
紅黑樹是對2-3查找樹的改進纽匙，它能用一種統(tǒng)一的方式完成所有變換务蝠。
紅黑樹是一種平衡二叉樹,因此它沒有3-節(jié)點。那紅黑樹是怎么將3-節(jié)點來改進成全都是二叉樹呢烛缔？
紅黑樹就字面上的意思馏段，有紅色的節(jié)點，有黑色的節(jié)點：
我們可以將紅色節(jié)點的左鏈接畫平看看：
一顆典型的二叉樹：
將紅色節(jié)點的左鏈接畫平之后：得到2-3平衡樹:
3.4紅黑樹基礎(chǔ)知識
前面已經(jīng)說了践瓷，紅黑樹是在2-3的基礎(chǔ)上實現(xiàn)的一種樹院喜，它能夠用統(tǒng)一的方式完成所有變換。很好理解：紅黑樹也是平衡樹的一種晕翠，在插入元素的時候它也得保持樹的平衡喷舀，那紅黑樹是以什么的方式來保持樹的平衡的呢？
紅黑樹用的是也是兩種方式來替代2-3樹不斷的節(jié)點交換操作：
旋轉(zhuǎn)：順時針旋轉(zhuǎn)和逆時針旋轉(zhuǎn)
反色：交換紅黑的顏色
這個兩個實現(xiàn)比2-3樹交換的節(jié)點(合并淋肾，分解)要方便一些
紅黑樹為了保持平衡硫麻，還有制定一些約束，遵守這些約束的才能叫做紅黑樹：
紅黑樹是二叉搜索樹樊卓。
根節(jié)點是黑色拿愧。
每個葉子節(jié)點都是黑色的空節(jié)點（NIL節(jié)點）。
每個紅色節(jié)點的兩個子節(jié)點都是黑色碌尔。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(每一條樹鏈上的黑色節(jié)點數(shù)量（稱之為“黑高”）必須相等)赶掖。
