上一篇文章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)單介紹一下。

image

上面這張圖就是一個(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ù)

image

紅黑樹(shù)那么多規(guī)則，那么在插入和刪除元素會(huì)不會(huì)破壞紅黑樹(shù)的規(guī)則呢？什么情況下會(huì)破壞？什么情況下不會(huì)？

比如我們向原紅黑樹(shù)插入為14的新節(jié)點(diǎn)就不會(huì)破壞規(guī)則

image

向原紅黑樹(shù)插入值為21的新節(jié)點(diǎn)就破壞了規(guī)則

image

那么紅黑樹(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ū)別是什么呢？

image.png

HashMap中的紅黑樹(shù)節(jié)點(diǎn) 采用的是TreeNode 類

image.png

image.png

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ù)。