上一篇文章HashMap的底層原理探索我們分析了JDK1.7中Hashmap的源碼實(shí)現(xiàn)，但是在JDK1.8的時(shí)候HashMap的實(shí)現(xiàn)做了很大的變動(dòng)和優(yōu)化蜜氨。1.7和1.7之前HashMap都是“數(shù)組+鏈表”實(shí)現(xiàn)的泛豪，1.8之后就是“數(shù)組+（鏈表或紅黑樹(shù)）”來(lái)實(shí)現(xiàn)的了稠诲。這里我特地將“鏈表或紅黑樹(shù)”用一對(duì)括號(hào)括在一起，因?yàn)镠ashMap底層依舊是一個(gè)數(shù)組候址，然后數(shù)組中的元素是鏈表或者紅黑樹(shù)來(lái)實(shí)現(xiàn)的吕粹。
HashMap的實(shí)現(xiàn)就先介紹到這，下面就先講一下紅黑樹(shù)岗仑，然后才能理解為什么要用紅黑樹(shù)來(lái)優(yōu)化HashMap匹耕，用紅黑樹(shù)有什么好處。
一.紅黑樹(shù)介紹
1.二叉查找樹(shù)介紹
在介紹紅黑樹(shù)之前我們要先理解二叉查找樹(shù)的數(shù)據(jù)結(jié)構(gòu)荠雕。下面簡(jiǎn)單介紹一下稳其。
上面這張圖就是一個(gè)二叉查找樹(shù)。二叉查找樹(shù)有如下幾條特性
（1）.左子樹(shù)上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值炸卑。
（2）.右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值既鞠。
（3）.左、右子樹(shù)也分別為二叉排序樹(shù)
那既然他名字中是有“查找”的盖文，那么他是怎么查找的呢嘱蛋？比如我們要查找10這個(gè)元素，查找過(guò)程為：首先找到根節(jié)點(diǎn)，然后根據(jù)二叉查找樹(shù)的第一二條特性洒敏，我們知道要查找的10>9所以是在根節(jié)點(diǎn)的右邊去查找龄恋，找到13，10<13,所以接著在13的左邊找凶伙，找到11,10<11,繼續(xù)在11的左邊查找郭毕，這樣就找到了10.這其實(shí)就是二分查找的思想。最后我們要查出結(jié)果所需的最大次數(shù)就是二叉樹(shù)的高度：佟（二分查找的思想:找到數(shù)組的中間位置的元素v显押，將數(shù)組分成>v和<v兩部分，然后將v和要查找的數(shù)據(jù)進(jìn)行一個(gè)比較傻挂，如果大于v那么就在>v的部分再次進(jìn)行二分查找乘碑，否則就在<v的部分進(jìn)行二分查找，直到找到對(duì)應(yīng)的元素踊谋。）
那既然要查出結(jié)果所需的最大次數(shù)就是二叉樹(shù)的高度蝉仇，那這個(gè)高度會(huì)不會(huì)有時(shí)候很長(zhǎng)呢？
比如我們依次插入 根節(jié)點(diǎn)為9如下五個(gè)節(jié)點(diǎn)：7,6,5,4,3殖蚕。依照二叉查找樹(shù)的特性，結(jié)果會(huì)變成什么樣呢沉迹？7,6,5,4,3一個(gè)比一個(gè)小睦疫，那么就會(huì)成一條直線，也就是成為了線性的查詢鞭呕，時(shí)間復(fù)雜度變成了O（N）級(jí)別蛤育。為了解決這種情況，該紅黑樹(shù)出場(chǎng)了葫松。
2.紅黑樹(shù)介紹
紅黑樹(shù)其實(shí)就是一種自平衡的二叉查找樹(shù)瓦糕。他這個(gè)自平衡的特性就是對(duì)HashMap中鏈表可能會(huì)很長(zhǎng)做出的優(yōu)化。
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)腋么，顏色或紅色或黑色咕娄。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求:
性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色珊擂。
性質(zhì)2. 根節(jié)點(diǎn)是黑色圣勒。
性質(zhì)3 每個(gè)葉節(jié)點(diǎn)（NIL節(jié)點(diǎn)，空節(jié)點(diǎn)）是黑色的摧扇。
性質(zhì)4 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色圣贸。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
下面這棵樹(shù)就是一個(gè)典型的紅黑樹(shù)
紅黑樹(shù)那么多規(guī)則扛稽，那么在插入和刪除元素會(huì)不會(huì)破壞紅黑樹(shù)的規(guī)則呢吁峻？什么情況下會(huì)破壞？什么情況下不會(huì)？
比如我們向原紅黑樹(shù)插入為14的新節(jié)點(diǎn)就不會(huì)破壞規(guī)則
向原紅黑樹(shù)插入值為21的新節(jié)點(diǎn)就破壞了規(guī)則
那么紅黑樹(shù)是怎么維護(hù)這個(gè)二叉查找樹(shù)的自平衡性的呢用含？
紅黑樹(shù)通過(guò)“變色”和“旋轉(zhuǎn)”來(lái)維護(hù)紅黑樹(shù)的規(guī)則矮慕，變色就是讓黑的變成紅的，紅的變成黑的耕餐，旋轉(zhuǎn)又分為“左旋轉(zhuǎn)”和“右旋轉(zhuǎn)”凡傅。這個(gè)比較復(fù)雜，容易暈肠缔，我們就只要知道紅黑樹(shù)就是通過(guò)這種方式來(lái)實(shí)現(xiàn)它的自平衡性就行了夏跷。
二.HashMap中是怎么使用紅黑樹(shù)的？
JDK1.7的時(shí)候是使用一個(gè)Entry數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)明未，用key的hashcode取模來(lái)決定key會(huì)被放到數(shù)組里的位置槽华，如果hashcode相同，或者h(yuǎn)ashcode取模后的結(jié)果相同（hash collision）趟妥，那么這些key會(huì)被定位到Entry數(shù)組的同一個(gè)格子里猫态，這些key會(huì)形成一個(gè)鏈表。在hashcode特別差的情況下披摄，比方說(shuō)所有key的hashcode都相同亲雪，這個(gè)鏈表可能會(huì)很長(zhǎng)，那么put/get操作都可能需要遍歷這個(gè)鏈表疚膊。也就是說(shuō)時(shí)間復(fù)雜度在最差情況下會(huì)退化到O(n)
紅黑樹(shù)我們大致了解了义辕，他的好處就是他的自平衡性，讓他這棵樹(shù)的最大高度為2log(n+1)寓盗，n是樹(shù)的節(jié)點(diǎn)數(shù)灌砖。那么紅黑樹(shù)的復(fù)雜度就只有 O(log n)。
下面我們通過(guò)追蹤JDK1.8 HashMap的put方法的源碼來(lái)理解
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put方法調(diào)用了putVal方法
static final int TREEIFY_THRESHOLD = 8;
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//以看到這里的數(shù)組和1.7不同傀蚌，是使用了一個(gè)Node數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)基显。
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果超過(guò)了8個(gè)，那么會(huì)調(diào)用treeifyBin函數(shù)善炫，將鏈表轉(zhuǎn)換為紅黑樹(shù)撩幽。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
通過(guò)putVal方法可以看到這里的數(shù)組和1.7不同，是使用了一個(gè)Node數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)销部。那這個(gè)Node和1.7里面的Entry的區(qū)別是什么呢摸航？
HashMap中的紅黑樹(shù)節(jié)點(diǎn) 采用的是TreeNode 類
TreeNode和Entry都是Node的子類，也就說(shuō)Node可能是鏈表結(jié)構(gòu)舅桩，也可能是紅黑樹(shù)結(jié)構(gòu)酱虎。
如果插入的key的hashcode相同，那么這些key也會(huì)被定位到Node數(shù)組的同一個(gè)格子里擂涛。如果同一個(gè)格子里的key不超過(guò)8個(gè)读串，使用鏈表結(jié)構(gòu)存儲(chǔ)聊记。如果超過(guò)了8個(gè)，那么會(huì)調(diào)用treeifyBin函數(shù)恢暖，將鏈表轉(zhuǎn)換為紅黑樹(shù)排监。
先分析到這。杰捂。舆床。。嫁佳。
