摘要：表示該類本身不可比表示與對(duì)應(yīng)的之間不可比。當(dāng)數(shù)目滿足時(shí)，鏈表將轉(zhuǎn)為紅黑樹結(jié)構(gòu)，否則繼續(xù)擴(kuò)容。至此，插入告一段落。當(dāng)超出時(shí)，哈希表將會(huì)即內(nèi)部數(shù)據(jù)結(jié)構(gòu)重建至大約兩倍。要注意的是使用許多有這相同的鍵值肯定會(huì)降低哈希表性能。

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

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

// 為了找到合適的位置插入新節(jié)點(diǎn)，源碼中進(jìn)行了一系列比較。
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; // 獲取根節(jié)點(diǎn)，從根節(jié)點(diǎn)開始遍歷
    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;
        }
    }
}

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

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

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

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

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;
}

有沒有發(fā)現(xiàn)，如果當(dāng)你看懂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父節(jié)點(diǎn)為黑 || x父節(jié)點(diǎn)為根（黑）
        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()的作用就是要維持這種“平衡”，保證最佳效率。所謂的紅黑樹“平衡”即：

①：所有節(jié)點(diǎn)非黑即紅；
②：根為黑，葉子為null且為黑，紅的兩子節(jié)點(diǎn)為黑；
③：任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的黑子節(jié)點(diǎn)個(gè)數(shù)相同；

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

圖②中打鉤的都是合格的紅黑樹其實(shí)，圖②右邊方框內(nèi)為左旋右旋節(jié)點(diǎn)關(guān)系變化圖解。

// 左旋 與 右旋
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左子節(jié)點(diǎn)
        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;
}

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

同時(shí)，在線紅黑樹插入刪除動(dòng)畫演示【點(diǎn)我】，還不理解的童鞋可以親自直觀的試試。

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()在鏈表中數(shù)目大于等于“TREEIFY_THRESHOLD - 1”時(shí)觸發(fā)。當(dāng)數(shù)目滿足MIN_TREEIFY_CAPACITY時(shí)，鏈表將轉(zhuǎn)為紅黑樹結(jié)構(gòu)，否則繼續(xù)擴(kuò)容。treeify()類似putTreeVal()。

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

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

附上前一段時(shí)間翻譯的HashMap源碼開篇注釋，將開頭作為總結(jié)。也算收尾呼應(yīng)吧。

/**
 * 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.
 *
 * 哈希表實(shí)現(xiàn)了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.
 *
 * 在哈希函數(shù)將元素恰當(dāng)?shù)姆植荚谕爸械那闆r下，接口提供了穩(wěn)定的基礎(chǔ)操作（get和put）。
 * 遍歷集合的時(shí)間與HashMap實(shí)例的 “容量”(hash桶的數(shù)量) + “大小”（鍵值對(duì)數(shù)量）的和成正比。
 * 因此，當(dāng)循環(huán)比重較大時(shí)，初始容量值不能設(shè)的太大（或者負(fù)載因子太小）是非常重要的。
 *
 * 
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.
 *
 * 兩個(gè)參數(shù)影響著HashMap實(shí)例：“初始容量”和“負(fù)載因子”。“初始容量”指的是哈希表中桶的數(shù)量，在哈希表創(chuàng)建的同時(shí)初始化。
 * “負(fù)載因子”度量著哈希表能裝多滿（譯者注：相對(duì)于桶的形象概念，建議參看網(wǎng)上hashMap結(jié)構(gòu)圖理解）直到在自動(dòng)擴(kuò)容。
 * 當(dāng)超出時(shí)，哈希表將會(huì)rehashed（即內(nèi)部數(shù)據(jù)結(jié)構(gòu)重建）至大約兩倍。
 *
 * 
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.
 *
 * 一般來說，默認(rèn)負(fù)載因子（0.75）在時(shí)間和空間之間起到了很好的權(quán)衡。更大的值雖然減輕了空間負(fù)荷卻增加了查找花銷
 * （在大多數(shù)HashMap操作上都有體現(xiàn)，包括get和put）。當(dāng)設(shè)置map初始容量時(shí)，需要考慮預(yù)期條目數(shù)和它的負(fù)載因子
 * 使得rehash操作次數(shù)最少。如果初始容量大于最大條目數(shù)/負(fù)載因子，甚至不會(huì)發(fā)生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.
 *
 * 如果大量的鍵值對(duì)將存儲(chǔ)在HashMap實(shí)例中，使用一個(gè)足夠大的容量來初始化遠(yuǎn)比讓它自動(dòng)按需rehash擴(kuò)容的效率高。
 * 要注意的是使用許多有這相同hashCode()的鍵值肯定會(huì)降低哈希表性能。為了降低影響，當(dāng)key支持Comparable接口時(shí)，
 * 在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是非線程安全的。如果多線程同時(shí)訪問一個(gè)哈希表，并且至少一個(gè)線程在修改map結(jié)構(gòu)是，必須在外加上
 * synchronized關(guān)鍵字。（結(jié)構(gòu)化修改包括任何增刪一個(gè)或者多個(gè)鍵值對(duì)；只修改一個(gè)已存在的key的值不屬于
 * 結(jié)構(gòu)修改。）典型的是用同步對(duì)象封裝map實(shí)現(xiàn)。
 *
 * 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(...));
 *
 * 如果沒有這樣的對(duì)象，map需要使用Collections.synchronizedMap方法封裝。最好室在創(chuàng)建的時(shí)候，防止意外
 * 異步訪問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（錯(cuò)誤的原因）：迭代器創(chuàng)建后，在任何時(shí)候進(jìn)行結(jié)構(gòu)化修改將會(huì)拋出
 * ConcurrentModificationException，不包括迭代器本身的remove方法，因此，在并發(fā)修改時(shí)，迭代器寧
 * 可快速而干凈的拋錯(cuò)，也不任意存在，在不確定的行為，在不確定的時(shí)間的未來。（譯者注：意會(huì)下吧各位- -）
 *
 * 
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行為，一般而言，在異步并發(fā)修改面前，不可能做 任何嚴(yán)格的保證。Fail-fast迭代器盡力地拋
 * ConcurrentModificationException。因此，編寫一個(gè)依賴于這個(gè)異常正確性的程序是錯(cuò)誤的：
 * fail-fast行為只是用來檢測(cè)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
 */