摘要：表示該類本身不可比表示與對應的之間不可比。當數目滿足時，鏈表將轉為紅黑樹結構，否則繼續擴容。至此，插入告一段落。當超出時，哈希表將會即內部數據結構重建至大約兩倍。要注意的是使用許多有這相同的鍵值肯定會降低哈希表性能。

回顧上期?觀光線路圖：putAll() --> putMapEntries() --> tableSizeFor() --> resize() --> hash() --> putVal()...

本期與您繼續一起前進：putVal() --> putTreeVal() --> find() --> balanceInsertion() --> rotateLeft()/rotateRight() --> treeifyBin()...

// 為了找到合適的位置插入新節點，源碼中進行了一系列比較。
final TreeNode putTreeVal(HashMap map, Node[] tab,
                               int h, K k, V v) {
    Class kc = null;
    boolean searched = false;
    TreeNode root = (parent != null) ? root() : this; // 獲取根節點，從根節點開始遍歷
    for (TreeNode p = root;;) {
        int dir, ph; K pk;
        if ((ph = p.hash) > h)
            dir = -1; // 左
        else if (ph < h)
            dir = 1; // 右
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p; // 相等直接返回
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            if (!searched) {
                TreeNode q, ch;
                searched = true;
                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;
            }
            dir = tieBreakOrder(k, pk);
        }

        TreeNode xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node xpn = xp.next;
            TreeNode x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

當前節點hash值(ph)與插入節點hash值(h)比較，
若ph > h(dir=-1)，將新節點歸為左子樹;
若ph < h(dir=1)，右子樹;
否則即表示hash值相等，然后又對key進行了比較。

“kc = comparableClassFor(k)) == null”表示該類本身不可比（class C don"t implements Comparable）；“dir = compareComparables(kc, k, pk)) == 0”表示k與pk對應的Class之間不可比。searched為一次性開關僅在p為root時生效，遍歷比較左右子樹中是否存在于插入節點相等的。

最后比到tieBreakOrder()中的“System.identityHashCode(a) <= System.identityHashCode(b)”，即對象的內存地址來生成的hashCode相互比較。堪稱鐵杵磨成針的比較。

這里循環的推進是靠“if ((p = (dir <= 0) ? p.left : p.right) == null)”，之前千辛萬苦比較出的dir也在這使用。直到為空的左/右子樹節點，插入新值（新值插入的過程參考下圖理解）。

final TreeNode find(int h, Object k, Class kc) {
    TreeNode p = this;
    do {
        int ph, dir; K pk;
        TreeNode pl = p.left, pr = p.right, q;
        if ((ph = p.hash) > h)
            p = pl;
        else if (ph < h)
            p = pr;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        else if (pl == null)
            p = pr;
        else if (pr == null)
            p = pl;
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&
                 (dir = compareComparables(kc, k, pk)) != 0)
            p = (dir < 0) ? pl : pr;
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        else
            p = pl;
    } while (p != null);
    return null;
}

有沒有發現，如果當你看懂putTreeVal，類比find是不是變得很好理解了呢？

static  TreeNode balanceInsertion(TreeNode root,
                                                    TreeNode x) {
    x.red = true; // x為紅
    for (TreeNode xp, xpp, xppl, xppr;;) {
        // x為根
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // x父節點為黑 || x父節點為根（黑）
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 
        if (xp == (xppl = xpp.left)) {
            // ①
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            // ②
            else {
                if (x == xp.right) {
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        else {
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp;
            }
            else {
                if (x == xp.left) {
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

在插入新值后，可能打破了紅黑樹原有的“平衡”，balanceInsertion()的作用就是要維持這種“平衡”，保證最佳效率。所謂的紅黑樹“平衡”即：

①：所有節點非黑即紅；
②：根為黑，葉子為null且為黑，紅的兩子節點為黑；
③：任一節點到葉子節點的黑子節點個數相同；

下面，以“(xp == (xppl = xpp.left))”簡(chou)單(lou)的給大家畫個圖例（其中①②與源碼注釋相對應）。

圖②中打鉤的都是合格的紅黑樹其實，圖②右邊方框內為左旋右旋節點關系變化圖解。

// 左旋 與 右旋
static  TreeNode rotateLeft(TreeNode root, TreeNode p) {
    TreeNode r, pp, rl;
    if (p != null && (r = p.right) != null) {
        if ((rl = p.right = r.left) != null)
            rl.parent = p;
        if ((pp = r.parent = p.parent) == null)
            (root = r).red = false;
        else if (pp.left == p)
            pp.left = r; // p為pp左子節點
        else
            pp.right = r;
        r.left = p;
        p.parent = r;
    }
    return root;
}

static  TreeNode rotateRight(TreeNode root, TreeNode p) {
    TreeNode l, pp, lr;
    if (p != null && (l = p.left) != null) {
        if ((lr = p.left = l.right) != null)
            lr.parent = p;
        if ((pp = l.parent = p.parent) == null)
            (root = l).red = false;
        else if (pp.right == p)
            pp.right = l;
        else
            pp.left = l;
        l.right = p;
        p.parent = l;
    }
    return root;
}

左旋右旋過程包含在上面的圖例中了，另附上兩張網上看到的動圖便于大家理解。

同時，在線紅黑樹插入刪除動畫演示【點我】，還不理解的童鞋可以親自直觀的試試。

final void treeifyBin(Node[] tab, int hash) {
    int n, index; Node e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode hd = null, tl = null;
        do {
            TreeNode p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);
    }
}

putVal()的treeifyBin()在鏈表中數目大于等于“TREEIFY_THRESHOLD - 1”時觸發。當數目滿足MIN_TREEIFY_CAPACITY時，鏈表將轉為紅黑樹結構，否則繼續擴容。treeify()類似putTreeVal()。

至此，HashMap插入告一段落。有誤或有讀不懂的地方歡迎交流。時間有限，江湖再見。

更多有意思的內容，歡迎訪問筆者小站： rebey.cn

附上前一段時間翻譯的HashMap源碼開篇注釋，將開頭作為總結。也算收尾呼應吧。

/**
 * Hash table based implementation of the Map interface.  This
 * implementation provides all of the optional map operations, and permits
 * null values and the null key.  (The HashMap
 * class is roughly equivalent to Hashtable, except that it is
 * unsynchronized and permits nulls.)  This class makes no guarantees as to
 * the order of the map; in particular, it does not guarantee that the order
 * will remain constant over time.
 *
 * 哈希表實現了Map接口。該接口提供了所有可選的map操作，且允許鍵、值為空。（HashMap近似Hashtable，除了異步和
 * 允許空值。）HashMap無法保證map的順序；尤其是持久不變。（譯者注：比如rehash。）
 *
 * 
This implementation provides constant-time performance for the basic
 * operations (get and put), assuming the hash function
 * disperses the elements properly among the buckets.  Iteration over
 * collection views requires time proportional to the "capacity" of the
 * HashMap instance (the number of buckets) plus its size (the number
 * of key-value mappings).  Thus, it"s very important not to set the initial
 * capacity too high (or the load factor too low) if iteration performance is
 * important.
 *
 * 在哈希函數將元素恰當的分布在桶中的情況下，接口提供了穩定的基礎操作（get和put）。
 * 遍歷集合的時間與HashMap實例的 “容量”(hash桶的數量) + “大小”（鍵值對數量）的和成正比。
 * 因此，當循環比重較大時，初始容量值不能設的太大（或者負載因子太小）是非常重要的。
 *
 * 
An instance of HashMap has two parameters that affect its
 * performance: initial capacity and load factor.  The
 * capacity is the number of buckets in the hash table, and the initial
 * capacity is simply the capacity at the time the hash table is created.  The
 * load factor is a measure of how full the hash table is allowed to
 * get before its capacity is automatically increased.  When the number of
 * entries in the hash table exceeds the product of the load factor and the
 * current capacity, the hash table is rehashed (that is, internal data
 * structures are rebuilt) so that the hash table has approximately twice the
 * number of buckets.
 *
 * 兩個參數影響著HashMap實例：“初始容量”和“負載因子”。“初始容量”指的是哈希表中桶的數量，在哈希表創建的同時初始化。
 * “負載因子”度量著哈希表能裝多滿（譯者注：相對于桶的形象概念，建議參看網上hashMap結構圖理解）直到在自動擴容。
 * 當超出時，哈希表將會rehashed（即內部數據結構重建）至大約兩倍。
 *
 * 
As a general rule, the default load factor (.75) offers a good
 * tradeoff between time and space costs.  Higher values decrease the
 * space overhead but increase the lookup cost (reflected in most of
 * the operations of the HashMap class, including
 * get and put).  The expected number of entries in
 * the map and its load factor should be taken into account when
 * setting its initial capacity, so as to minimize the number of
 * rehash operations.  If the initial capacity is greater than the
 * maximum number of entries divided by the load factor, no rehash
 * operations will ever occur.
 *
 * 一般來說，默認負載因子（0.75）在時間和空間之間起到了很好的權衡。更大的值雖然減輕了空間負荷卻增加了查找花銷
 * （在大多數HashMap操作上都有體現，包括get和put）。當設置map初始容量時，需要考慮預期條目數和它的負載因子
 * 使得rehash操作次數最少。如果初始容量大于最大條目數/負載因子，甚至不會發生rehash。
 *
 * 
If many mappings are to be stored in a HashMap
 * instance, creating it with a sufficiently large capacity will allow
 * the mappings to be stored more efficiently than letting it perform
 * automatic rehashing as needed to grow the table.  Note that using
 * many keys with the same {@code hashCode()} is a sure way to slow
 * down performance of any hash table. To ameliorate impact, when keys
 * are {@link Comparable}, this class may use comparison order among
 * keys to help break ties.
 *
 * 如果大量的鍵值對將存儲在HashMap實例中，使用一個足夠大的容量來初始化遠比讓它自動按需rehash擴容的效率高。
 * 要注意的是使用許多有這相同hashCode()的鍵值肯定會降低哈希表性能。為了降低影響，當key支持Comparable接口時，
 * 在keys間比較排序來打破瓶頸。
 *
 * 
Note that this implementation is not synchronized.
 * If multiple threads access a hash map concurrently, and at least one of
 * the threads modifies the map structurally, it must be
 * synchronized externally.  (A structural modification is any operation
 * that adds or deletes one or more mappings; merely changing the value
 * associated with a key that an instance already contains is not a
 * structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the map.
 *
 * HashMap是非線程安全的。如果多線程同時訪問一個哈希表，并且至少一個線程在修改map結構是，必須在外加上
 * synchronized關鍵字。（結構化修改包括任何增刪一個或者多個鍵值對；只修改一個已存在的key的值不屬于
 * 結構修改。）典型的是用同步對象封裝map實現。
 *
 * If no such object exists, the map should be "wrapped" using the
 * {@link Collections#synchronizedMap Collections.synchronizedMap}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the map:
 *   Map m = Collections.synchronizedMap(new HashMap(...));
 *
 * 如果沒有這樣的對象，map需要使用Collections.synchronizedMap方法封裝。最好室在創建的時候，防止意外
 * 異步訪問map，如：Map m = Collections.synchronizedMap(new HashMap(...));
 *
 * 
The iterators returned by all of this class"s "collection view methods"
 * are fail-fast: if the map is structurally modified at any time after
 * the iterator is created, in any way except through the iterator"s own
 * remove method, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of concurrent
 * modification, the iterator fails quickly and cleanly, rather than risking
 * arbitrary, non-deterministic behavior at an undetermined time in the
 * future.
 *
 * 迭代器返回了類所有“集合視圖方法”是fail-fast（錯誤的原因）：迭代器創建后，在任何時候進行結構化修改將會拋出
 * ConcurrentModificationException，不包括迭代器本身的remove方法，因此，在并發修改時，迭代器寧
 * 可快速而干凈的拋錯，也不任意存在，在不確定的行為，在不確定的時間的未來。（譯者注：意會下吧各位- -）
 *
 * 
Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw ConcurrentModificationException on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness: the fail-fast behavior of iterators
 * should be used only to detect bugs.
 *
 * 迭代器不能保證fail-fast行為，一般而言，在異步并發修改面前，不可能做 任何嚴格的保證。Fail-fast迭代器盡力地拋
 * ConcurrentModificationException。因此，編寫一個依賴于這個異常正確性的程序是錯誤的：
 * fail-fast行為只是用來檢測BUG.
 * 
 * 
This class is a member of the
 * 
 * Java Collections Framework.
 *
 * @param  the type of keys maintained by this map
 * @param  the type of mapped values
 *
 * @author  Doug Lea
 * @author  Josh Bloch
 * @author  Arthur van Hoff
 * @author  Neal Gafter
 * @see     Object#hashCode()
 * @see     Collection
 * @see     Map
 * @see     TreeMap
 * @see     Hashtable
 * @since   1.2
 */