上壹篇文章 HashMap的底層原理探索 我們分析了JDK1.7中Hashmap的源碼實現，但是在JDK1.8的時候HashMap的實現做了很大的變動和優化。1.7和1.7之前HashMap都是“數組+鏈表”實現的，1.8之後就是“數組+（鏈表或紅黑樹）”來實現的了。這裏我特地將“鏈表或紅黑樹”用壹對括號括在壹起，因為HashMap底層依舊是壹個數組，然後數組中的元素是鏈表或者紅黑樹來實現的。
HashMap的實現就先介紹到這，下面就先講壹下紅黑樹，然後才能理解為什麽要用紅黑樹來優化HashMap，用紅黑樹有什麽好處。
在介紹紅黑樹之前我們要先理解二叉查找樹的數據結構。下面簡單介紹壹下。
上面這張圖就是壹個二叉查找樹。二叉查找樹有如下幾條特性
（1）.左子樹上所有結點的值均小於或等於它的根結點的值。
（2）.右子樹上所有結點的值均大於或等於它的根結點的值。
（3）.左、右子樹也分別為二叉排序樹
那既然他名字中是有“查找”的，那麽他是怎麽查找的呢？比如我們要查找10這個元素，查找過程為：首先找到根節點，然後根據二叉查找樹的第壹二條特性，我們知道要查找的10>9所以是在根節點的右邊去查找，找到13，10<13,所以接著在13的左邊找，找到11,10<11,繼續在11的左邊查找，這樣就找到了10.這其實就是二分查找的思想。最後我們要查出結果所需的最大次數就是二叉樹的高度！（二分查找的思想:找到數組的中間位置的元素v，將數組分成>v和<v兩部分，然後將v和要查找的數據進行壹個比較，如果大於v那麽就在>v的部分再次進行二分查找，否則就在<v的部分進行二分查找，直到找到對應的元素。）
那既然要查出結果所需的最大次數就是二叉樹的高度，那這個高度會不會有時候很長呢？
比如我們依次插入 根節點為9如下五個節點：7,6,5,4,3。依照二叉查找樹的特性，結果會變成什麽樣呢？7,6,5,4,3壹個比壹個小，那麽就會成壹條直線，也就是成為了線性的查詢，時間復雜度變成了O（N）級別。為了解決這種情況，該紅黑樹出場了。
紅黑樹其實就是壹種 自平衡 的二叉查找樹。他這個自平衡的特性就是對HashMap中鏈表可能會很長做出的優化。
紅黑樹是每個節點都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強制壹般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:
性質1. 節點是紅色或黑色。
性質2. 根節點是黑色。
性質3 每個葉節點（NIL節點，空節點）是黑色的。
性質4 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
性質5. 從任壹節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
下面這棵樹就是壹個典型的紅黑樹
紅黑樹那麽多規則，那麽在插入和刪除元素會不會破壞紅黑樹的規則呢？什麽情況下會破壞？什麽情況下不會？
比如我們向原紅黑樹插入為14的新節點就不會破壞規則
向原紅黑樹插入值為21的新節點就破壞了規則
那麽紅黑樹是怎麽維護這個二叉查找樹的自平衡性的呢？
紅黑樹通過 “變色”和“旋轉” 來維護紅黑樹的規則，變色就是讓黑的變成紅的，紅的變成黑的，旋轉又分為“左旋轉”和“右旋轉”。這個比較復雜，容易暈，我們就只要知道紅黑樹就是通過這種方式來實現它的自平衡性就行了。
JDK1.7的時候是使用壹個Entry數組來存儲數據，用key的hashcode取模來決定key會被放到數組裏的位置，如果hashcode相同，或者hashcode取模後的結果相同（hash collision），那麽這些key會被定位到Entry數組的同壹個格子裏，這些key會形成壹個鏈表。在hashcode特別差的情況下，比方說所有key的hashcode都相同，這個鏈表可能會很長，那麽put/get操作都可能需要遍歷這個鏈表。也就是說時間復雜度在最差情況下會退化到O(n)
紅黑樹我們大致了解了，他的好處就是他的自平衡性，讓他這棵樹的最大高度為2log(n+1)，n是樹的節點數。那麽紅黑樹的復雜度就只有 O(log n)。
下面我們通過追蹤JDK1.8 HashMap的put方法的源碼來理解
put方法調用了putVal方法
通過putVal方法可以看到這裏的數組和1.7不同，是使用了壹個Node數組來存儲數據。那這個Node和1.7裏面的Entry的區別是什麽呢？
HashMap中的紅黑樹節點 采用的是TreeNode 類
TreeNode和Entry都是Node的子類，也就說Node可能是鏈表結構，也可能是紅黑樹結構。
如果插入的key的hashcode相同，那麽這些key也會被定位到Node數組的同壹個格子裏。如果同壹個格子裏的key不超過8個，使用鏈表結構存儲。如果超過了8個，那麽會調用treeifyBin函數，將鏈表轉換為紅黑樹。
先分析到這。。。。。