一、Map
1.1 Map和Collection
- map是將鍵映射到值得對象，一個映射不能包含重復(fù)的鍵，每個鍵最多只能映射到一個值
- map儲存的元素是成對出現(xiàn)的，鍵唯一，值可以重復(fù)
- Collection儲存的元素是單獨(dú)出現(xiàn)的，Set不可以重復(fù)，List可以重復(fù)
1.2 常用的一些功能
二、散列表的介紹
- 鏈表和數(shù)組都可以按照人們的意愿來排列元素的次序，他們可以說是有序的(存儲的順序和取出的順序是一致的），但想要獲取某個元素就要遍歷整個線性表，浪費(fèi)大量時間
- 散列表：不在意元素的順序，能夠快速的查找元素的數(shù)據(jù)
2.1 什么是散列表
在Java中，散列表由數(shù)組和鏈表組成。它的工作原理是為每個對象計算出一個散列碼，將整個散列碼與桶的數(shù)量作求余操作（或者h(yuǎn)ash&（n-1）），這個計算出的整數(shù)就是對象在散列表中的位置。
哈希表還有一個重要的屬性: 負(fù)載因子(load factor)，它用來衡量哈希表的 空/滿 程度，一定程度上也可以體現(xiàn)查詢的效率，計算公式為:
負(fù)載因子 = 總鍵值對數(shù) / 箱子個數(shù)
負(fù)載因子越大，意味著哈希表越滿，越容易導(dǎo)致沖突，性能也就越低。因此，一般來說，當(dāng)負(fù)載因子大于某個常數(shù)(可能是 1，或者 0.75 等)時，哈希表將自動擴(kuò)容。
哈希表在自動擴(kuò)容時，一般會創(chuàng)建兩倍于原來個數(shù)的箱子，因此即使 key 的哈希值不變，對箱子個數(shù)取余的結(jié)果也會發(fā)生改變，因此所有鍵值對的存放位置都有可能發(fā)生改變，這個過程也稱為重哈希(rehash)。
哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過大的問題。假設(shè)所有 key 的哈希值都一樣，那么即使擴(kuò)容以后他們的位置也不會變化。雖然負(fù)載因子會降低，但實(shí)際存儲在每個箱子中的鏈表長度并不發(fā)生改變，因此也就不能提高哈希表的查詢性能。
2.2 散列沖突
有時候兩個不同的對象計算出相同的hashCode，就儲存在同一個桶上，這就是散列沖突。此時需要用該對象和桶上的對象進(jìn)行比較。如果存在，不添加，不存在，添加。（JDK1.8中，桶的容量變成8時，會從鏈表變成紅黑樹）
如果散列表太滿了，就需要對散列表再散列。創(chuàng)建一個新的桶，將原來的數(shù)據(jù)插入到新的桶中
裝填因子（load factor）決定了什么時候擴(kuò)容。負(fù)載因子越大，意味著哈希表越滿，越容易導(dǎo)致沖突，鏈表變長，查詢效率降低，性能也就越低。因此，一般來說，當(dāng)負(fù)載因子大于某個常數(shù)(可能是 1，或者 0.75 等)時，哈希表將自動進(jìn)行2倍擴(kuò)容。負(fù)載因子越小，沖突發(fā)生的可能性小，但是導(dǎo)致散列表的稀疏程度越大，造成了空間的浪費(fèi)。
三、什么是紅黑樹
利用二叉查找樹的特性，可以快速查找到某個元素。但是如果數(shù)據(jù)是按升序或降序排列的，這是樹就變成了鏈表。
紅黑樹是一種平衡樹，它可以保證二叉樹的均衡結(jié)構(gòu)
只有遵循這些約束的才叫紅黑樹（背這個貌似沒啥用）：
- 紅黑樹是二叉搜索樹。
- 根節(jié)點(diǎn)是黑色。
- 每個葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）。
- 每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點(diǎn))
- 從任一節(jié)點(diǎn)到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)(每一條樹鏈上的黑色節(jié)點(diǎn)數(shù)量（稱之為“黑高”）必須相等)。
3.1 由2-3樹到紅黑樹
如果從代碼角度去理解紅黑樹的旋轉(zhuǎn)和變色，那么會有助于增加我們對紅黑樹的恐懼
構(gòu)建過程：
- 合并2-節(jié)點(diǎn)使其變成3-節(jié)點(diǎn)，繼續(xù)擴(kuò)充3-節(jié)點(diǎn)，將其變成4-節(jié)點(diǎn)
- 從下到上，分解4-節(jié)點(diǎn)為3-節(jié)點(diǎn)...直至不能再分
- （根據(jù)此過程可以快速將畫出2-3樹，然后修改成紅黑樹）
由2-3樹腦補(bǔ)的紅黑樹的顏色表示：每個節(jié)點(diǎn)只有一條鏈接指向自己（從父節(jié)點(diǎn)到自己），將鏈接的顏色保存在表示節(jié)點(diǎn)的Node數(shù)據(jù)類型的boolean變量color中，若為true，說明這個節(jié)點(diǎn)是紅色的
紅黑樹參考資料：
- 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
- http://www.itdecent.cn/p/37c845a5add6
- https://www.cnblogs.com/nullzx/p/6111175.html
- https://blog.csdn.net/fei33423/article/details/79132930
