空閑時(shí)間，根了一下最新HashMap源碼，這里記錄一下。如有錯(cuò)漏，請(qǐng)指正。

篇幅太長(zhǎng)，因此這里分了兩篇文章。

主要從以下功能切入：

• 構(gòu)造函數(shù)
• put
• get
• remove

構(gòu)造函數(shù)：

//默認(rèn)構(gòu)造函數(shù),默認(rèn)初始容量為16 ，默認(rèn)加載因子為0.75
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

//指定初始容量的構(gòu)造函數(shù)，默認(rèn)加載因子為0.75
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//指定初始容量和加載因子的構(gòu)造函數(shù)
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //若初始容量大于最大容量，則初始容量為最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    
    //若加載因子小于0或NaN即Not a number(0.0f/0.0f的值就是NaN)的話，拋出異常
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    //初始化閾值，該值用于判斷何時(shí)需要擴(kuò)容(resize)
    this.threshold = tableSizeFor(initialCapacity);
}


/**
* 該方法用于保證數(shù)組長(zhǎng)度為2的n次方
* 
* 問(wèn): 為何數(shù)組長(zhǎng)度一定要為2的n次方？
* 我們知道2的n次方=1+n個(gè)0，而2的n次方-1  實(shí)際就是n個(gè)1
* 在HashMap中，我們需要根據(jù)key的hash值取數(shù)組中的下標(biāo)，為了較少碰撞（即key在table中位置相同），每個(gè)key在數(shù) * 組中的下標(biāo)可以通過(guò)以下公式獲取：
* int index = key.hash % table.length;
* 但是由于%運(yùn)算效率不高，因此使用效率高的與運(yùn)算來(lái)取代%運(yùn)算
* int index =  (table.length - 1) & key.hash; 
* 這里又要回到為什么要保證數(shù)組長(zhǎng)度為2的n次方，因?yàn)?的n次方-1=n個(gè)1，例如這里數(shù)組長(zhǎng)度為2?=16，那么：
* int index = 1111 & key.hash; 
* 這樣既保證了均勻性，index也不會(huì)超過(guò)數(shù)組長(zhǎng)度，同時(shí)效率也提高了。
* 兩種運(yùn)算效率的對(duì)比可自行測(cè)試。
* */
static final int tableSizeFor(int cap) {
    //>>> : 無(wú)符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊，即這里保證數(shù)組長(zhǎng)度為正數(shù)
    //>> ：帶符號(hào)右移，正數(shù)右移高位補(bǔ)0，負(fù)數(shù)右移高位補(bǔ)1
    
    //以下運(yùn)算為何可以保證返回值為2的n次方呢？
    //我們隨便拿個(gè)數(shù)字cap=190，那么n = 189，二進(jìn)制為：10111101
    //10111101 |= 01011110 結(jié)果為： 11111111 = 2的8次方-1
    //接著后面的|=已經(jīng)無(wú)需在意，因此這里189的二進(jìn)制所有位都為1了
    //最后返回值為n+1即2的8次方 = 256
    //經(jīng)上面例子得出結(jié)果：通過(guò)將cap-1的二進(jìn)制最高位1后所有位都轉(zhuǎn)為1，最后再加上1就是我們想要的2的n次方了
    
    //這里再詳細(xì)說(shuō)一下下面算法：
    int n = cap - 1;
        n |= n >>> 1; //將最高位后1位 置為1
        n |= n >>> 2; //將最高位后2位 置為1
        n |= n >>> 4; //由于已經(jīng)將前4位置為1了，這時(shí)n>>>4用于轉(zhuǎn)后4位
        n |= n >>> 8; //由于已經(jīng)將前8位置為1了，這時(shí)n>>>8用于轉(zhuǎn)后8位
        n |= n >>> 16; //由于已經(jīng)將前16位置為1了，這時(shí)n>>>16用于轉(zhuǎn)后16位
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

//根據(jù)指定map構(gòu)造一個(gè)新的HashMap，默認(rèn)加載因子為0.75
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

//將map內(nèi)容拷貝到本地HashMap，關(guān)于evict參數(shù)，HashMap中用于判斷數(shù)組是否處于創(chuàng)建模式
//evict = false的話，處于創(chuàng)建模式
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size(); //獲取map大小
    if (s > 0) {  //map 非空
        if (table == null) { //若當(dāng)前數(shù)組為空，根據(jù)map大小獲取數(shù)組閾值
            float ft = ((float)s / loadFactor) + 1.0F;
            int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                     (int)ft : MAXIMUM_CAPACITY);
            if (t > threshold)
                threshold = tableSizeFor(t);
        }
        else if (s > threshold) //否則當(dāng)前數(shù)組為空且map大小比閾值大，需要擴(kuò)容才能放得下map
            resize(); //關(guān)于擴(kuò)容函數(shù)，后面會(huì)分析
        //處理好數(shù)組號(hào)，將map的所有值都拷貝到HashMap
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

put相關(guān)函數(shù)

//對(duì)外接口，put一個(gè)key-value
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//根據(jù)傳遞的key對(duì)象獲取hash值
static final int hash(Object key) {
    //我們上面說(shuō)過(guò)，要盡可能減少碰撞(不同key在數(shù)組中處于相同位置)，保證均勻性以滿足散列特征。
    int h;
    //key的hash值的高16位不變，低16位與高16位異或作為key的最終hash值
    //我們前面知道數(shù)組長(zhǎng)度總是為2的n次方，并且最后根據(jù)key的hash值取數(shù)組下標(biāo)的時(shí)候公式為:
    //int index = (table.length - 1) & hash;
    //假如key.hashCode() = 1111-0001-1111-1111-0111-1110-1111-1000，數(shù)組長(zhǎng)度為2?=16=0001-0110
    //最高的24位都沒(méi)有參與運(yùn)算，因?yàn)閿?shù)組長(zhǎng)度的限制(我們事實(shí)也很難會(huì)用到2^30這個(gè)最大容量)。因此，
    //大多數(shù)情況下hash值的高位都沒(méi)有參與運(yùn)算(例子這里只有低5位參與運(yùn)算)，這樣的話很容易產(chǎn)生碰撞，
    //因此設(shè)計(jì)者通過(guò)將高16位與低16位異或來(lái)減少這種影響
    //更詳細(xì)說(shuō)明可參考:https://www.cnblogs.com/zhengwang/p/8136164.html
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}


//內(nèi)部實(shí)現(xiàn)類，put一個(gè)key-value
//hash:key的哈希值
//key: key值
//value: value值
//onlyIfAbsent: true的話，不改變?cè)疽呀?jīng)存在的key-value
//evict: 關(guān)于evict參數(shù)，evict = false的話，table處于創(chuàng)建模式
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
     //若數(shù)組為空或者數(shù)組長(zhǎng)度為0則擴(kuò)容
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length; 
    
    //根據(jù)hash獲取數(shù)組中的下標(biāo)，若數(shù)組中不存在節(jié)點(diǎn)的話，new一個(gè)節(jié)點(diǎn)并放到對(duì)應(yīng)數(shù)組下標(biāo)
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    
    //若數(shù)組中已經(jīng)存在節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)為tab[(n - 1) & hash]
    else { 
        Node<K,V> e; K k;
        //若當(dāng)前節(jié)點(diǎn)與要插入的key-value的key相等的話，將e賦值為當(dāng)前節(jié)點(diǎn)p
        //這里的key相等為以下判斷，即要插入的key-value的key的hash值與當(dāng)前節(jié)點(diǎn)的hash值相等
        //且k=當(dāng)前節(jié)點(diǎn)的key與key相等或要插入的key-value的key.equals(k)為true。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        
        //若當(dāng)前節(jié)點(diǎn)為紅黑樹(shù)節(jié)點(diǎn)的話，e=紅黑樹(shù)節(jié)點(diǎn)的putTreeVal方法的返回值
        //putTreeVal后面會(huì)細(xì)講
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        
        //下面代碼表示循環(huán)鏈表，找出鏈表與要插入的key-value的key相等的節(jié)點(diǎn)
        else {
            for (int binCount = 0; ; ++binCount) {
                //若在鏈表中沒(méi)有找到對(duì)應(yīng)key(最后節(jié)點(diǎn).next為null)的節(jié)點(diǎn)，跳出循環(huán)
                if ((e = p.next) == null) {
                    //new一個(gè)節(jié)點(diǎn)，并插到鏈表最后面
                    p.next = newNode(hash, key, value, null);
                    
                    //判斷當(dāng)前鏈表長(zhǎng)度是否比紅黑樹(shù)定義的閾值大，是的話，則開(kāi)始將鏈表節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹(shù)節(jié)點(diǎn)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                
                //若在鏈表中找到了與要插入的key-value的key相等的節(jié)點(diǎn)，跳出循環(huán)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                
                //將next賦給當(dāng)前節(jié)點(diǎn)，用于循環(huán)
                p = e;
            }
        }
        
        //在鏈表中找到了與要插入的key-value的key相等的節(jié)點(diǎn)，例如，相同一個(gè)key就會(huì)有相同的節(jié)點(diǎn)
        if (e != null) { 
            V oldValue = e.value;
            //判斷onlyIfAbsent=false或原本key-value的值為空的時(shí)候則賦為最新值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //LinkedHashMap后期操作函數(shù)，HashMap暫未實(shí)現(xiàn)
            return oldValue; //返回舊的值
        }
    }
    
    ++modCount; //增加修改次數(shù)
    
    //判斷是否需要擴(kuò)容
    if (++size > threshold)
        resize();
    
    afterNodeInsertion(evict);//LinkedHashMap后期操作函數(shù)，HashMap暫未實(shí)現(xiàn)
    return null;
}

//將鏈表節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹(shù)節(jié)點(diǎn)
//tab: 鏈表節(jié)點(diǎn)數(shù)組
//hash: 當(dāng)前要插入key的hash值
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    
    //若tab為null或數(shù)組長(zhǎng)度小于紅黑樹(shù)的最小容量的話，沒(méi)有必要將鏈表轉(zhuǎn)為紅黑樹(shù)，直接擴(kuò)容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    
    //e = tab[index = (n - 1) & hash]) 取數(shù)組中的節(jié)點(diǎn)即鏈表中的第一個(gè)節(jié)點(diǎn)
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);//將鏈表節(jié)點(diǎn)轉(zhuǎn)為紅黑樹(shù)節(jié)點(diǎn)
            if (tl == null)
                hd = p; //記錄紅黑樹(shù)頭節(jié)點(diǎn)即鏈表中第一個(gè)節(jié)點(diǎn)
            else {
                //新增一個(gè)雙向鏈表
                p.prev = tl; //設(shè)置當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
                tl.next = p; //設(shè)置上一個(gè)節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            }
            tl = p; //將上一個(gè)節(jié)點(diǎn)賦值為當(dāng)前節(jié)點(diǎn)，用于循環(huán)，直到鏈表最后一個(gè)
        } while ((e = e.next) != null);
        
        //若頭節(jié)點(diǎn)非空，則從紅黑樹(shù)頭節(jié)點(diǎn)開(kāi)始將鏈表轉(zhuǎn)化為紅黑樹(shù)結(jié)構(gòu)
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

//從當(dāng)前節(jié)點(diǎn)開(kāi)始將鏈表節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null; //根節(jié)點(diǎn)
    //從當(dāng)前節(jié)點(diǎn)開(kāi)始，進(jìn)行結(jié)構(gòu)轉(zhuǎn)換
    //x為當(dāng)前鏈表節(jié)點(diǎn)
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        //獲取當(dāng)前節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null; //設(shè)置左右節(jié)點(diǎn)為null
        
        //若根節(jié)點(diǎn)為空，則將當(dāng)前節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
        //并且parent設(shè)置為null，因?yàn)楦?jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)
        //并且根節(jié)點(diǎn)一定為黑色
        if (root == null) {
            x.parent = null;
            x.red = false;
            root = x;
        }
        
        //若根節(jié)點(diǎn)非空
        else {
            K k = x.key; //當(dāng)前鏈表節(jié)點(diǎn)的key
            int h = x.hash; //當(dāng)前鏈表節(jié)點(diǎn)的hash值
            Class<?> kc = null; //聲明key的class
            
            //從根節(jié)點(diǎn)開(kāi)始進(jìn)行構(gòu)成紅黑樹(shù)結(jié)構(gòu)
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; //聲明方向，當(dāng)前節(jié)點(diǎn)hash值
                K pk = p.key; //聲明當(dāng)前節(jié)點(diǎn)的key
                
                //若當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的hash比鏈表節(jié)點(diǎn)的hash值大的話，則將鏈表節(jié)點(diǎn)放在紅黑樹(shù)節(jié)點(diǎn)的左邊
                if ((ph = p.hash) > h)
                    dir = -1; 
                //若當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的hash比鏈表節(jié)點(diǎn)的hash值小的話，則將鏈表節(jié)點(diǎn)放在紅黑樹(shù)節(jié)點(diǎn)的右邊
                else if (ph < h)
                    dir = 1;
                
                //若當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的hash與鏈表節(jié)點(diǎn)的hash值相等的話需要再進(jìn)行判斷(即判斷兩個(gè)key是否相同)
                //若kc為null并且當(dāng)前鏈表節(jié)點(diǎn)的key的class沒(méi)有實(shí)現(xiàn)comparable接口
                //或者kc不為null并且當(dāng)前鏈表節(jié)點(diǎn)的key的class實(shí)現(xiàn)了comparable，則通過(guò)比較得出方向
                //否則將調(diào)用tieBreakOrder(k, pk)獲取一個(gè)必定為左或右的方向
                else if ((kc == null && (kc = comparableClassFor(k)) == null) 
                         || (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                //聲明xp=當(dāng)前紅黑樹(shù)節(jié)點(diǎn)
                TreeNode<K,V> xp = p;
                //根據(jù)方向獲取當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的左節(jié)點(diǎn)或右節(jié)點(diǎn)
                //若為空的話，則將當(dāng)前鏈表節(jié)點(diǎn)x插入到當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的左邊或右邊并且退出循環(huán)
                //否則繼續(xù)循環(huán)
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp; //設(shè)置當(dāng)前鏈表節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前紅黑樹(shù)節(jié)點(diǎn)
                    
                    if (dir <= 0) 
                        xp.left = x; //當(dāng)前鏈表節(jié)點(diǎn)x為當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的左節(jié)點(diǎn)
                    else
                        xp.right = x; //當(dāng)前鏈表節(jié)點(diǎn)x為當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的右節(jié)點(diǎn)
                    
                    //插入后需要調(diào)整紅黑樹(shù)平衡，并且將平衡后返回的節(jié)點(diǎn)作為根節(jié)點(diǎn)
                    root = balanceInsertion(root, x); 
                    break;
                }
            }
        }
    }
    
    moveRootToFront(tab, root);
}

//根據(jù)對(duì)象獲取實(shí)現(xiàn)Comparable的接口類
static Class<?> comparableClassFor(Object x) {
    //implement Comparable接口
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        
        //若class為String.class的話則直接返回，因?yàn)镾tring已實(shí)現(xiàn)Comparable<String>接口
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        
        //獲取class實(shí)現(xiàn)的接口
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                //遍歷所有接口
                //判斷是否繼承Comparable接口
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) 
                    //是的話直接返回class
                    return c;
            }
        }
    }
    return null;
}

//根據(jù)class比較兩個(gè)對(duì)象
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

//該方法一定會(huì)返回一個(gè)要么為1，要么為-1的值
//若a為null, 或者b為null，或者a的class name和b的class name相等
//則直接返回a和b的System.identityHashCode值相比較，若還是一樣的話，則返回-1
//否則返回1
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

//插入一個(gè)key-value后需要重新調(diào)整紅黑樹(shù)結(jié)構(gòu)，使其達(dá)到平衡，即保證log(n)的時(shí)間復(fù)雜度
//root: 根節(jié)點(diǎn)
//x：要插入的紅黑樹(shù)節(jié)點(diǎn)
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    x.red = true; //紅黑樹(shù)規(guī)則：新插入的節(jié)點(diǎn)顏色總是紅色的
    
    //聲明
    //xp: 要插入節(jié)點(diǎn)的父節(jié)點(diǎn)
    //xpp: 要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)
    //xppl: 要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)
    //xppr：要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        //若父節(jié)點(diǎn)為null，則當(dāng)前要插入的節(jié)點(diǎn)x為根節(jié)點(diǎn)
        //將根節(jié)點(diǎn)置為黑色，返回當(dāng)前要插入的節(jié)點(diǎn)x
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        
        //若父節(jié)點(diǎn)為黑色或者父節(jié)點(diǎn)的父節(jié)點(diǎn)為null的話，返回根節(jié)點(diǎn)
        //因?yàn)楫?dāng)前父節(jié)點(diǎn)即為根節(jié)點(diǎn)，且x節(jié)點(diǎn)為紅色，沒(méi)有違反紅黑樹(shù)規(guī)則
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        
        //往下執(zhí)行： 父節(jié)點(diǎn)為紅色 
        //若父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)
        if (xp == (xppl = xpp.left)) {
            //爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)不等于null且為紅色
            //滿足紅黑樹(shù)插入平衡情況一: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)和其叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))均為紅色
            //則需要執(zhí)行變色操作
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false; //將爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)置為黑色
                xp.red = false; //將父節(jié)點(diǎn)置為黑色
                xpp.red = true; //將爺爺節(jié)點(diǎn)置為紅色
                x = xpp; //將當(dāng)前節(jié)點(diǎn)賦值為爺爺節(jié)點(diǎn)，再進(jìn)行平衡操作
            }
            else {
                //若當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)
                //滿足紅黑樹(shù)插入平衡情況二: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))是黑               //色的且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)。
                //由于當(dāng)前父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)，因此這里需要將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)作為新的節(jié)點(diǎn)，
                //以新的當(dāng)前節(jié)點(diǎn)為支點(diǎn)做左旋操作
                if (x == xp.right) {
                    //將當(dāng)前節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)且執(zhí)行左旋操作
                    root = rotateLeft(root, x = xp);
                    //重新設(shè)置爺爺節(jié)點(diǎn)和父節(jié)點(diǎn)
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                
                //若父節(jié)點(diǎn)不為空將其設(shè)置為黑色
                //滿足紅黑樹(shù)插入平衡情況三: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))                 //是黑色的，且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)。
                //由于當(dāng)前父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)，因此這里需要將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)涂黑，
                //爺爺節(jié)點(diǎn)涂紅，以爺爺節(jié)點(diǎn)為支點(diǎn)做右旋操作
                if (xp != null) {
                    xp.red = false; 
                    
                    //若爺爺節(jié)點(diǎn)不為空，將其設(shè)置為紅色并且執(zhí)行右旋操作
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        //若父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)
        else {
            //若要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)非空且為紅色
            //滿足紅黑樹(shù)插入平衡情況一: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)和其叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))均為紅色
            //則需要執(zhí)行變色操作
            if (xppl != null && xppl.red) {
                xppl.red = false; //將要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置為黑色
                xp.red = false; //將父節(jié)點(diǎn)設(shè)置為黑色
                xpp.red = true; //將爺爺節(jié)點(diǎn)設(shè)置為紅色
                x = xpp; //將當(dāng)前節(jié)點(diǎn)賦值為爺爺節(jié)點(diǎn)，再進(jìn)行平衡操作
            }
            //若要插入節(jié)點(diǎn)的爺爺節(jié)點(diǎn)的左節(jié)點(diǎn)為空或者為黑色
            else {
                //若當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)
                //滿足紅黑樹(shù)插入平衡情況二: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))是黑               //色的且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的右子節(jié)點(diǎn)。
                //由于當(dāng)前父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)，因此這里需要將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)作為新的節(jié)點(diǎn)，
                //以新的當(dāng)前節(jié)點(diǎn)為支點(diǎn)做右旋操作
                if (x == xp.left) {
                    root = rotateRight(root, x = xp); //將當(dāng)前節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)且執(zhí)行右旋操作
                    
                    //重新設(shè)置爺爺節(jié)點(diǎn)和父節(jié)點(diǎn)
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                
                //若父節(jié)點(diǎn)不為空將其設(shè)置為黑色
                //滿足紅黑樹(shù)插入平衡情況三: 插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色的，叔叔節(jié)點(diǎn)(爺爺節(jié)點(diǎn)的另一個(gè)子節(jié)點(diǎn))                 //是黑色的，且插入節(jié)點(diǎn)是其父節(jié)點(diǎn)的左子節(jié)點(diǎn)。
                //由于當(dāng)前父節(jié)點(diǎn)為爺爺節(jié)點(diǎn)的右節(jié)點(diǎn)，因此這里需要將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)涂黑，
                //爺爺節(jié)點(diǎn)涂紅，以爺爺節(jié)點(diǎn)為支點(diǎn)做左旋操作
                if (xp != null) {
                    xp.red = false; 
                    
                    //若爺爺節(jié)點(diǎn)非空
                    if (xpp != null) {
                        xpp.red = true; //爺爺節(jié)點(diǎn)設(shè)置為紅色
                        root = rotateLeft(root, xpp); //將爺爺節(jié)點(diǎn)執(zhí)行左旋操作
                    }
                }
            }
        }
    }
}

//左旋操作
//root: 紅黑樹(shù)根節(jié)點(diǎn)
//p：當(dāng)前節(jié)點(diǎn)
/*
* 左旋示意圖：對(duì)節(jié)點(diǎn)x進(jìn)行左旋
*       p                        p
*      /                        /
*     x                        y
*   /   \                    /   \
* lx     y      ----->      x    ry
*      /   \              /   \
*    ly      ry          lx    ly
**/
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    //聲明r: 當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
    //pp：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
    //rl: 當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)的左節(jié)點(diǎn)
    TreeNode<K,V> r, pp, rl; 
    
    //若當(dāng)前節(jié)點(diǎn)不為null且當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)不為空
    if (p != null && (r = p.right) != null) {
        //將當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)的左節(jié)點(diǎn)
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        
        //將當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
        //若父節(jié)點(diǎn)為null，則設(shè)置當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)為根節(jié)點(diǎn)，同時(shí)設(shè)置為黑色
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        
        //當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)非null且當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)
        else if (pp.left == p)
            //父節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
            pp.left = r;
        
        //當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)
        else
            //將父節(jié)點(diǎn)的右節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)
            pp.right = r;
        
        //將當(dāng)前節(jié)點(diǎn)設(shè)置為右節(jié)點(diǎn)的左節(jié)點(diǎn)
        r.left = p;
        
        //將當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為右節(jié)點(diǎn)
        p.parent = r;
    }
    return root;
}

//右旋操作
//root: 紅黑樹(shù)根節(jié)點(diǎn)
//p：當(dāng)前節(jié)點(diǎn)
/*
 * 右轉(zhuǎn)示意圖：對(duì)節(jié)點(diǎn)y進(jìn)行右旋
 *         p                    p
 *        /                    /
 *       y                    x
 *     /   \                /   \
 *    x     ry   ----->    lx    y
 *  /   \                      /   \
 * lx    rx                   rx   ry
 */
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    //聲明l: 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
    //pp：當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
    //lr: 當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)
    TreeNode<K,V> l, pp, lr;
    
    //當(dāng)前節(jié)點(diǎn)非null且左節(jié)點(diǎn)非null
    if (p != null && (l = p.left) != null) {
        //若當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)非null，則當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)的右節(jié)點(diǎn)的父節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        
        //將當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
        //若父節(jié)點(diǎn)為null，則設(shè)置當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)為根節(jié)點(diǎn)，同時(shí)設(shè)置為黑色
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        
        //當(dāng)前節(jié)點(diǎn)父節(jié)點(diǎn)非null且當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)
        else if (pp.right == p)
            //父節(jié)點(diǎn)的右節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
            pp.right = l;
        
        //當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)
        else
            //將父節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置為當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)
            pp.left = l;
        
        //設(shè)置左節(jié)點(diǎn)的右節(jié)點(diǎn)為當(dāng)前節(jié)點(diǎn)
        l.right = p;
        
        //設(shè)置當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)為左節(jié)點(diǎn)
        p.parent = l;
    }
    return root;
}

//用于確保紅黑樹(shù)中的根節(jié)點(diǎn)為數(shù)組中的下標(biāo)節(jié)點(diǎn)(頭節(jié)點(diǎn))
//tab: 節(jié)點(diǎn)數(shù)組
//root: 紅黑樹(shù)根節(jié)點(diǎn)
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    if (root != null && tab != null && (n = tab.length) > 0) {
        int index = (n - 1) & root.hash; //獲取紅黑樹(shù)節(jié)點(diǎn)在數(shù)組中的下標(biāo)
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index]; //獲取數(shù)組下標(biāo)中的節(jié)點(diǎn)(頭節(jié)點(diǎn))
        
        if (root != first) { //若紅黑樹(shù)的根節(jié)點(diǎn)不是頭節(jié)點(diǎn)的話
            Node<K,V> rn; //聲明紅黑樹(shù)根節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            tab[index] = root; //設(shè)置數(shù)組下標(biāo)的節(jié)點(diǎn)(頭節(jié)點(diǎn))為紅黑樹(shù)根節(jié)點(diǎn)
            TreeNode<K,V> rp = root.prev; //聲明紅黑樹(shù)根節(jié)點(diǎn)的鏈表的前一個(gè)節(jié)點(diǎn)rp
            
            if ((rn = root.next) != null) //如果紅黑樹(shù)根節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)不為空的話
                //設(shè)置紅黑樹(shù)根節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)為根節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
                ((TreeNode<K,V>)rn).prev = rp; 
            
            
            if (rp != null) //若根節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)不為空 
                rp.next = rn; //將根節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)設(shè)置根節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            
            
            //若頭節(jié)點(diǎn)不為null
            if (first != null) 
                first.prev = root; //將頭結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)設(shè)置為紅黑樹(shù)根節(jié)點(diǎn)
            
            root.next = first; //紅黑樹(shù)根節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)設(shè)置為頭結(jié)點(diǎn)
            root.prev = null;
        }
        //檢查紅黑樹(shù)是否正常
        assert checkInvariants(root);
    }
}

//遞歸檢查紅黑樹(shù)是否正常

//紅黑樹(shù)基本規(guī)則：
//1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色的；
//2.根節(jié)點(diǎn)總是黑色的；
//3.如果節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的(反之不一定)，(也就是從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))；
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
    //聲明父節(jié)點(diǎn)，左節(jié)點(diǎn)，右節(jié)點(diǎn)，前節(jié)點(diǎn)，后節(jié)點(diǎn)
    TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
    tb = t.prev, tn = (TreeNode<K,V>)t.next;
    
    //若前節(jié)點(diǎn)不為null且前節(jié)點(diǎn)的后節(jié)點(diǎn)不等于當(dāng)前節(jié)點(diǎn)，證明和鏈表中位置不一致，異常
    if (tb != null && tb.next != t)
        return false;
    
    //若后節(jié)點(diǎn)不為null且后節(jié)點(diǎn)的前節(jié)點(diǎn)不等于當(dāng)前節(jié)點(diǎn)，證明和鏈表中位置不一致，異常
    if (tn != null && tn.prev != t)
        return false;
    
    //若父節(jié)點(diǎn)不為null，且當(dāng)前節(jié)點(diǎn)不是父節(jié)點(diǎn)的左節(jié)點(diǎn)又不是父節(jié)點(diǎn)的右節(jié)點(diǎn)，異常
    if (tp != null && t != tp.left && t != tp.right)
        return false;
    
    //若當(dāng)前左節(jié)點(diǎn)不為null且左節(jié)點(diǎn)的父節(jié)點(diǎn)不等于當(dāng)前節(jié)點(diǎn)或者左節(jié)點(diǎn)的hash值比當(dāng)前節(jié)點(diǎn)的hash值大的話，異常
    if (tl != null && (tl.parent != t || tl.hash > t.hash))
        return false;
    
    //若當(dāng)前右節(jié)點(diǎn)不為null且右節(jié)點(diǎn)的父節(jié)點(diǎn)不等于當(dāng)前節(jié)點(diǎn)或右節(jié)點(diǎn)的hash值比當(dāng)前節(jié)點(diǎn)的hash值小的話，異常
    if (tr != null && (tr.parent != t || tr.hash < t.hash))
        return false;
    
    //若當(dāng)前節(jié)點(diǎn)為紅色，且左節(jié)點(diǎn)不為空且為紅色，且右節(jié)點(diǎn)不為空且為紅色，異常
    if (t.red && tl != null && tl.red && tr != null && tr.red)
        return false;
    
    //若左節(jié)點(diǎn)不為nul則遞歸判斷左節(jié)點(diǎn)
    if (tl != null && !checkInvariants(tl))
        return false;
    
     //若左節(jié)點(diǎn)不為nul則遞歸判斷右節(jié)點(diǎn)
    if (tr != null && !checkInvariants(tr))
        return false;
    
    //紅黑樹(shù)結(jié)構(gòu)正常，返回true
    return true;
}

//紅黑樹(shù)的put操作
//map: 要put的hash map
//tab: 數(shù)組
//h: 要put的key-value的key的hash值
//k: 要put的key-value的key
//v: 要put的key-value的value
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null; //聲明key的class臨時(shí)變量
    boolean searched = false; //聲明是否搜索過(guò)的bool臨時(shí)變量
    TreeNode<K,V> root = (parent != null) ? root() : this; //獲取根節(jié)點(diǎn)
    
    //p為當(dāng)前節(jié)點(diǎn)，從當(dāng)前紅黑樹(shù)的根節(jié)點(diǎn)遍歷，找到要put的kay-value的key的對(duì)應(yīng)節(jié)點(diǎn)或者
    //得到新節(jié)點(diǎn)在紅黑樹(shù)的位置
    for (TreeNode<K,V> p = root;;) { 
        int dir, ph; K pk; //聲明方向，當(dāng)前節(jié)點(diǎn)的hash值，當(dāng)前節(jié)點(diǎn)的key
        
        //若要put的key-value的key的hash值比當(dāng)前節(jié)點(diǎn)hash值小
        if ((ph = p.hash) > h)
            dir = -1; //在當(dāng)前節(jié)點(diǎn)左邊
        
        //若要put的key-value的key的hash值比當(dāng)前節(jié)點(diǎn)hash值大
        else if (ph < h)
            dir = 1; //在當(dāng)前節(jié)點(diǎn)右邊
        
        //若要put的key-value的key與當(dāng)前紅黑樹(shù)節(jié)點(diǎn)的key相等，直接返回當(dāng)前節(jié)點(diǎn)
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        
        //若還沒(méi)得到方向的話，下面代碼保證得到一個(gè)方向值
        else if ((kc == null &&
                  //若key的class實(shí)現(xiàn)了Comparable接口的話，直接比較兩個(gè)key，得到方向
                  (kc = comparableClassFor(k)) == null) || 
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //判斷是否搜索過(guò)
            //該方法代表在put的時(shí)候會(huì)從紅黑樹(shù)中查找對(duì)應(yīng)的key是否存在，若存在的話，
            //直接返回在紅黑樹(shù)中找到的節(jié)點(diǎn)。否則會(huì)將put的key-value封裝成一個(gè)紅黑樹(shù)節(jié)點(diǎn)
            //插入到紅黑樹(shù)中
            if (!searched) {
                TreeNode<K,V> q, ch; //聲明查找到的節(jié)點(diǎn)q和臨時(shí)節(jié)點(diǎn)遍歷ch
                searched = true; //將搜索標(biāo)識(shí)置為true
                
                //若當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)不為null并且從左節(jié)點(diǎn)開(kāi)始查找節(jié)點(diǎn)，查找到的節(jié)點(diǎn)不為空的話
                //返回查找到的節(jié)點(diǎn)
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) 
                    
                    ||
                    
                    //或
                   //若當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)不為null并且從右節(jié)點(diǎn)開(kāi)始查找節(jié)點(diǎn)，查找到的節(jié)點(diǎn)不為空的話
                    //返回查找到的節(jié)點(diǎn)
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            
            //該方法一定會(huì)返回一個(gè)要么為1，要么為-1的值(即一定會(huì)得到一個(gè)左/右的方向)
            dir = tieBreakOrder(k, pk);
        }

        //程序執(zhí)行到這里證明要新創(chuàng)建一個(gè)紅黑樹(shù)節(jié)點(diǎn)，并將其插入的紅黑樹(shù)中
        
        TreeNode<K,V> xp = p;  //聲明父節(jié)點(diǎn)
        //判斷要插入的方向
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next; //聲明父節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)
            
            //根據(jù)key的hash值、key、value、父節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)創(chuàng)建一個(gè)紅黑樹(shù)節(jié)點(diǎn)
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); 
            
            //新節(jié)點(diǎn)在父節(jié)點(diǎn)的位置
            //即為父節(jié)點(diǎn)的左節(jié)點(diǎn)或右節(jié)點(diǎn)
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            
            //父節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)為新節(jié)點(diǎn)
            xp.next = x;
            
            //新節(jié)點(diǎn)的父節(jié)點(diǎn)和新節(jié)點(diǎn)的前節(jié)點(diǎn)都為父節(jié)點(diǎn)
            x.parent = x.prev = xp;
            
            //如果父節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)不為null的話，將父節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)設(shè)置為新節(jié)點(diǎn)
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            
            //重新平衡紅黑樹(shù)后檢查樹(shù)結(jié)構(gòu)再移動(dòng)根節(jié)點(diǎn)為數(shù)組下標(biāo)節(jié)點(diǎn)(頭節(jié)點(diǎn))
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

//返回包含此節(jié)點(diǎn)的紅黑樹(shù)的根節(jié)點(diǎn)
final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

//根據(jù)key的hash值，key，key的class，從紅黑樹(shù)的當(dāng)前節(jié)點(diǎn)開(kāi)始，找到對(duì)應(yīng)的節(jié)點(diǎn)
//h: key的hash值
//k: key
//kc: key的class
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this; //賦值當(dāng)前節(jié)點(diǎn)
    
    do {
        int ph, dir; K pk; //聲明當(dāng)前key的hash值，方向，key
        TreeNode<K,V> pl = p.left, pr = p.right, q; //聲明當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，右節(jié)點(diǎn)，q為查找節(jié)點(diǎn)
        
        if ((ph = p.hash) > h)
            p = pl; //如果當(dāng)前節(jié)點(diǎn)的hash值大于key的hash值，則將當(dāng)前節(jié)點(diǎn)賦值為左節(jié)點(diǎn)繼續(xù)查找
        
        else if (ph < h)
            p = pr; //如果當(dāng)前節(jié)點(diǎn)的hash值小于key的hash值，則將當(dāng)前節(jié)點(diǎn)賦值為右節(jié)點(diǎn)繼續(xù)查找
        
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p; //如果hash值等于key的hash值，返回當(dāng)前節(jié)點(diǎn)，證明找到了
        
        else if (pl == null) //如果左節(jié)點(diǎn)為null，則將當(dāng)前節(jié)點(diǎn)當(dāng)前賦值為右節(jié)點(diǎn)繼續(xù)查找
            p = pr;
        
        else if (pr == null) //如果右節(jié)點(diǎn)為null，則將當(dāng)前節(jié)點(diǎn)當(dāng)前賦值為左節(jié)點(diǎn)繼續(xù)查找
            p = pl;
        
        //若key的class實(shí)現(xiàn)了Comparable接口的話，通過(guò)Comparable接口比較兩個(gè)key的大小
        //將當(dāng)前節(jié)點(diǎn)賦值為對(duì)應(yīng)的方向的節(jié)點(diǎn)
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        
        //若在上面接口得到kc后，這里通過(guò)find再尋找一次
        //若不為null，證明已找到對(duì)應(yīng)key的節(jié)點(diǎn)，返回
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        
        //否當(dāng)前節(jié)點(diǎn)直接賦值為左節(jié)點(diǎn)再繼續(xù)查找
        else
            p = pl;
        
    } while (p != null); //若當(dāng)前節(jié)點(diǎn)不為null，繼續(xù)查找
    
    return null;
}