今天我們接着上面繼續分析HashMap的源碼，JDK8中我們引入了紅黑樹，這一章節，我們主要來探讨下紅黑樹。 在引入紅黑樹之前，我們先了解下二叉查找樹（Binary Search Tree BST）。
1. 二叉查找樹
BST具備的特性：
（1）左側樹值小于等于它的根節點值。
（2）右側樹大于等于它的根節點值。
（3）左右側數都是二叉查找樹。
BST具備的優點：
（1）通過上面的特征描述，相比線型存儲，它優化了查找的性能，比如說：下面就是一個典型的二叉樹查找，如果我們要查找數值為10的節點，隻需要3步，9->13->11->10。
BST具備的缺陷：
1.糟糕情況下會變成線型結構，這樣會大大降低性能。（這種情況比如說：插入節點總是小于根節點或者大于根節點），如下圖所示：
2. 二叉查找樹
基于二叉查找樹存在這種缺陷，紅黑樹的出現就是解決這種問題，它是二叉查找樹的典型，又叫做平衡二叉查找樹，接下來具體講講紅黑樹的一些特征。
紅黑樹的特征：
（1）根節點是黑色
（2）顧名思義，節點的顔色分為紅色或者黑色
（3）空節點為黑色
（4）每個紅色節點的子節點都是黑色節點（不能有兩個連續的紅色節點）
（5）從任意節點到每個葉子的所有路徑黑色節點個數相同
由于紅黑樹具有上面這些特征的限制，我們在對紅黑樹進行插入，删除操作時可能會破壞原有紅黑樹的樹結構，這個時候需要對數結構重新作出調整，紅黑數調整的方式有有兩種：變色和旋轉（左旋轉、右旋轉）。
- 左旋轉
對于目前結點而言，如果右子結點為紅色，左子結點為黑色，則執行左旋轉，如下圖：
- 右旋轉
對于目前結點而言，如果左子、左孫子結點均為紅色，則執行右旋轉，如下圖：
- 變色
對于目前結點而言，如果左、右子結點均為紅色，則執行變色，如下圖：