1, 樹介紹

這里用的是紅黑樹，比普通的二叉樹多了個(gè)標(biāo)志符，一般的二叉樹結(jié)構(gòu)如下

     a
    /\
   /  \
  b    c

二叉樹有個(gè)缺點(diǎn)，像上面b節(jié)點(diǎn)下如果還有其他多個(gè)節(jié)點(diǎn)，c下面沒有，則這個(gè)樹是非平衡的，非平衡樹的缺點(diǎn)很明顯就是遍歷的層級(jí)可能會(huì)很多，對(duì)效率的提升可能不是很明顯，平衡樹指的的是它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1
紅黑樹也算是平衡二叉樹的一種，只是子和父之間的顏色不同，正常來講應(yīng)該由以下幾點(diǎn)組成

//結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)
private class Node{
    private Key key;//鍵
    private Value value;//值
    private Node left, right;//指向子樹的鏈接:左子樹和右子樹.
    private int N;//以該節(jié)點(diǎn)為根的子樹中的結(jié)點(diǎn)總數(shù)
    boolean color;//由其父結(jié)點(diǎn)指向它的鏈接的顏色也就是結(jié)點(diǎn)顏色.

1，每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。
2，根節(jié)點(diǎn)必須是黑色
3，紅色節(jié)點(diǎn)不能連續(xù)（也即是，紅色節(jié)點(diǎn)的孩子和父親都不能是紅色）。
4，對(duì)于每個(gè)節(jié)點(diǎn)，從該點(diǎn)至null（樹尾端）的任何路徑，都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)。

為何要紅黑樹，可能是和上面的定義有關(guān)，在插入數(shù)據(jù)時(shí)，為了保證樹的平衡型，會(huì)考慮對(duì)整個(gè)樹進(jìn)行左旋和右旋，如果想系統(tǒng)的學(xué)習(xí)紅黑樹請(qǐng)參考：https://www.cnblogs.com/CarpenterLee/p/5503882.html
這里只說一下和hashmap有關(guān)的內(nèi)容，下面是treenode的定義

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }

    /**
     * Returns root of tree containing this node.
     */
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }

先說繼承部分，LinkedHashMap.Entry<K,V> 最終又繼承了 hashmap 中的 node類，所以在hashmap中的數(shù)組中的元素可以直接是treenode

static class Entry<K,V> extends HashMap.Node<K,V> {

2, 鏈表轉(zhuǎn)換為紅黑樹

在hashmap 的put方法中有涉及, 第一個(gè)是轉(zhuǎn)換為tree，還有就是在tree中增加元素，另外就是在get方法中從tree中獲取元素

//put方法轉(zhuǎn)換為tree
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    // 如果鏈表長(zhǎng)度大于8，鏈表轉(zhuǎn)化為紅黑樹，執(zhí)行插入
    treeifyBin(tab, hash);
break;

//put方法中插入元素
else if (p instanceof TreeNode)
    // 如果p是紅黑樹類型，調(diào)用putTreeVal方式賦值
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

//get方法中獲取元素
if (first instanceof TreeNode)
    return ((TreeNode<K,V>)first).getTreeNode(hash, key);

3, put 方法轉(zhuǎn)換為tree

//入?yún)?為當(dāng)前table，入?yún)?為當(dāng)前hash，此方法是發(fā)生在鏈表已經(jīng)插入數(shù)據(jù)后，長(zhǎng)度大于8時(shí)
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果tab 不存在，或者長(zhǎng)度小于64 則進(jìn)行擴(kuò)容(暫不知道這種情況何時(shí)發(fā)生)
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //判斷 tab hash下標(biāo) 中的第一個(gè)元素不為null 
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            //將普通 node 轉(zhuǎn)為 treeNode
            TreeNode<K,V> p = replacementTreeNode(e, null);
            //第一次 執(zhí)行時(shí)為null，將第一個(gè)元素 賦值給 hd，tl表示上一個(gè)，在else里就將所有元素串聯(lián)起來了
            //這里do while 僅僅是完成了treenode 的鏈表鏈接，并沒有轉(zhuǎn)換成一棵樹
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //將鏈接轉(zhuǎn)為樹
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

上面的方法比較特殊，僅僅是將普通的node節(jié)點(diǎn)轉(zhuǎn)為treenode的鏈表結(jié)構(gòu)，并沒有直接轉(zhuǎn)為tree結(jié)構(gòu)，接著繼續(xù)看hd.treeify(tab);方法

//方法本身是 treenode 對(duì)象的一個(gè)方法，下面this 指 tab中 頭對(duì)象
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //從this 開始遍歷，聲明兩個(gè)treenode， x第一次時(shí)是this，this的下一個(gè)next，遍歷的遞增條件就是x=next
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //第一次循環(huán)中 next 和root 是同一個(gè)，但root作為樹的根節(jié)點(diǎn)，再后續(xù)的插入元素過程中可能會(huì)因?yàn)樾D(zhuǎn)而發(fā)生改變
        //next 元素就變?yōu)榱随湵?獲取next元素的源頭，保證鏈表的便利繼續(xù)進(jìn)行
        next = (TreeNode<K,V>)x.next;
        //執(zhí)行時(shí) 將當(dāng)前遍歷的左右樹置空
        x.left = x.right = null;
        //root表示第一個(gè)元素，僅有第一次遍歷時(shí)才會(huì)執(zhí)行這個(gè)方法，確定x也就是this是root根節(jié)點(diǎn)，red為黑樹
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            //拿到當(dāng)前遍歷元素的 key 和 hash
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            //內(nèi)部二次遍歷，也是從root開始遍歷，從整棵樹的根節(jié)點(diǎn)進(jìn)行大小對(duì)比，確定擺放位置
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                //如果 當(dāng)前元素hash小于 二次遍歷中的元素時(shí)，dir 為-1 ，大于為1，hash相等暫不考慮
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                //暫不知道這行的意思，應(yīng)該是hash一樣時(shí)，再對(duì)比key的大小
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                //二次遍歷中，根據(jù)大小關(guān)系對(duì)比，如果左右位置為null，則直接放置
                //否則會(huì)繼續(xù)遍歷，if語句中，p元素已經(jīng)為當(dāng)前遍歷的左右分支，可以繼續(xù)遍歷
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    //因?yàn)閜 在if中已經(jīng)完成了‘next’操作，所以xp就代表二次循環(huán)中的當(dāng)前元素，一次遍歷中當(dāng)前元素x 的parent就是xp
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //這個(gè)方法表示，對(duì)當(dāng)前樹進(jìn)行平衡操作，并返回新的root，這個(gè)時(shí)候更新root節(jié)點(diǎn)并不影響一次遍歷中的next
                    //內(nèi)部就是根據(jù)root節(jié)點(diǎn)和剛插入的x元素，來判斷是否平衡
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //root作為樹的根節(jié)點(diǎn)和最初table中的第一個(gè)元素可能已經(jīng)不是同一個(gè)，確保給定的根是其倉(cāng)的第一個(gè)節(jié)點(diǎn)
    moveRootToFront(tab, root);
}

此方法中還缺少一個(gè)點(diǎn)，在執(zhí)行此方法時(shí)，本身是一個(gè)鏈表存在，現(xiàn)在并沒有將鏈接關(guān)系結(jié)束，這一點(diǎn)可能在 moveRootToFront 或者 balanceInsertion 中有涉及，本文章主要講解hashmap，關(guān)于樹的細(xì)節(jié)暫告一段落，如果今后有時(shí)間繼續(xù)研究的話，會(huì)繼續(xù)更新