jdk1.8之后對(duì)HashMap做了很大的優(yōu)化力奋，把原有的（數(shù)組+鏈表）結(jié)構(gòu)改成了（數(shù)組+鏈表+紅黑樹）凡资。
當(dāng)鏈表的長度大于8的時(shí)候渴肉，自動(dòng)轉(zhuǎn)換成紅黑樹冗懦。把原來的Entry改為節(jié)點(diǎn)Node。jdk1.8中HashMap的數(shù)據(jù)結(jié)構(gòu)如下：

image.png

基本屬性

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)容量16
 
/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;    // 最大容量
 
/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認(rèn)負(fù)載因子0.75
 
/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8; // 鏈表節(jié)點(diǎn)轉(zhuǎn)換紅黑樹節(jié)點(diǎn)的閾值, 9個(gè)節(jié)點(diǎn)轉(zhuǎn)
 
/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6;   // 紅黑樹節(jié)點(diǎn)轉(zhuǎn)換鏈表節(jié)點(diǎn)的閾值, 6個(gè)節(jié)點(diǎn)轉(zhuǎn)
 
/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64; // 轉(zhuǎn)紅黑樹時(shí), table的最小長度
 
/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> {  // 基本hash節(jié)點(diǎn), 繼承自Entry
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
 
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
 
    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }
 
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }
 
    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
 
    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}
 
/**
 * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
 * extends Node) so can be used as extension of either regular or
 * linked node.
 */
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {// 紅黑樹節(jié)點(diǎn)
    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);
    }
    // ...
}

定位節(jié)點(diǎn)下標(biāo)

計(jì)算hash值的運(yùn)算比1.7的更簡單仇祭。計(jì)算節(jié)點(diǎn)下標(biāo)和1.7的算法是一樣的披蕉，這里就不詳細(xì)描述，具體請(qǐng)看我的上一篇文章：http://www.reibang.com/p/2d8647961ab5

// 代碼1
static final int hash(Object key) { // 計(jì)算key的hash值
    int h;
    // 1.先拿到key的hashCode值; 2.將hashCode的高16位參與運(yùn)算
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代碼2
int n = tab.length;
// 將(tab.length - 1) 與 hash值進(jìn)行&運(yùn)算
int index = (n - 1) & hash;

get方法

public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}
 
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // table不為空 && table長度大于0 && table索引位置(根據(jù)hash值計(jì)算出)不為空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {    
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k)))) 
            return first;   // first的key等于傳入的key則返回first對(duì)象
        if ((e = first.next) != null) { // 向下遍歷
            if (first instanceof TreeNode)  // 判斷是否為TreeNode
                // 如果是紅黑樹節(jié)點(diǎn)乌奇，則調(diào)用紅黑樹的查找目標(biāo)節(jié)點(diǎn)方法getTreeNode
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 走到這代表節(jié)點(diǎn)為鏈表節(jié)點(diǎn)
            do { // 向下遍歷鏈表, 直至找到節(jié)點(diǎn)的key和傳入的key相等時(shí),返回該節(jié)點(diǎn)
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;    // 找不到符合的返回空
}

1没讲，先判斷table不為空，且table的長度大于0华弓，且table索引位置不為空
2食零，檢查第一個(gè)節(jié)點(diǎn)困乒，如果第一個(gè)節(jié)點(diǎn)就是要的值寂屏，直接返回。
3娜搂，向下遍歷鏈表迁霎，判斷是否為treeNode,如果是就調(diào)用getTreeNode
4，如果不是紅黑樹百宇，就遍歷鏈表找到數(shù)據(jù)
5考廉，如果都找不到直接返回null
接下來看getTreeNode

final TreeNode<K,V> getTreeNode(int h, Object k) {
    // 使用根結(jié)點(diǎn)調(diào)用find方法   
    // 查找根節(jié)點(diǎn), 索引位置的頭節(jié)點(diǎn)并不一定為紅黑樹的根結(jié)點(diǎn)
    return ((parent != null) ? root() : this).find(h, k, null); 
}

/**
 * 從調(diào)用此方法的結(jié)點(diǎn)開始查找, 通過hash值和key找到對(duì)應(yīng)的節(jié)點(diǎn)
 * 此處是紅黑樹的遍歷, 紅黑樹是特殊的自平衡二叉查找樹
 * 平衡二叉查找樹的特點(diǎn)：左節(jié)點(diǎn)<根節(jié)點(diǎn)<右節(jié)點(diǎn)
 */
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {    
    TreeNode<K,V> p = this; // this為調(diào)用此方法的節(jié)點(diǎn)
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)  // 傳入的hash值小于p節(jié)點(diǎn)的hash值, 則往p節(jié)點(diǎn)的左邊遍歷
            p = pl; // p賦值為p節(jié)點(diǎn)的左節(jié)點(diǎn)
        else if (ph < h)    // 傳入的hash值大于p節(jié)點(diǎn)的hash值, 則往p節(jié)點(diǎn)的右邊遍歷
            p = pr; // p賦值為p節(jié)點(diǎn)的右節(jié)點(diǎn)
        // 傳入的hash值和key值等于p節(jié)點(diǎn)的hash值和key值,則p節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn),返回p節(jié)點(diǎn)
        else if ((pk = p.key) == k || (k != null && k.equals(pk))) 
            return p;
        else if (pl == null)    // p節(jié)點(diǎn)的左節(jié)點(diǎn)為空則將向右遍歷
            p = pr; 
        else if (pr == null)    // p節(jié)點(diǎn)的右節(jié)點(diǎn)為空則向左遍歷
            p = pl;
        else if ((kc != null ||
                 // 如果傳入的key(k)所屬的類實(shí)現(xiàn)了Comparable接口,則將傳入的key跟p節(jié)點(diǎn)的key比較
                  (kc = comparableClassFor(k)) != null) && // 此行不為空代表k實(shí)現(xiàn)了Comparable
                 (dir = compareComparables(kc, k, pk)) != 0)//k<pk則dir<0, k>pk則dir>0
            p = (dir < 0) ? pl : pr;    // k < pk則向左遍歷(p賦值為p的左節(jié)點(diǎn)), 否則向右遍歷
        // 代碼走到此處, 代表key所屬類沒有實(shí)現(xiàn)Comparable, 直接指定向p的右邊遍歷
        else if ((q = pr.find(h, k, kc)) != null)   
            return q;
        else// 代碼走到此處代表上一個(gè)向右遍歷（pr.find(h, k, kc)）為空, 因此直接向左遍歷
            p = pl; 
    } while (p != null);
    return null;
}

1，將p節(jié)點(diǎn)賦值為調(diào)用此方法的節(jié)點(diǎn)
2携御，如果傳入的hash值小于p節(jié)點(diǎn)的hash值昌粤，則往p節(jié)點(diǎn)的左邊遍歷
3，如果傳入的hash值大于p節(jié)點(diǎn)的hash值啄刹，則往p節(jié)點(diǎn)的右邊遍歷
4涮坐，如果傳入的hash值等于p節(jié)點(diǎn)的hash值，并且傳入的key值跟p節(jié)點(diǎn)的key值相等, 則該p節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)誓军，返回p節(jié)點(diǎn)
5袱讹，如果p的左節(jié)點(diǎn)為空則向右遍歷，反之如果p的右節(jié)點(diǎn)為空則向左遍歷
6昵时，如果傳入的key（即代碼中的參數(shù)變量k）所屬的類實(shí)現(xiàn)了Comparable接口（kc不為空捷雕，comparableClassFor方法見下文代碼塊3），則將傳入的key跟p節(jié)點(diǎn)的key進(jìn)行比較（kc實(shí)現(xiàn)了Comparable接口壹甥，因此通過kc的比較方法進(jìn)行比較）救巷，并將比較結(jié)果賦值給dir，如果dir<0則代表k<pk句柠，則向p節(jié)點(diǎn)的左邊遍歷（pl）征绸；否則久橙，向p節(jié)點(diǎn)的右邊遍歷（pr）。
7管怠，代碼走到此處淆衷，代表key所屬類沒有實(shí)現(xiàn)Comparable，因此直接指定向p的右邊遍歷渤弛，如果能找到目標(biāo)節(jié)點(diǎn)則返回
8祝拯，代碼走到此處代表與第7點(diǎn)向右遍歷沒有找到目標(biāo)節(jié)點(diǎn)，因此直接向左邊遍歷
9她肯，以上都找不到目標(biāo)節(jié)點(diǎn)則返回空

/**
 * Returns x's Class if it is of the form "class C implements
 * Comparable<C>", else null.
 */
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

如果x實(shí)現(xiàn)了Comparable接口佳头，則返回 x的Class。

put方法

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table是否為空或者length等于0, 如果是則調(diào)用resize方法進(jìn)行初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;    
    // 通過hash值計(jì)算索引位置, 如果table表該索引位置節(jié)點(diǎn)為空則新增一個(gè)
    if ((p = tab[i = (n - 1) & hash]) == null)// 將索引位置的頭節(jié)點(diǎn)賦值給p
        tab[i] = newNode(hash, key, value, null);
    else {  // table表該索引位置不為空
        Node<K,V> e; K k;
        if (p.hash == hash && // 判斷p節(jié)點(diǎn)的hash值和key值是否跟傳入的hash值和key值相等
            ((k = p.key) == key || (key != null && key.equals(k)))) 
            e = p;  // 如果相等, 則p節(jié)點(diǎn)即為要查找的目標(biāo)節(jié)點(diǎn)晴氨，賦值給e
        // 判斷p節(jié)點(diǎn)是否為TreeNode, 如果是則調(diào)用紅黑樹的putTreeVal方法查找目標(biāo)節(jié)點(diǎn)
        else if (p instanceof TreeNode) 
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {  // 走到這代表p節(jié)點(diǎn)為普通鏈表節(jié)點(diǎn)
            for (int binCount = 0; ; ++binCount) {  // 遍歷此鏈表, binCount用于統(tǒng)計(jì)節(jié)點(diǎn)數(shù)
                if ((e = p.next) == null) { // p.next為空代表不存在目標(biāo)節(jié)點(diǎn)則新增一個(gè)節(jié)點(diǎn)插入鏈表尾部
                    p.next = newNode(hash, key, value, null);
                    // 計(jì)算節(jié)點(diǎn)是否超過8個(gè), 減一是因?yàn)檠h(huán)是從p節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開始的
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);// 如果超過8個(gè)康嘉，調(diào)用treeifyBin方法將該鏈表轉(zhuǎn)換為紅黑樹
                    break;
                }
                if (e.hash == hash && // e節(jié)點(diǎn)的hash值和key值都與傳入的相等, 則e即為目標(biāo)節(jié)點(diǎn),跳出循環(huán)
                    ((k = e.key) == key || (key != null && key.equals(k)))) 
                    break;
                p = e;  // 將p指向下一個(gè)節(jié)點(diǎn)
            }
        }
        // e不為空則代表根據(jù)傳入的hash值和key值查找到了節(jié)點(diǎn),將該節(jié)點(diǎn)的value覆蓋,返回oldValue
        if (e != null) { 
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); // 用于LinkedHashMap
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) // 插入節(jié)點(diǎn)后超過閾值則進(jìn)行擴(kuò)容
        resize();
    afterNodeInsertion(evict);  // 用于LinkedHashMap
    return null;
}

1，校驗(yàn)table是否為空或者length等于0籽前，如果是則調(diào)用resize方法（見下文resize方法）進(jìn)行初始化
2亭珍，通過hash值計(jì)算索引位置，將該索引位置的頭節(jié)點(diǎn)賦值給p節(jié)點(diǎn)枝哄，如果該索引位置節(jié)點(diǎn)為空則使用傳入的參數(shù)新增一個(gè)節(jié)點(diǎn)并放在該索引位置
3肄梨，判斷p節(jié)點(diǎn)的key和hash值是否跟傳入的相等，如果相等, 則p節(jié)點(diǎn)即為要查找的目標(biāo)節(jié)點(diǎn)挠锥，將p節(jié)點(diǎn)賦值給e節(jié)點(diǎn)
4众羡，如果p節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，則判斷p節(jié)點(diǎn)是否為TreeNode蓖租，如果是則調(diào)用紅黑樹的putTreeVal方法（見下文代碼塊4）查找目標(biāo)節(jié)點(diǎn)
5粱侣，走到這代表p節(jié)點(diǎn)為普通鏈表節(jié)點(diǎn)，則調(diào)用普通的鏈表方法進(jìn)行查找蓖宦，并定義變量binCount來統(tǒng)計(jì)該鏈表的節(jié)點(diǎn)數(shù)
6齐婴，如果p的next節(jié)點(diǎn)為空時(shí)，則代表找不到目標(biāo)節(jié)點(diǎn)球昨，則新增一個(gè)節(jié)點(diǎn)并插入鏈表尾部尔店，并校驗(yàn)節(jié)點(diǎn)數(shù)是否超過8個(gè)，如果超過則調(diào)用treeifyBin方法（見下文代碼塊6）將鏈表節(jié)點(diǎn)轉(zhuǎn)為紅黑樹節(jié)點(diǎn)
7主慰，如果遍歷的e節(jié)點(diǎn)存在hash值和key值都與傳入的相同嚣州，則e節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)，跳出循環(huán)
8共螺，如果e節(jié)點(diǎn)不為空该肴，則代表目標(biāo)節(jié)點(diǎn)存在，使用傳入的value覆蓋該節(jié)點(diǎn)的value藐不，并返回oldValue
9匀哄，如果插入節(jié)點(diǎn)后節(jié)點(diǎn)數(shù)超過閾值秦效，則調(diào)用resize方法（見下文resize方法）進(jìn)行擴(kuò)容
繼續(xù)看putTreeVal方法

/**
 * Tree version of putVal.
 * 紅黑樹插入會(huì)同時(shí)維護(hù)原來的鏈表屬性, 即原來的next屬性
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    // 查找根節(jié)點(diǎn), 索引位置的頭節(jié)點(diǎn)并不一定為紅黑樹的根結(jié)點(diǎn)
    TreeNode<K,V> root = (parent != null) ? root() : this;  
    for (TreeNode<K,V> p = root;;) {    // 將根節(jié)點(diǎn)賦值給p, 開始遍歷
        int dir, ph; K pk;
        if ((ph = p.hash) > h)  // 如果傳入的hash值小于p節(jié)點(diǎn)的hash值 
            dir = -1;   // 則將dir賦值為-1, 代表向p的左邊查找樹
        else if (ph < h)    // 如果傳入的hash值大于p節(jié)點(diǎn)的hash值,
            dir = 1;    // 則將dir賦值為1, 代表向p的右邊查找樹
        // 如果傳入的hash值和key值等于p節(jié)點(diǎn)的hash值和key值, 則p節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn), 返回p節(jié)點(diǎn)
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))  
            return p;
        // 如果k所屬的類沒有實(shí)現(xiàn)Comparable接口 或者 k和p節(jié)點(diǎn)的key相等
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) { 
            if (!searched) {    // 第一次符合條件, 該方法只有第一次才執(zhí)行
                TreeNode<K,V> q, ch;
                searched = true;
                // 從p節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)分別調(diào)用find方法進(jìn)行查找, 如果查找到目標(biāo)節(jié)點(diǎn)則返回
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))  
                    return q;
            }
            // 否則使用定義的一套規(guī)則來比較k和p節(jié)點(diǎn)的key的大小, 用來決定向左還是向右查找
            dir = tieBreakOrder(k, pk); // dir<0則代表k<pk，則向p左邊查找涎嚼；反之亦然
        }
 
        TreeNode<K,V> xp = p;   // xp賦值為x的父節(jié)點(diǎn),中間變量,用于下面給x的父節(jié)點(diǎn)賦值
        // dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目標(biāo)位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {  
            // 走進(jìn)來代表已經(jīng)找到x的位置阱州，只需將x放到該位置即可
            Node<K,V> xpn = xp.next;    // xp的next節(jié)點(diǎn)      
            // 創(chuàng)建新的節(jié)點(diǎn), 其中x的next節(jié)點(diǎn)為xpn, 即將x節(jié)點(diǎn)插入xp與xpn之間
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);   
            if (dir <= 0)   // 如果時(shí)dir <= 0, 則代表x節(jié)點(diǎn)為xp的左節(jié)點(diǎn)
                xp.left = x;
            else        // 如果時(shí)dir> 0, 則代表x節(jié)點(diǎn)為xp的右節(jié)點(diǎn)
                xp.right = x;
            xp.next = x;    // 將xp的next節(jié)點(diǎn)設(shè)置為x
            x.parent = x.prev = xp; // 將x的parent和prev節(jié)點(diǎn)設(shè)置為xp
            // 如果xpn不為空,則將xpn的prev節(jié)點(diǎn)設(shè)置為x節(jié)點(diǎn),與上文的x節(jié)點(diǎn)的next節(jié)點(diǎn)對(duì)應(yīng)
            if (xpn != null)    
                ((TreeNode<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x)); // 進(jìn)行紅黑樹的插入平衡調(diào)整
            return null;
        }
    }
}

1，查找當(dāng)前紅黑樹的根結(jié)點(diǎn)法梯，將根結(jié)點(diǎn)賦值給p節(jié)點(diǎn)苔货，開始進(jìn)行查找
2，如果傳入的hash值小于p節(jié)點(diǎn)的hash值立哑，將dir賦值為-1夜惭，代表向p的左邊查找樹
3，如果傳入的hash值大于p節(jié)點(diǎn)的hash值铛绰， 將dir賦值為1诈茧，代表向p的右邊查找樹
4，如果傳入的hash值等于p節(jié)點(diǎn)的hash值捂掰，并且傳入的key值跟p節(jié)點(diǎn)的key值相等, 則該p節(jié)點(diǎn)即為目標(biāo)節(jié)點(diǎn)敢会，返回p節(jié)點(diǎn)
5，如果k所屬的類沒有實(shí)現(xiàn)Comparable接口尘颓，或者k和p節(jié)點(diǎn)的key使用compareTo方法比較相等：第一次會(huì)從p節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)分別調(diào)用find方法（見上文代碼塊2）進(jìn)行查找走触，如果查找到目標(biāo)節(jié)點(diǎn)則返回晦譬；如果不是第一次或者調(diào)用find方法沒有找到目標(biāo)節(jié)點(diǎn)疤苹，則調(diào)用tieBreakOrder方法（見下文代碼塊5）比較k和p節(jié)點(diǎn)的key值的大小，以決定向樹的左節(jié)點(diǎn)還是右節(jié)點(diǎn)查找敛腌。
6卧土，如果dir <= 0則向左節(jié)點(diǎn)查找（p賦值為p.left，并進(jìn)行下一次循環(huán)）像樊，否則向右節(jié)點(diǎn)查找尤莺，如果已經(jīng)無法繼續(xù)查找（p賦值后為null），則代表該位置即為x的目標(biāo)位置生棍，另外變量xp用來記錄查找的最后一個(gè)節(jié)點(diǎn)颤霎，即下文新增的x節(jié)點(diǎn)的父節(jié)點(diǎn)。
7涂滴，以傳入的hash友酱、key、value參數(shù)和xp節(jié)點(diǎn)的next節(jié)點(diǎn)為參數(shù)柔纵，構(gòu)建x節(jié)點(diǎn)（注意：xp節(jié)點(diǎn)在此處可能是葉子節(jié)點(diǎn)缔杉、沒有左節(jié)點(diǎn)的節(jié)點(diǎn)、沒有右節(jié)點(diǎn)的節(jié)點(diǎn)三種情況搁料，即使它是葉子節(jié)點(diǎn)或详，它也可能有next節(jié)點(diǎn)系羞，紅黑樹的結(jié)構(gòu)跟鏈表的結(jié)構(gòu)是互不影響的，不會(huì)因?yàn)槟硞€(gè)節(jié)點(diǎn)是葉子節(jié)點(diǎn)就說它沒有next節(jié)點(diǎn)霸琴，紅黑樹在進(jìn)行操作時(shí)會(huì)同時(shí)維護(hù)紅黑樹結(jié)構(gòu)和鏈表結(jié)構(gòu)椒振，next屬性就是用來維護(hù)鏈表結(jié)構(gòu)的），根據(jù)dir的值決定x決定放在xp節(jié)點(diǎn)的左節(jié)點(diǎn)還是右節(jié)點(diǎn)梧乘，將xp的next節(jié)點(diǎn)設(shè)為x杠人，將x的parent和prev節(jié)點(diǎn)設(shè)為xp，如果原xp的next節(jié)點(diǎn)（xpn）不為空, 則將該節(jié)點(diǎn)的prev節(jié)點(diǎn)設(shè)置為x節(jié)點(diǎn), 與上面的將x節(jié)點(diǎn)的next節(jié)點(diǎn)設(shè)置為xpn對(duì)應(yīng)宋下。
8嗡善，進(jìn)行紅黑樹的插入平衡調(diào)整，見文末的解釋2学歧。
接著查看treeifyBin,將鏈表轉(zhuǎn)換為紅黑樹

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // table為空或者table的長度小于64, 進(jìn)行擴(kuò)容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 
        resize();
    // 根據(jù)hash值計(jì)算索引值, 遍歷該索引位置的鏈表
    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)紅黑樹節(jié)點(diǎn)
            if (tl == null) // tl為空代表為第一次循環(huán)
                hd = p; // 頭結(jié)點(diǎn)
            else {
                p.prev = tl;    // 當(dāng)前節(jié)點(diǎn)的prev屬性設(shè)為上一個(gè)節(jié)點(diǎn)
                tl.next = p;    // 上一個(gè)節(jié)點(diǎn)的next屬性設(shè)置為當(dāng)前節(jié)點(diǎn)
            }
            tl = p; // tl賦值為p, 在下一次循環(huán)中作為上一個(gè)節(jié)點(diǎn)
        } while ((e = e.next) != null); // e指向下一個(gè)節(jié)點(diǎn)
        // 將table該索引位置賦值為新轉(zhuǎn)的TreeNode的頭節(jié)點(diǎn)
        if ((tab[index] = hd) != null) 
            hd.treeify(tab);    // 以頭結(jié)點(diǎn)為根結(jié)點(diǎn), 構(gòu)建紅黑樹
    }
}

1罩引，校驗(yàn)table是否為空，如果長度小于64枝笨，則調(diào)用resize方法（見下文resize方法）進(jìn)行擴(kuò)容袁铐。
2，根據(jù)hash值計(jì)算索引值横浑，將該索引位置的節(jié)點(diǎn)賦值給e節(jié)點(diǎn)剔桨，從e節(jié)點(diǎn)開始遍歷該索引位置的鏈表。
3徙融，調(diào)用replacementTreeNode方法（該方法就一行代碼洒缀，直接返回一個(gè)新建的TreeNode）將鏈表節(jié)點(diǎn)轉(zhuǎn)為紅黑樹節(jié)點(diǎn)，將頭結(jié)點(diǎn)賦值給hd節(jié)點(diǎn)欺冀，每次遍歷結(jié)束將p節(jié)點(diǎn)賦值給tl树绩，用于在下一次循環(huán)中作為上一個(gè)節(jié)點(diǎn)進(jìn)行一些鏈表的關(guān)聯(lián)操作（p.prev = tl 和 tl.next = p）。
4隐轩，將table該索引位置賦值為新轉(zhuǎn)的TreeNode的頭節(jié)點(diǎn)hd饺饭，如果該節(jié)點(diǎn)不為空，則以hd為根結(jié)點(diǎn)职车，調(diào)用treeify方法構(gòu)建紅黑樹瘫俊。

final void treeify(Node<K,V>[] tab) {   // 構(gòu)建紅黑樹
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {// this即為調(diào)用此方法的TreeNode
        next = (TreeNode<K,V>)x.next;   // next賦值為x的下個(gè)節(jié)點(diǎn)
        x.left = x.right = null;    // 將x的左右節(jié)點(diǎn)設(shè)置為空
        if (root == null) { // 如果還沒有根結(jié)點(diǎn), 則將x設(shè)置為根結(jié)點(diǎn)
            x.parent = null;    // 根結(jié)點(diǎn)沒有父節(jié)點(diǎn)
            x.red = false;  // 根結(jié)點(diǎn)必須為黑色
            root = x;   // 將x設(shè)置為根結(jié)點(diǎn)
        }
        else {
            K k = x.key;    // k賦值為x的key
            int h = x.hash; // h賦值為x的hash值
            Class<?> kc = null;
            // 如果當(dāng)前節(jié)點(diǎn)x不是根結(jié)點(diǎn), 則從根節(jié)點(diǎn)開始查找屬于該節(jié)點(diǎn)的位置
            for (TreeNode<K,V> p = root;;) {    
                int dir, ph;
                K pk = p.key;   
                if ((ph = p.hash) > h)  // 如果x節(jié)點(diǎn)的hash值小于p節(jié)點(diǎn)的hash值
                    dir = -1;   // 則將dir賦值為-1, 代表向p的左邊查找
                else if (ph < h)    // 與上面相反, 如果x節(jié)點(diǎn)的hash值大于p節(jié)點(diǎn)的hash值
                    dir = 1;    // 則將dir賦值為1, 代表向p的右邊查找
                // 走到這代表x的hash值和p的hash值相等，則比較key值
                else if ((kc == null && // 如果k沒有實(shí)現(xiàn)Comparable接口 或者 x節(jié)點(diǎn)的key和p節(jié)點(diǎn)的key相等
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 使用定義的一套規(guī)則來比較x節(jié)點(diǎn)和p節(jié)點(diǎn)的大小悴灵，用來決定向左還是向右查找
                    dir = tieBreakOrder(k, pk); 
 
                TreeNode<K,V> xp = p;   // xp賦值為x的父節(jié)點(diǎn),中間變量用于下面給x的父節(jié)點(diǎn)賦值
                // dir<=0則向p左邊查找,否則向p右邊查找,如果為null,則代表該位置即為x的目標(biāo)位置
                if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                    x.parent = xp;  // x的父節(jié)點(diǎn)即為最后一次遍歷的p節(jié)點(diǎn)
                    if (dir <= 0)   // 如果時(shí)dir <= 0, 則代表x節(jié)點(diǎn)為父節(jié)點(diǎn)的左節(jié)點(diǎn)
                        xp.left = x;
                    else    // 如果時(shí)dir > 0, 則代表x節(jié)點(diǎn)為父節(jié)點(diǎn)的右節(jié)點(diǎn)
                        xp.right = x;
                    // 進(jìn)行紅黑樹的插入平衡(通過左旋扛芽、右旋和改變節(jié)點(diǎn)顏色來保證當(dāng)前樹符合紅黑樹的要求)
                    root = balanceInsertion(root, x);   
                    break;
                }
            }
        }
    }
    moveRootToFront(tab, root); // 如果root節(jié)點(diǎn)不在table索引位置的頭結(jié)點(diǎn), 則將其調(diào)整為頭結(jié)點(diǎn)
}

/**
 * 如果當(dāng)前索引位置的頭節(jié)點(diǎn)不是root節(jié)點(diǎn), 則將root的上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)進(jìn)行關(guān)聯(lián), 
 * 將root放到頭節(jié)點(diǎn)的位置, 原頭節(jié)點(diǎn)放在root的next節(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;
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        if (root != first) {    // 如果root節(jié)點(diǎn)不是該索引位置的頭節(jié)點(diǎn)
            Node<K,V> rn;
            tab[index] = root;  // 將該索引位置的頭節(jié)點(diǎn)賦值為root節(jié)點(diǎn)
            TreeNode<K,V> rp = root.prev;   // root節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
            // 如果root節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空, 
            // 則將root節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的prev屬性設(shè)置為root節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
            if ((rn = root.next) != null)   
                ((TreeNode<K,V>)rn).prev = rp; 
            // 如果root節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)不為空, 
            // 則將root節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的next屬性設(shè)置為root節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
            if (rp != null) 
                rp.next = rn;
            if (first != null)  // 如果原頭節(jié)點(diǎn)不為空, 則將原頭節(jié)點(diǎn)的prev屬性設(shè)置為root節(jié)點(diǎn)
                first.prev = root;
            root.next = first;  // 將root節(jié)點(diǎn)的next屬性設(shè)置為原頭節(jié)點(diǎn)
            root.prev = null;
        }
        assert checkInvariants(root);   // 檢查樹是否正常
    }
}

resize

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {   // 老table不為空
        if (oldCap >= MAXIMUM_CAPACITY) {      // 老table的容量超過最大容量值
            threshold = Integer.MAX_VALUE;  // 設(shè)置閾值為Integer.MAX_VALUE
            return oldTab;
        }
        // 將新容量賦值為老容量*2，如果新容量<最大容量并且老容量>=16, 則將新閾值設(shè)置為原來的兩倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)   
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // 老表的容量為0, 老表的閾值大于0, 是因?yàn)槌跏既萘勘环湃腴撝?        newCap = oldThr;    // 則將新表的容量設(shè)置為老表的閾值 
    else {  // 老表的容量為0, 老表的閾值為0, 則為空表称勋，設(shè)置默認(rèn)容量和閾值
        newCap = DEFAULT_INITIAL_CAPACITY; 
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {  // 如果新閾值為空, 則通過新的容量*負(fù)載因子獲得新閾值
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr; // 將當(dāng)前閾值賦值為剛計(jì)算出來的新的閾值
    @SuppressWarnings({"rawtypes","unchecked"})
    // 定義新表,容量為剛計(jì)算出來的新容量
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab; // 將當(dāng)前的表賦值為新定義的表
    if (oldTab != null) {   // 如果老表不為空, 則需遍歷將節(jié)點(diǎn)賦值給新表
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {  // 將索引值為j的老表頭節(jié)點(diǎn)賦值給e
                oldTab[j] = null; // 將老表的節(jié)點(diǎn)設(shè)置為空, 以便垃圾收集器回收空間
                // 如果e.next為空, 則代表老表的該位置只有1個(gè)節(jié)點(diǎn), 
                // 通過hash值計(jì)算新表的索引位置, 直接將該節(jié)點(diǎn)放在該位置
                if (e.next == null) 
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                     // 調(diào)用treeNode的hash分布(跟下面最后一個(gè)else的內(nèi)容幾乎相同)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null; // 存儲(chǔ)跟原索引位置相同的節(jié)點(diǎn)
                    Node<K,V> hiHead = null, hiTail = null; // 存儲(chǔ)索引位置為:原索引+oldCap的節(jié)點(diǎn)
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //如果e的hash值與老表的容量進(jìn)行與運(yùn)算為0,則擴(kuò)容后的索引位置跟老表的索引位置一樣
                        if ((e.hash & oldCap) == 0) {   
                            if (loTail == null) // 如果loTail為空, 代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
                                loHead = e; // 則將loHead賦值為第一個(gè)節(jié)點(diǎn)
                            else    
                                loTail.next = e;    // 否則將節(jié)點(diǎn)添加在loTail后面
                            loTail = e; // 并將loTail賦值為新增的節(jié)點(diǎn)
                        }
                        //如果e的hash值與老表的容量進(jìn)行與運(yùn)算為1,則擴(kuò)容后的索引位置為:老表的索引位置＋oldCap
                        else {  
                            if (hiTail == null) // 如果hiTail為空, 代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
                                hiHead = e; // 則將hiHead賦值為第一個(gè)節(jié)點(diǎn)
                            else
                                hiTail.next = e;    // 否則將節(jié)點(diǎn)添加在hiTail后面
                            hiTail = e; // 并將hiTail賦值為新增的節(jié)點(diǎn)
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null; // 最后一個(gè)節(jié)點(diǎn)的next設(shè)為空
                        newTab[j] = loHead; // 將原索引位置的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)
                    }
                    if (hiTail != null) {
                        hiTail.next = null; // 最后一個(gè)節(jié)點(diǎn)的next設(shè)為空
                        newTab[j + oldCap] = hiHead; // 將索引位置為原索引+oldCap的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)
                    }
                }
            }
        }
    }
    return newTab;
}

1胸哥，如果老表的容量大于0，判斷老表的容量是否超過最大容量值：如果超過則將閾值設(shè)置為Integer.MAX_VALUE赡鲜，并直接返回老表（此時(shí)oldCap * 2比Integer.MAX_VALUE大空厌，因此無法進(jìn)行重新分布庐船，只是單純的將閾值擴(kuò)容到最大）；將新表的容量賦值為老表的容量*2嘲更，如果新容量小于最大容量并且老容量不小于16筐钟，則直接將新的閾值設(shè)置為原來的兩倍。
2赋朦，如果老表的容量為0篓冲，老表的閾值大于0，這種情況是傳了容量的new方法創(chuàng)建的空表宠哄，將新表的容量設(shè)置為老表的閾值（這種情況發(fā)生在新創(chuàng)建的HashMap第一次put時(shí)壹将，該HashMap初始化的時(shí)候傳了初始容量，由于HashMap并沒有capacity變量來存放容量值毛嫉，因此傳進(jìn)來的初始容量是存放在threshold變量上（查看HashMap(int initialCapacity, float loadFactor)方法）诽俯，因此此時(shí)老表的threshold的值就是我們要新創(chuàng)建的HashMap的capacity，所以將新表的容量設(shè)置為老表的閾值承粤。
3暴区，如果老表的容量為0，老表的閾值為0辛臊，這種情況是沒有傳容量的new方法創(chuàng)建的空表仙粱，將閾值和容量設(shè)置為默認(rèn)值。
4彻舰，如果新表的閾值為空伐割，則通過新的容量 * 負(fù)載因子獲得閾值（這種情況是初始化的時(shí)候傳了初始容量，跟第2點(diǎn)相同情況淹遵，或者初始容量設(shè)置的太小導(dǎo)致老表的容量沒有超過16導(dǎo)致的）口猜。
5负溪，將當(dāng)前閾值設(shè)置為剛計(jì)算出來的新的閾值透揣，定義新表，容量為剛計(jì)算出來的新容量川抡，將當(dāng)前的表設(shè)置為新定義的表辐真。
6，如果老表不為空崖堤，則需遍歷所有節(jié)點(diǎn)侍咱，將節(jié)點(diǎn)賦值給新表。
7密幔，將老表上索引為j的頭結(jié)點(diǎn)賦值給e節(jié)點(diǎn)楔脯，并將老表上索引為j的節(jié)點(diǎn)設(shè)置為空。
8胯甩，如果e的next節(jié)點(diǎn)為空昧廷，則代表老表的該位置只有1個(gè)節(jié)點(diǎn)堪嫂，通過hash值計(jì)算新表的索引位置，直接將該節(jié)點(diǎn)放在新表的該位置上木柬。
9皆串，如果e的next節(jié)點(diǎn)不為空，并且e為TreeNode眉枕，則調(diào)用split方法（見下文代碼塊10）進(jìn)行hash分布恶复。
10，如果e的next節(jié)點(diǎn)不為空速挑，并且e為普通的鏈表節(jié)點(diǎn)谤牡，則進(jìn)行普通的hash分布。
11姥宝，如果e的hash值與老表的容量（為一串只有1個(gè)為2的二進(jìn)制數(shù)拓哟，例如16為0000 0000 0001 0000）進(jìn)行位與運(yùn)算為0，則說明e節(jié)點(diǎn)擴(kuò)容后的索引位置跟老表的索引位置一樣（見例子1）伶授，進(jìn)行鏈表拼接操作：如果loTail為空断序，代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)，則將loHead賦值為該節(jié)點(diǎn)糜烹；否則將節(jié)點(diǎn)添加在loTail后面违诗，并將loTail賦值為新增的節(jié)點(diǎn)。
12疮蹦，如果e的hash值與老表的容量（為一串只有1個(gè)為2的二進(jìn)制數(shù)诸迟，例如16為0000 0000 0001 0000）進(jìn)行位與運(yùn)算為1，則說明e節(jié)點(diǎn)擴(kuò)容后的索引位置為：老表的索引位置＋oldCap（見例子1）愕乎，進(jìn)行鏈表拼接操作：如果hiTail為空阵苇，代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)，則將hiHead賦值為該節(jié)點(diǎn)感论；否則將節(jié)點(diǎn)添加在hiTail后面绅项，并將hiTail賦值為新增的節(jié)點(diǎn)。
13比肄，老表節(jié)點(diǎn)重新hash分布在新表結(jié)束后快耿，如果loTail不為空（說明老表的數(shù)據(jù)有分布到新表上原索引位置的節(jié)點(diǎn)），則將最后一個(gè)節(jié)點(diǎn)的next設(shè)為空芳绩，并將新表上原索引位置的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)掀亥；如果hiTail不為空（說明老表的數(shù)據(jù)有分布到新表上原索引+oldCap位置的節(jié)點(diǎn)），則將最后一個(gè)節(jié)點(diǎn)的next設(shè)為空妥色，并將新表上索引位置為原索引+oldCap的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)搪花。
14，返回新表。

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    TreeNode<K,V> b = this; // 拿到調(diào)用此方法的節(jié)點(diǎn)
    TreeNode<K,V> loHead = null, loTail = null; // 存儲(chǔ)跟原索引位置相同的節(jié)點(diǎn)
    TreeNode<K,V> hiHead = null, hiTail = null; // 存儲(chǔ)索引位置為:原索引+oldCap的節(jié)點(diǎn)
    int lc = 0, hc = 0;
    for (TreeNode<K,V> e = b, next; e != null; e = next) {  // 從b節(jié)點(diǎn)開始遍歷
        next = (TreeNode<K,V>)e.next;   // next賦值為e的下個(gè)節(jié)點(diǎn)
        e.next = null;  // 同時(shí)將老表的節(jié)點(diǎn)設(shè)置為空撮竿，以便垃圾收集器回收
        //如果e的hash值與老表的容量進(jìn)行與運(yùn)算為0,則擴(kuò)容后的索引位置跟老表的索引位置一樣
        if ((e.hash & bit) == 0) {  
            if ((e.prev = loTail) == null)  // 如果loTail為空, 代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
                loHead = e; // 則將loHead賦值為第一個(gè)節(jié)點(diǎn)
            else
                loTail.next = e;    // 否則將節(jié)點(diǎn)添加在loTail后面
            loTail = e; // 并將loTail賦值為新增的節(jié)點(diǎn)
            ++lc;   // 統(tǒng)計(jì)原索引位置的節(jié)點(diǎn)個(gè)數(shù)
        }
        //如果e的hash值與老表的容量進(jìn)行與運(yùn)算為1,則擴(kuò)容后的索引位置為:老表的索引位置＋oldCap
        else {  
            if ((e.prev = hiTail) == null)  // 如果hiHead為空, 代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)
                hiHead = e; // 則將hiHead賦值為第一個(gè)節(jié)點(diǎn)
            else
                hiTail.next = e;    // 否則將節(jié)點(diǎn)添加在hiTail后面
            hiTail = e; // 并將hiTail賦值為新增的節(jié)點(diǎn)
            ++hc;   // 統(tǒng)計(jì)索引位置為原索引+oldCap的節(jié)點(diǎn)個(gè)數(shù)
        }
    }
 
    if (loHead != null) {   // 原索引位置的節(jié)點(diǎn)不為空
        if (lc <= UNTREEIFY_THRESHOLD)  // 節(jié)點(diǎn)個(gè)數(shù)少于6個(gè)則將紅黑樹轉(zhuǎn)為鏈表結(jié)構(gòu)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;    // 將原索引位置的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)
            // hiHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節(jié)點(diǎn)被分到兩個(gè)位置)
            // 已經(jīng)被改變, 需要重新構(gòu)建新的紅黑樹
            if (hiHead != null) 
                loHead.treeify(tab);    // 以loHead為根結(jié)點(diǎn), 構(gòu)建新的紅黑樹
        }
    }
    if (hiHead != null) {   // 索引位置為原索引+oldCap的節(jié)點(diǎn)不為空
        if (hc <= UNTREEIFY_THRESHOLD)  // 節(jié)點(diǎn)個(gè)數(shù)少于6個(gè)則將紅黑樹轉(zhuǎn)為鏈表結(jié)構(gòu)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;  // 將索引位置為原索引+oldCap的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)
            // loHead不為空則代表原來的紅黑樹(老表的紅黑樹由于節(jié)點(diǎn)被分到兩個(gè)位置)
            // 已經(jīng)被改變, 需要重新構(gòu)建新的紅黑樹
            if (loHead != null) 
                hiHead.treeify(tab);    // 以hiHead為根結(jié)點(diǎn), 構(gòu)建新的紅黑樹
        }
    }
}

1丁稀，以調(diào)用此方法的節(jié)點(diǎn)開始，遍歷整個(gè)紅黑樹節(jié)點(diǎn)（此處實(shí)際是遍歷的鏈表節(jié)點(diǎn)倚聚，上文提過线衫，紅黑樹節(jié)點(diǎn)也會(huì)同時(shí)維護(hù)鏈表結(jié)構(gòu)）。
2惑折，如果e的hash值與老表的容量（為一串只有1個(gè)為2的二進(jìn)制數(shù)授账，例如16為0000 0000 0001 0000）進(jìn)行位與運(yùn)算為0，則說明e節(jié)點(diǎn)擴(kuò)容后的索引位置跟老表的索引位置一樣（見下文例子1）惨驶，進(jìn)行鏈表拼接操作：如果loTail為空白热，代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)，則將loHead賦值為該節(jié)點(diǎn)粗卜；否則將節(jié)點(diǎn)添加在loTail后面屋确，并將loTail賦值為新增的節(jié)點(diǎn)，并統(tǒng)計(jì)原索引位置的節(jié)點(diǎn)個(gè)數(shù)续扔。
3攻臀，如果e的hash值與老表的容量（為一串只有1個(gè)為2的二進(jìn)制數(shù)，例如16為0000 0000 0001 0000）進(jìn)行位與運(yùn)算為1纱昧，則說明e節(jié)點(diǎn)擴(kuò)容后的索引位置為：老表的索引位置＋oldCap（見例子1）刨啸，進(jìn)行鏈表拼接操作：如果hiTail為空，代表該節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)识脆，則將hiHead賦值為該節(jié)點(diǎn)设联；否則將節(jié)點(diǎn)添加在hiTail后面，并將hiTail賦值為新增的節(jié)點(diǎn)灼捂，并統(tǒng)計(jì)索引位置為原索引+oldCap的節(jié)點(diǎn)個(gè)數(shù)离例。
4，如果原索引位置的節(jié)點(diǎn)不為空：如果當(dāng)該索引位置節(jié)點(diǎn)數(shù)<=6個(gè)悉稠，調(diào)用untreeify方法（見下文代碼塊11）將紅黑樹節(jié)點(diǎn)轉(zhuǎn)為鏈表節(jié)點(diǎn)宫蛆；否則將原索引位置的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)（即loHead結(jié)點(diǎn)），如果判斷hiHead不為空則代表原來的紅黑樹（老表的紅黑樹由于節(jié)點(diǎn)被分到兩個(gè)位置）已經(jīng)被改變偎球，需要重新構(gòu)建新的紅黑樹洒扎，以loHead為根結(jié)點(diǎn)，調(diào)用treeify方法（見上文代碼塊7）構(gòu)建新的紅黑樹衰絮。
5，如果索引位置為原索引+oldCap的節(jié)點(diǎn)不為空：如果當(dāng)該索引位置節(jié)點(diǎn)數(shù)<=6個(gè)磷醋，調(diào)用untreeify方法（見下文代碼塊11）將紅黑樹節(jié)點(diǎn)轉(zhuǎn)為鏈表節(jié)點(diǎn)猫牡；否則將索引位置為原索引+oldCap的節(jié)點(diǎn)設(shè)置為對(duì)應(yīng)的頭結(jié)點(diǎn)（即hiHead結(jié)點(diǎn)），如果判斷l(xiāng)oHead不為空則代表原來的紅黑樹（老表的紅黑樹由于節(jié)點(diǎn)被分到兩個(gè)位置）已經(jīng)被改變邓线，需要重新構(gòu)建新的紅黑樹淌友，以hiHead為根結(jié)點(diǎn)煌恢，調(diào)用treeify方法（見上文代碼塊7）構(gòu)建新的紅黑樹。

// 將紅黑樹節(jié)點(diǎn)轉(zhuǎn)為鏈表節(jié)點(diǎn), 當(dāng)節(jié)點(diǎn)<=6個(gè)時(shí)會(huì)被觸發(fā)
final Node<K,V> untreeify(HashMap<K,V> map) {  
    Node<K,V> hd = null, tl = null; // hd指向頭結(jié)點(diǎn), tl指向尾節(jié)點(diǎn)
    // 從調(diào)用該方法的節(jié)點(diǎn), 即鏈表的頭結(jié)點(diǎn)開始遍歷, 將所有節(jié)點(diǎn)全轉(zhuǎn)為鏈表節(jié)點(diǎn)
    for (Node<K,V> q = this; q != null; q = q.next) {   
        // 調(diào)用replacementNode方法構(gòu)建鏈表節(jié)點(diǎn)
        Node<K,V> p = map.replacementNode(q, null); 
        // 如果tl為null, 則代表當(dāng)前節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn), 將hd賦值為該節(jié)點(diǎn)
        if (tl == null)
            hd = p;
        else    // 否則, 將尾節(jié)點(diǎn)的next屬性設(shè)置為當(dāng)前節(jié)點(diǎn)p
            tl.next = p;
        tl = p; // 每次都將tl節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn), 即尾節(jié)點(diǎn)
    }
    return hd;  // 返回轉(zhuǎn)換后的鏈表的頭結(jié)點(diǎn)
}

1震庭，從調(diào)用該方法的節(jié)點(diǎn)瑰抵，即鏈表的頭結(jié)點(diǎn)開始遍歷, 將所有節(jié)點(diǎn)全轉(zhuǎn)為鏈表節(jié)點(diǎn)
2，調(diào)用replacementNode方法構(gòu)建鏈表節(jié)點(diǎn)
3器联，如果tl為null, 則代表當(dāng)前節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)二汛，將hd賦值為該節(jié)點(diǎn)，否則, 將尾節(jié)點(diǎn)的next屬性設(shè)置為當(dāng)前節(jié)點(diǎn)p
4拨拓，每次都將tl節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn), 即尾節(jié)點(diǎn)
5肴颊，返回轉(zhuǎn)換后的鏈表的頭結(jié)點(diǎn)

總結(jié)

1，HashMap的底層是個(gè)Node數(shù)組（Node<K,V>[] table）渣磷，在數(shù)組的具體索引位置婿着，如果存在多個(gè)節(jié)點(diǎn)，則可能是以鏈表或紅黑樹的形式存在醋界。
2竟宋，增加、刪除形纺、查找鍵值對(duì)時(shí)袜硫，定位到哈希桶數(shù)組的位置是很關(guān)鍵的一步，源碼中是通過下面3個(gè)操作來完成這一步：1）拿到key的hashCode值挡篓；2）將hashCode的高位參與運(yùn)算婉陷，重新計(jì)算hash值；3）將計(jì)算出來的hash值與(table.length - 1)進(jìn)行&運(yùn)算官研。
3秽澳，HashMap的默認(rèn)初始容量（capacity）是16，capacity必須為2的冪次方戏羽；默認(rèn)負(fù)載因子（load factor）是0.75担神；實(shí)際能存放的節(jié)點(diǎn)個(gè)數(shù)（threshold，即觸發(fā)擴(kuò)容的閾值）= capacity * load factor始花。
4妄讯，HashMap在觸發(fā)擴(kuò)容后，閾值會(huì)變?yōu)樵瓉淼?倍酷宵，并且會(huì)進(jìn)行重hash亥贸，重hash后索引位置index的節(jié)點(diǎn)的新分布位置最多只有兩個(gè)：原索引位置或原索引+oldCap位置。例如capacity為16浇垦，索引位置5的節(jié)點(diǎn)擴(kuò)容后炕置，只可能分布在新報(bào)索引位置5和索引位置21（5+16）。
5，導(dǎo)致HashMap擴(kuò)容后朴摊，同一個(gè)索引位置的節(jié)點(diǎn)重hash最多分布在兩個(gè)位置的根本原因是：1）table的長度始終為2的n次方默垄；2）索引位置的計(jì)算方法為“(table.length - 1) & hash”。HashMap擴(kuò)容是一個(gè)比較耗時(shí)的操作甚纲，定義HashMap時(shí)盡量給個(gè)接近的初始容量值口锭。
6，HashMap有threshold屬性和loadFactor屬性介杆，但是沒有capacity屬性鹃操。初始化時(shí)，如果傳了初始化容量值这溅，該值是存在threshold變量组民，并且Node數(shù)組是在第一次put時(shí)才會(huì)進(jìn)行初始化，初始化時(shí)會(huì)將此時(shí)的threshold值作為新表的capacity值悲靴，然后用capacity和loadFactor計(jì)算新表的真正threshold值臭胜。
7，當(dāng)同一個(gè)索引位置的節(jié)點(diǎn)在增加后達(dá)到9個(gè)時(shí)癞尚，并且此時(shí)數(shù)組的長度大于等于64耸三，則會(huì)觸發(fā)鏈表節(jié)點(diǎn)（Node）轉(zhuǎn)紅黑樹節(jié)點(diǎn)（TreeNode，間接繼承Node）浇揩，轉(zhuǎn)成紅黑樹節(jié)點(diǎn)后仪壮，其實(shí)鏈表的結(jié)構(gòu)還存在，通過next屬性維持胳徽。鏈表節(jié)點(diǎn)轉(zhuǎn)紅黑樹節(jié)點(diǎn)的具體方法為源碼中的treeifyBin(Node<K,V>[] tab, int hash)方法积锅。而如果數(shù)組長度小于64，則不會(huì)觸發(fā)鏈表轉(zhuǎn)紅黑樹养盗，而是會(huì)進(jìn)行擴(kuò)容缚陷。
8，當(dāng)同一個(gè)索引位置的節(jié)點(diǎn)在移除后達(dá)到6個(gè)時(shí)往核，并且該索引位置的節(jié)點(diǎn)為紅黑樹節(jié)點(diǎn)箫爷，會(huì)觸發(fā)紅黑樹節(jié)點(diǎn)轉(zhuǎn)鏈表節(jié)點(diǎn)。紅黑樹節(jié)點(diǎn)轉(zhuǎn)鏈表節(jié)點(diǎn)的具體方法為源碼中的untreeify(HashMap<K,V> map)方法聂儒。
9虎锚，HashMap在JDK1.8之后不再有死循環(huán)的問題，JDK1.8之前存在死循環(huán)的根本原因是在擴(kuò)容后同一索引位置的節(jié)點(diǎn)順序會(huì)反掉衩婚。
10窜护，HashMap是非線程安全的，在并發(fā)場景下使用ConcurrentHashMap來代替谅猾。