hashmap 是一個(gè) key-value 形式的鍵值對集合。（本文內(nèi)容基于 JDK1.8）下面是一個(gè)簡單的 hashmap 的結(jié)構(gòu)。本文主要是通過源碼的方式分析 HashMap 的實(shí)現(xiàn)和優(yōu)化。主要是圍繞源碼本身展開，以添加注釋的方式進(jìn)行記錄和分析

初始化

在創(chuàng)建 HashMap 對象示例的時(shí)候不會(huì)初始化存儲(chǔ)數(shù)組，會(huì)在首次調(diào)用 put 方法的時(shí)候初始化數(shù)組。構(gòu)造方法如下：

public HashMap(int initialCapacity, float loadFactor) {
    // initialCapacity 初始容量 < 0 報(bào)錯(cuò); 默認(rèn) 16
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    // initialCapacity 初始容量是否大于最大容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // loadFactor 負(fù)載因子 <= 0 || isNaN ; 默認(rèn)0.75
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
復(fù)制代碼

put 方法

添加數(shù)據(jù)通常我們采用 put 方法，該方法也是我們開發(fā)中比較常用的方法之一。最終會(huì)調(diào)用 putVal 方法進(jìn)行初始化和添加數(shù)據(jù)。在這個(gè)方法中我們需要注意的有幾個(gè)地方：

如果沒有初始化會(huì)調(diào)用 resize() 方法進(jìn)行 hashmap 存儲(chǔ)數(shù)組的初始化。
默認(rèn)通過 & 運(yùn)算計(jì)算節(jié)點(diǎn)存儲(chǔ)位置，這里也證明了為什么初始化數(shù)組的長度要是 2 的 n 次方。
如果不存在 hash 沖突的情況下，通過然后調(diào)用 newNode 方法創(chuàng)建節(jié)點(diǎn)，存放到對應(yīng)的數(shù)組下標(biāo)。
如果存在 hsah 沖突的情況下。這里就會(huì)有三種情況：

首次 hash 沖突的情況下，當(dāng)前節(jié)點(diǎn)是一個(gè)普通的節(jié)點(diǎn)，如果 key 相同得話，將采取數(shù)據(jù)覆蓋的方式；
如果當(dāng)前節(jié)點(diǎn)類型是 treeNode 類型，是一棵紅黑樹。將調(diào)用 putTreeVal 方法來進(jìn)行添加子節(jié)點(diǎn)；
最后，將當(dāng)作鏈表處理，首先查找鏈表的尾節(jié)點(diǎn)，找到尾節(jié)點(diǎn)后，將當(dāng)前節(jié)點(diǎn)添加到尾節(jié)點(diǎn)，這里有一個(gè)判斷如果當(dāng)前鏈表的節(jié)點(diǎn)數(shù) > 8 并且 hashmap 的總長度 > 64 就會(huì)將當(dāng)前的鏈表進(jìn)行變換為紅黑樹。還有一種特殊情況，如果在鏈表的查找過程中查找到了一個(gè)當(dāng)前新增key 相同的節(jié)點(diǎn)，那么就會(huì)覆蓋當(dāng)前節(jié)點(diǎn)數(shù)據(jù)并且退出循環(huán)；

前面所有的步驟都是為了找到當(dāng)前的節(jié)點(diǎn)指針，然后再通過當(dāng)前對象修改 value 值，這里有一個(gè)需要注意的地方，在修改的時(shí)候會(huì)做一個(gè)判斷如果 **_onlyIfAbsent_** 等于 false 才可以修改，就是說可能當(dāng)前 hashmap 存在不可以被修改的情況，比如：map.putIfAbsent 方法的時(shí)候調(diào)用就會(huì)修改失敗，最后才能修改 value 值，并且返回舊值。
最后對修改次數(shù)累加，然后判斷一次是否需要拓展 hashmap 的容量，然后返回 null , 方法結(jié)束。

// put 方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

// putVal 方法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果沒有初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 調(diào)用 resize 初始化
        // n = tab.length 容量
        n = (tab = resize()).length;
    // 默認(rèn)通過 & 運(yùn)算計(jì)算節(jié)點(diǎn)存儲(chǔ)位置，這里也證明了為什么初始化數(shù)組的長度要是2的n 次方
    // 并且把當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)給 p
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 如果節(jié)點(diǎn)數(shù)據(jù)已經(jīng)存在，即存在 hash 沖突的情況
        Node<K,V> e; K k;
        // 1. 當(dāng)前節(jié)點(diǎn)存在，并且插入k，和存在的 k 的value 值相同，那么直接刷新當(dāng)前節(jié)點(diǎn)數(shù)據(jù)即可
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 新的節(jié)點(diǎn)數(shù)據(jù) = p, 其實(shí)這里也只是獲取 p 的指針
            e = p;
        // 2. 如果是 TreeNode 結(jié)構(gòu)， 即紅黑樹結(jié)構(gòu)
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 3. 其他情況，即鏈表結(jié)構(gòu)
            for (int binCount = 0; ; ++binCount) {
                // 父節(jié)點(diǎn)子節(jié)點(diǎn)為 null
                if ((e = p.next) == null) {
                    // 將 p.next = newNode
                    p.next = newNode(hash, key, value, null);
                    // 節(jié)點(diǎn)數(shù)是否大于變形的閾值 (TREEIFY_THRESHOLD = 8)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        // 如果 tab.length < 64 默認(rèn)拓容
                        // 否則進(jìn)行紅黑樹轉(zhuǎn)換
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果存在值相同的情況
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 如果 e 不為空，就是說當(dāng)前節(jié)點(diǎn)指針不為空，【這種情況是覆蓋】，返回舊值
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // 當(dāng)前節(jié)點(diǎn)可以被修改或者是新增節(jié)點(diǎn)
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 預(yù)留模板方法
            afterNodeAccess(e);
            return oldValue;
        }
    }
    // 修改次數(shù) ++
    ++modCount;
    // 大于拓容閾值
    if (++size > threshold)
        // 拓容
        resize();
    // 預(yù)留模板方法
    afterNodeInsertion(evict);
    return null;
}
復(fù)制代碼

總結(jié)：其實(shí)通過上面的分析和代碼的，我們分析出有一下幾個(gè)核心方法：

newNode 創(chuàng)建 Node 節(jié)點(diǎn)
((TreeNode<K,V>)p).putTreeVal(**this**, tab, hash, key, value);添加節(jié)點(diǎn)信息；
treeifyBin 節(jié)點(diǎn)沖突情況下，鏈表轉(zhuǎn)換為紅黑樹；
resize() HashMap 拓容；

newNode 創(chuàng)建節(jié)點(diǎn)

創(chuàng)建 HashMap 的節(jié)點(diǎn)信息，其實(shí)這個(gè)方法看上去比較普通，但是本質(zhì)上也是比較普通。但是對于 hash 這個(gè)參數(shù)我們可以思考一下。

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}
復(fù)制代碼

hash 計(jì)算 hash 碼

hash 方法如下，

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
復(fù)制代碼

理論上 hash 散列是一個(gè) int 值，如果直接拿出來作為下標(biāo)訪問 hashmap 的話，考慮到二進(jìn)制 32 位，取值范圍在**-2147483648 ~ 2147483647** 范圍。大概有 40 億個(gè) key ，只要哈希函數(shù)映射比較均勻松散，一般很難出現(xiàn)碰撞。存在一個(gè)問題是 40 億長度的數(shù)組，內(nèi)存是不能放下的。因?yàn)樵蹅?HashMap 的默認(rèn)長度為 16 。所以這個(gè) hashCode , (key.hashCode ) 是不能直接來使用的。使用之前先做對數(shù)組長度的與運(yùn)算，得到的值才能用來訪問數(shù)組下標(biāo)。代碼如下：

// n = hashmap 的長度
p = tab[i = (n - 1) & hash]) 
復(fù)制代碼

這里為什么要使用 n -1 ，來進(jìn)行與運(yùn)算，這里詳單與是一個(gè)”低位掩碼”, 以默認(rèn)長度 16 為例子。和某個(gè)數(shù)進(jìn)行與預(yù)算，結(jié)果的大小是 < 16 的。如下所示：

    10000000 00100000 00001001
&   00000000 00000000 00001111
------------------------------
    00000000 00000000 00001001  // 高位全部歸 0, 只保留后四位 
復(fù)制代碼

這個(gè)時(shí)候會(huì)有一個(gè)問題，如果本身的散列值分布松散，只要是取后面幾位的話，碰撞也會(huì)非常嚴(yán)重。還有如果散列本省做得不好的話，分布上成等差數(shù)列的漏洞，可能出現(xiàn)最后幾位出現(xiàn)規(guī)律性的重復(fù)。這個(gè)時(shí)候“擾動(dòng)函數(shù)”的價(jià)值制就體現(xiàn)出來了。如下所示：在 hash 函數(shù)中有這樣的一段代碼：(h = key.hashCode()) ^ (h >>> 16) 右位移 16 位，正好是32bit 的一半，與自己的高半?yún)^(qū)做成異或，就是為了**混合原始的哈希碼的高位和低位，以此來加大低位的隨機(jī)性。**并且混合后的低位摻雜了高位的部分特征，這樣高位的信息變相保存下來。其實(shí)按照開發(fā)經(jīng)驗(yàn)來說絕大多數(shù)情況使用的時(shí)候 hashmap 的長度不會(huì)超過 1000，所以提升低位的隨機(jī)性可以提升可以減少hash 沖突，提升程序性能。

如果感興趣的小伙伴可以瀏覽下一下 Peter Lawlay 的專欄《An introduction to optimising a hashing strategy》

Node.putTreeVal

當(dāng)前是一棵紅黑樹那么就需要添加節(jié)點(diǎn)

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;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> 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<K,V> 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<K,V> xp = p;
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> 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<K,V>)xpn).prev = x;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}
復(fù)制代碼

treeifyBin 鏈表樹化

如果 hashmap 的長度小于 64 會(huì)優(yōu)先選擇拓容，否則會(huì)當(dāng)前沖突 key 所在的結(jié)構(gòu)由鏈表轉(zhuǎn)換為紅黑樹。這個(gè)是 jdk 1.8 才有的新特征，hashmap 在 hash 沖突后可能由鏈表變化為紅黑樹結(jié)構(gòu)。這樣做的目的是為了提高讀寫效率。

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 不一定樹化還可能是拓容，需要看數(shù)組的長度是否小于 64 MIN_TREEIFY_CAPACITY
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        // hd 頭節(jié)點(diǎn), tl 尾節(jié)點(diǎn)
        TreeNode<K,V> hd = null, tl = null;
        do {
            // 將鏈表轉(zhuǎn)換為樹結(jié)構(gòu)
            TreeNode<K,V> 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)
            // 轉(zhuǎn)換紅黑樹操作，這里循環(huán)比較，染色、旋轉(zhuǎn)等
            hd.treeify(tab);
    }
}
復(fù)制代碼

replacementTreeNode 方法

replacementTreeNode 方法主要是將 Node 轉(zhuǎn)換為 TreeNode

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}
復(fù)制代碼

TreeNode#treeify 方法

treeify 方法主要是將樹結(jié)構(gòu)轉(zhuǎn)換為紅黑樹。

final void treeify(Node<K,V>[] tab) {
    // 根節(jié)點(diǎn)默認(rèn)為 null
    TreeNode<K,V> root = null;
    // 鏈表遍歷，x 指向當(dāng)前節(jié)點(diǎn)，next 指向下一個(gè)節(jié)點(diǎn)
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        // 下一個(gè)節(jié)點(diǎn)
        next = (TreeNode<K,V>)x.next;
        // 設(shè)置當(dāng)前節(jié)點(diǎn)的 left, right 為 null
        x.left = x.right = null;
        // 如果沒有根節(jié)點(diǎn)
        if (root == null) {
            // 當(dāng)前父節(jié)點(diǎn)為 null
            x.parent = null;
            // 當(dāng)前紅色節(jié)點(diǎn)屬性設(shè)置為 false (把當(dāng)前節(jié)點(diǎn)設(shè)置為黑色)
            x.red = false;
            // 根節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)
            root = x;
        }
        // 如果已經(jīng)存在根節(jié)點(diǎn)
        else {
            // 獲取當(dāng)前鏈表的 key
            K k = x.key;
            // 獲取當(dāng)前節(jié)點(diǎn)的 hash
            int h = x.hash;
            // 定義當(dāng)前 key 所屬類型
            Class<?> kc = null;
            // 從根節(jié)點(diǎn)開始遍歷，此遍歷設(shè)置邊界，只能從內(nèi)部跳出
            for (TreeNode<K,V> p = root;;) {
                // dir 標(biāo)識(shí)方向（左右）ph 標(biāo)識(shí)當(dāng)前節(jié)點(diǎn)的 hash 值
                int dir, ph;
                // 當(dāng)前節(jié)點(diǎn)的 key
                K pk = p.key;
                // 如果當(dāng)前節(jié)點(diǎn) hash 值大于當(dāng)前 鏈表節(jié)點(diǎn)的 hash 值
                if ((ph = p.hash) > h)
                    // 標(biāo)識(shí)當(dāng)前節(jié)鏈表節(jié)點(diǎn)會(huì)放在當(dāng)前紅黑樹節(jié)點(diǎn)的左側(cè)
                    dir = -1;
                else if (ph < h)
                    // 右側(cè)
                    dir = 1;
                // 如果兩個(gè)節(jié)點(diǎn)的 key 的 hash 值相等，那么通過其他方式進(jìn)行比較
                // 如果當(dāng)前鏈表節(jié)點(diǎn)的 key 實(shí)現(xiàn)了comparable 接口，并且當(dāng)前樹節(jié)點(diǎn)和鏈表節(jié)點(diǎn)是相同的 class 實(shí)例，那么通過 comparable 比較
                // 如果還是相等再通過 tieBreakOrder 比較一次
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p; // 保存當(dāng)前樹節(jié)點(diǎn)
                // 如果 dir 小于等于 0: 當(dāng)前鏈表節(jié)點(diǎn)一定放置在當(dāng)前樹節(jié)點(diǎn)的左側(cè)，但不一定是該樹節(jié)點(diǎn)的左子節(jié)點(diǎn)，
                // 也可能是左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)或者更深層次的節(jié)點(diǎn)
                // 如果dir 大于等于 0:  當(dāng)前鏈表節(jié)點(diǎn)一定放置在當(dāng)前樹節(jié)點(diǎn)的右側(cè)，但不一定是該樹節(jié)點(diǎn)的右子節(jié)點(diǎn)，
                // 也可能是右子節(jié)點(diǎn)或者左子節(jié)點(diǎn)或者更深層次的節(jié)點(diǎn)
                // 如果當(dāng)前樹節(jié)點(diǎn)不是葉子，那么最終以當(dāng)前樹節(jié)點(diǎn)的左子節(jié)點(diǎn)或者右子節(jié)點(diǎn)為起始幾點(diǎn)，然后再重新開始尋找自己當(dāng)前鏈表節(jié)點(diǎn)的位置。
                // 如果當(dāng)前樹節(jié)點(diǎn)就是葉子節(jié)點(diǎn)，那么更具 dir 的值，就可以把當(dāng)前鏈表節(jié)點(diǎn)掛載到當(dāng)前樹節(jié)點(diǎn)的左或者右側(cè)了。
                // 掛載之后，還需要重新把樹進(jìn)行平衡。平衡之后，就可以針對下一個(gè)鏈表節(jié)點(diǎn)進(jìn)行處理了
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp; // 當(dāng)前鏈表節(jié)點(diǎn)作為當(dāng)前樹節(jié)點(diǎn)的子節(jié)點(diǎn)
                    if (dir <= 0)
                        xp.left = x; // 左子節(jié)點(diǎn)
                    else
                        xp.right = x; // 右子節(jié)點(diǎn)
                    root = balanceInsertion(root, x); // 重新平衡
                    break;
                }
            }
        }
    }
    // 把所有的鏈表節(jié)點(diǎn)都遍歷之后，最終構(gòu)造出來的樹可能是經(jīng)歷多個(gè)平衡操作，根節(jié)點(diǎn)目前到底是鏈表的那個(gè)節(jié)點(diǎn)是不確定的
    // 因?yàn)槲覀冃枰跇鋪碜霾檎遥跃蛻?yīng)該把 tab[N] 得到的對象一定是根節(jié)點(diǎn)對象，而且是鏈表的第一個(gè)節(jié)點(diǎn)對象，所以要做對應(yīng)的調(diào)整。
    // 把紅黑樹的節(jié)點(diǎn)設(shè)置為所在數(shù)組槽的第一個(gè)元素
    // 說明: TreeNode 既是一個(gè)紅黑樹也是一個(gè)雙向鏈表
    // 這個(gè)方法做的事情是保證樹根節(jié)點(diǎn)一定要成為鏈表的首節(jié)點(diǎn)
    moveRootToFront(tab, root);
}
復(fù)制代碼

balanceInsertion 樹平衡

這個(gè)方法分析之前，我們可以先看看紅黑樹的規(guī)則：紅黑樹是每個(gè)結(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。
性質(zhì)2. 根節(jié)點(diǎn)是黑色。
性質(zhì)3. 所有葉子都是黑色。（葉子是NIL結(jié)點(diǎn)）
性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)都是黑色。（從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)）
性質(zhì)5. 從任一節(jié)節(jié)點(diǎn)其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

// root 為根節(jié)點(diǎn)
// x 為需要插入的節(jié)點(diǎn)
// 最后返回的是一個(gè)平很后的根節(jié)點(diǎn)
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 查詢節(jié)點(diǎn)標(biāo)記為紅色
    x.red = true;
    // 設(shè)置一個(gè)只可以內(nèi)部退出的循環(huán)
    // 變量說明: 
    // xp 當(dāng)前節(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)為空， 說明當(dāng)前節(jié)點(diǎn)就是根節(jié)點(diǎn)，那么直接把當(dāng)前接待你標(biāo)記為黑色返回當(dāng)前節(jié)點(diǎn)。
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        // 如果當(dāng)前節(jié)點(diǎn)為黑設(shè)色并且當(dāng)前父節(jié)點(diǎn)為 null, 或者
        // 父節(jié)點(diǎn)為紅色，但是 xpp 節(jié)點(diǎn)為空
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        // 當(dāng)前節(jié)點(diǎn)等于 xppl
        if (xp == (xppl = xpp.left)) {
            //xppr != null 并且 是紅色
            if ((xppr = xpp.right) != null && xppr.red) {
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                x = xpp; // 當(dāng)前節(jié)點(diǎn)等于 xpp, 進(jìn)入下一次循環(huán)
            }
            else {
                if (x == xp.right) { // 當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)
                    root = rotateLeft(root, x = xp); //父節(jié)點(diǎn)左旋
                    xpp = (xp = x.parent) == null ? null : xp.parent; // 獲取 xpp
                }
                if (xp != null) { // 父節(jié)點(diǎn)不為空
                    xp.red = false; // 父節(jié)點(diǎn)設(shè)置為黑色
                    if (xpp != null) { // xpp 不為空
                        xpp.red = true; // xpp 為紅色
                        root = rotateRight(root, xpp); // xpp 右旋轉(zhuǎn)
                    }
                }
            }
        }
        else { // 如果 xp 是 xpp 的右節(jié)點(diǎn)
            if (xppl != null && xppl.red) { // xppl 不為空，并且為紅色
                xppl.red = false; // xppl 設(shè)置為黑色
                xp.red = false; // 父節(jié)點(diǎn)為黑色
                xpp.red = true; // xpp 為紅色
                x = xpp;  // x = xpp 進(jìn)入下次循環(huán)
            }
            else {
                if (x == xp.left) { // 當(dāng)前節(jié)點(diǎn)為父節(jié)點(diǎn)的左子節(jié)點(diǎn)
                    root = rotateRight(root, x = xp); // 根節(jié)點(diǎn)你右旋轉(zhuǎn)
                    xpp = (xp = x.parent) == null ? null : xp.parent; // xpp = xp.parent
                }
                if (xp != null) { // xp != null
                    xp.red = false; // xp 為黑色
                    if (xpp != null) { // xpp != null 
                        xpp.red = true; // xpp 為紅色
                        root = rotateLeft(root, xpp); // 左旋
                    }
                }
            }
        }
    }
}


// 節(jié)點(diǎn)左旋轉(zhuǎn)
// root 當(dāng)前根節(jié)點(diǎn)
// p 指定選裝的節(jié)點(diǎn)
// 返回旋轉(zhuǎn)后的根接待你（平衡涉及左旋右旋根根節(jié)點(diǎn)改變，所以需要返回最新的根節(jié)點(diǎn)）
// 示意圖
//        pp                    pp
//        |                     |  
//        p         --->        r
//       / \                   / \
//      l   r                 p  rr 
//         / \               / \
//        rl  rr            l  rl
// 旋轉(zhuǎn)做了幾件事情？
// 1. 將 rl 設(shè)置為 p 的子接待你，將 rl 設(shè)置為父節(jié)點(diǎn) p 
// 2. 將 r 的父節(jié)點(diǎn)設(shè)置 pp, 將 pp 的左子節(jié)點(diǎn)設(shè)或者右子接待你設(shè)置為 r 
// 3. 將 r 的左子節(jié)點(diǎn)設(shè)置為 p, 將 p 的父節(jié)點(diǎn)設(shè)置為 r
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                      TreeNode<K,V> p) {
    TreeNode<K,V> r, pp, rl;
    // 左旋的節(jié)點(diǎn)以及需要左旋的節(jié)點(diǎn)的右節(jié)點(diǎn)不為空
    if (p != null && (r = p.right) != null) { 
        // 要左旋轉(zhuǎn)的右子節(jié)點(diǎn) = rl , 
        if ((rl = p.right = r.left) != null) 
            // 設(shè)置 rl 父親節(jié)點(diǎn)設(shè)置為 p
            rl.parent = p; 
        // 將 r 的父節(jié)點(diǎn)設(shè)置為 p 的父節(jié)點(diǎn)，如果 pp == null 
        if ((pp = r.parent = p.parent) == null) 
            // 染黑
            (root = r).red = false; 
        else if (pp.left == p) // 判斷父節(jié)點(diǎn)是在 pp 的左邊還是右邊
            pp.left = r; // 如果是左子節(jié)點(diǎn)，把 pp.letf = r
        else
            pp.right = r; // 如果是右子節(jié)點(diǎn), pp.reight = r
        r.left = p; // 最后將 r的左子節(jié)點(diǎn)設(shè)置為 p
        p.parent = r; // 最后將 p.parent 設(shè)置為 r
    }
    return root;
}

// 節(jié)點(diǎn)右旋轉(zhuǎn)
// 右旋同理
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                       TreeNode<K,V> p) {
    TreeNode<K,V> 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;
}

復(fù)制代碼

moveRootToFront 方法

把所有的鏈表節(jié)點(diǎn)都遍歷之后，最終構(gòu)造出來的樹可能是經(jīng)歷多個(gè)平衡操作，根節(jié)點(diǎn)目前到底是鏈表的那個(gè)節(jié)點(diǎn)是不確定的。因?yàn)槲覀冃枰跇鋪碜霾檎遥跃蛻?yīng)該把 tab[N] 得到的對象一定是根節(jié)點(diǎn)對象，而且是鏈表的第一個(gè)節(jié)點(diǎn)對象，所以要做對應(yīng)的調(diào)整。把紅黑樹的節(jié)點(diǎn)設(shè)置為所在數(shù)組槽的第一個(gè)元素，這個(gè)方法做的事情是保證樹根節(jié)點(diǎn)一定要成為鏈表的首節(jié)點(diǎn)。

static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
    int n;
    // root 節(jié)點(diǎn)不為空， 并且表不為空， 并且數(shù)組長度大于 0
    if (root != null && tab != null && (n = tab.length) > 0) {
        // 當(dāng)前 Node 所在槽位
        int index = (n - 1) & root.hash;
        // 獲取當(dāng)前槽所在接待你
        TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
        // 如果當(dāng)前槽位節(jié)點(diǎn)不是首節(jié)點(diǎn)
        if (root != first) {
            // 后驅(qū)節(jié)點(diǎn)
            Node<K,V> rn;
            // 修改為首節(jié)點(diǎn)
            tab[index] = root;
            // rp 前驅(qū)節(jié)點(diǎn)為 root 的前驅(qū)節(jié)點(diǎn)
            TreeNode<K,V> rp = root.prev;
            // 后驅(qū)節(jié)點(diǎn)不為空
            if ((rn = root.next) != null)
                ((TreeNode<K,V>)rn).prev = rp;
            if (rp != null)
                rp.next = rn;
            if (first != null) 
                // 原來的頭節(jié)點(diǎn)前驅(qū)節(jié)點(diǎn)指向新的頭節(jié)點(diǎn) root 節(jié)點(diǎn)
                first.prev = root;
            // root 節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)指向之前的頭節(jié)點(diǎn)
            root.next = first;
            // root 由于是頭節(jié)點(diǎn)所以前驅(qū)節(jié)點(diǎn)為 null
            root.prev = null;
        }
        assert checkInvariants(root);
    }
}
復(fù)制代碼

remove 方法

remove 方法的本質(zhì)是將 key 值所在的節(jié)點(diǎn)的值設(shè)置為 nu

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}
復(fù)制代碼

removeNode 方法

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    // tab 不為空, 數(shù)組長度大于 0, 當(dāng)前節(jié)點(diǎn)數(shù)據(jù)不為 null
    // 不得不說 hashmap 源碼的邏輯還是非常嚴(yán)謹(jǐn)?shù)?/span>
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        // node 用來存儲(chǔ)當(dāng)前節(jié)點(diǎn)信息
        Node<K,V> node = null, e; K k; V v;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        else if ((e = p.next) != null) {
            // 如果是樹形結(jié)構(gòu)
            if (p instanceof TreeNode)
                // 獲取節(jié)點(diǎn)
                node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
            else {
                // 鏈表查找
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            // 如果是紅黑樹，刪除節(jié)點(diǎn)
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p) // 如果是頭節(jié)點(diǎn)
                // 那么頭節(jié)點(diǎn)指針指向移除節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)
                tab[index] = node.next;
            else
                // 前驅(qū)節(jié)點(diǎn)的后驅(qū)指針，指向當(dāng)前節(jié)點(diǎn)的后驅(qū)指針
                p.next = node.next;
            // 修改次數(shù)累加
            ++modCount;
            // 數(shù)據(jù)長度減少
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}
復(fù)制代碼

removeTreeNode 方法

removeTreeNode 是刪除節(jié)點(diǎn)的核心方法，刪除的時(shí)候如果是一個(gè)普通節(jié)點(diǎn)就可以直接情況，如果是鏈表的話需要將當(dāng)前節(jié)點(diǎn)刪除。如果是紅黑樹的話，需要?jiǎng)h除 TreeNode , 然后進(jìn)行一次樹平衡，或者將樹轉(zhuǎn)換為鏈表。

final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                          boolean movable) {
    int n;
    if (tab == null || (n = tab.length) == 0)
        return;
    // 獲取索引值
    int index = (n - 1) & hash;
    // 獲取頭節(jié)點(diǎn)，即樹的根節(jié)點(diǎn)
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    // 當(dāng)前節(jié)點(diǎn)的后驅(qū)節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)保存
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    // 前驅(qū)節(jié)點(diǎn)為 null 
    if (pred == null)
        // 當(dāng)前是頭節(jié)點(diǎn)，刪除之后，頭節(jié)點(diǎn)直接指向了刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    // 如果頭節(jié)點(diǎn)（即根節(jié)點(diǎn)）為空，說明當(dāng)前節(jié)點(diǎn)刪除后，紅黑樹為空，直接返回
    if (first == null)
        return;
    // 如果頭接單不為空，直接調(diào)用 root() 方法獲取根節(jié)點(diǎn)
    if (root.parent != null)
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        // 鏈表化，英文前面的鏈表節(jié)點(diǎn)完成刪除操作，故這里直接返回，即可完成節(jié)點(diǎn)刪除
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    
    // p 當(dāng)前節(jié)點(diǎn); pl 當(dāng)前節(jié)點(diǎn)左節(jié)點(diǎn)，pr 當(dāng)前節(jié)點(diǎn)右節(jié)點(diǎn)
    // replacement p 節(jié)點(diǎn)刪除后替代的節(jié)點(diǎn)
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if (pl != null && pr != null) {
        // p 節(jié)點(diǎn)刪除后， 他的左右節(jié)點(diǎn)不為空時(shí)， 遍歷他的右節(jié)點(diǎn)上的左子樹
        // （以下操作先讓 p 節(jié)點(diǎn)和 s 節(jié)點(diǎn)交換位置，然后再找到 replacement 節(jié)點(diǎn)替換他 ）
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
            s = sl;
        // 通過上述操作 s 節(jié)點(diǎn)是大于 p 節(jié)點(diǎn)的最小節(jié)點(diǎn)（替換它的節(jié)點(diǎn)）
        // 將 s 節(jié)點(diǎn)和 p 節(jié)點(diǎn)的顏色交換
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        // sr  s 節(jié)點(diǎn)的右節(jié)點(diǎn)
        TreeNode<K,V> sr = s.right;
        // pp  p 節(jié)點(diǎn)的父節(jié)點(diǎn)
        TreeNode<K,V> pp = p.parent;
        // 如果 pr 就是 s 節(jié)點(diǎn)
        if (s == pr) { // p was s's direct parent
            // 節(jié)點(diǎn)交換
            p.parent = s;
            s.right = p;
        }
        else {
            // 獲取 s 的父節(jié)點(diǎn)
            TreeNode<K,V> sp = s.parent;
            // 將 p 節(jié)點(diǎn)的父節(jié)點(diǎn)指向 sp, 且 sp 節(jié)點(diǎn)存在
            if ((p.parent = sp) != null) {
                // 判斷 s 節(jié)點(diǎn)的 sp 節(jié)點(diǎn)在左側(cè)還是右側(cè)， 將 p 節(jié)點(diǎn)存放在 s 節(jié)點(diǎn)一側(cè)
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            // 將 pr 節(jié)點(diǎn)編程 s 節(jié)點(diǎn)的右節(jié)點(diǎn)，并且 pr 節(jié)點(diǎn)存在
            if ((s.right = pr) != null)
                // 將 s 節(jié)點(diǎn)編程 pr 節(jié)點(diǎn)的父節(jié)點(diǎn)
                pr.parent = s;
        }
        // 因?yàn)?s 節(jié)點(diǎn)的性質(zhì)， s 節(jié)點(diǎn)沒有左節(jié)點(diǎn)
        // 當(dāng) p 節(jié)點(diǎn)和 s 節(jié)點(diǎn)交換了位置，所以將 p 節(jié)點(diǎn)的左幾點(diǎn)指向空
        p.left = null;
        
        // 將 sr 節(jié)點(diǎn)編程 p 節(jié)點(diǎn)的左節(jié)點(diǎn)，并且 sr 節(jié)點(diǎn)存在
        if ((p.right = sr) != null)
            // 將 p 節(jié)點(diǎn)編程 sr 的父節(jié)點(diǎn)
            sr.parent = p;
        // 將 pl 節(jié)點(diǎn)編程 s 節(jié)點(diǎn)的左節(jié)點(diǎn)，并且存在 pl 節(jié)點(diǎn)
        if ((s.left = pl) != null)
            // 將 pl 父節(jié)點(diǎn)賦值為s
            pl.parent = s;
        // s 父節(jié)點(diǎn)設(shè)置為 pp 并且 pp 節(jié)點(diǎn)存在
        if ((s.parent = pp) == null)
            // root 節(jié)點(diǎn)為 s
            root = s;
        // p 節(jié)點(diǎn)等于 pp.left 
        else if (p == pp.left)
            // pp 的左節(jié)點(diǎn)為 s
            pp.left = s;
        else
            // p 節(jié)點(diǎn)等于 pp.right 
            // pp 右節(jié)點(diǎn)為 s
            pp.right = s;
        
        // sr 不為空
        if (sr != null)
            // 替換節(jié)點(diǎn)為 sr
            replacement = sr;
        else
            // 否則替換節(jié)點(diǎn)為 p 
            replacement = p;
    }
    else if (pl != null)
        // 如果 pl 節(jié)點(diǎn)存在， pr 節(jié)點(diǎn)不存在，不用交換位置， pl 節(jié)點(diǎn)為替換為 replacement 節(jié)點(diǎn)
        replacement = pl;
    else if (pr != null)
        // 如果 pr 節(jié)點(diǎn)存在,  pl 節(jié)點(diǎn)不存在， 不用交換位置， pr 節(jié)點(diǎn)為替換為 replacement 節(jié)點(diǎn)
        replacement = pr;
    else
        // 如果都不存在 p 節(jié)點(diǎn)成為 replacement 節(jié)點(diǎn)
        replacement = p;
    
    // 以下判斷根據(jù)上述邏輯查看，僅以p 節(jié)點(diǎn)的當(dāng)前位置為性質(zhì)， 對 replacement 節(jié)點(diǎn)進(jìn)行操作
    if (replacement != p) {
        // 如果 replacement 不是 p 節(jié)點(diǎn)
        // 將 p 節(jié)點(diǎn)的父節(jié)點(diǎn) pp 變成 replacement 節(jié)點(diǎn)的父節(jié)點(diǎn)
        TreeNode<K,V> pp = replacement.parent = p.parent;
        // 如果 pp 節(jié)點(diǎn)不存在
        if (pp == null)
            // replacement 變成根節(jié)點(diǎn)
            root = replacement;
        else if (p == pp.left)
            // 如果 pp 節(jié)點(diǎn)存在，根據(jù) p 節(jié)點(diǎn)在 pp 節(jié)點(diǎn)的位置，設(shè)置 replacement 節(jié)點(diǎn)的位置
            pp.left = replacement;
        else
            pp.right = replacement;
        
        // 將 p 節(jié)點(diǎn)所有的引用關(guān)系設(shè)置為 null
        p.left = p.right = p.parent = null;
    }

    // 如果 p 節(jié)點(diǎn)是紅色，刪除后不影響  root 節(jié)點(diǎn)，如果是黑色，找到平衡后的根節(jié)點(diǎn)，并且用 r 表示
    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    // 如果 p 是 replacement 節(jié)點(diǎn)
    if (replacement == p) {  // detach
        // 得到 pp
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            // pp 存在
            // 根據(jù) p 節(jié)點(diǎn)的位置，將 pp 節(jié)點(diǎn)的對應(yīng)為位置設(shè)置為空
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    // 移動(dòng)新的節(jié)點(diǎn)到數(shù)組上
    if (movable)
        moveRootToFront(tab, r);
}
復(fù)制代碼

balanceDeletion 方法

刪除節(jié)點(diǎn)后的樹平衡方法。

static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                           TreeNode<K,V> x) {
    // x 當(dāng)前需要?jiǎng)h除的節(jié)點(diǎn)
    // xp x 父節(jié)點(diǎn)
    // xpl x 父節(jié)點(diǎn)的左子節(jié)點(diǎn)
    // xpr x 父節(jié)點(diǎn)的右子節(jié)點(diǎn)
    for (TreeNode<K,V> xp, xpl, xpr;;) {
        if (x == null || x == root)
            // x 為空或者 x 為根節(jié)點(diǎn)
            return root;
        else if ((xp = x.parent) == null) {
            // 當(dāng) xp 為空，說明 x 為根節(jié)點(diǎn)，將 x 設(shè)置為黑色并且返回 x 節(jié)點(diǎn)。
            x.red = false;
            return x;
        }
        else if (x.red) {
            // x節(jié)點(diǎn)是紅色，無需調(diào)整
            x.red = false;
            return root;
        }
        else if ((xpl = xp.left) == x) {
            // 如果x節(jié)點(diǎn)為xpl節(jié)點(diǎn)
            if ((xpr = xp.right) != null && xpr.red) {
                // 如果xpr節(jié)點(diǎn)不為空，且xpr節(jié)點(diǎn)是紅色的
                // 將xpr設(shè)置為黑色，xp設(shè)置為紅色
                xpr.red = false;
                xp.red = true;
                // 左旋
                root = rotateLeft(root, xp);
                // 重新將xp節(jié)點(diǎn)指向x節(jié)點(diǎn)的父節(jié)點(diǎn)，并將xpr節(jié)點(diǎn)指向xp的右節(jié)點(diǎn)
                xpr = (xp = x.parent) == null ? null : xp.right;
            }
            if (xpr == null)
                // 若xpr節(jié)點(diǎn)不存在
                // 則將x節(jié)點(diǎn)指向xp節(jié)點(diǎn)向上調(diào)整                
                x = xp;
            else {
                // sl xpr節(jié)點(diǎn)的左節(jié)點(diǎn)
                // sr xpr節(jié)點(diǎn)的右節(jié)點(diǎn)                
                TreeNode<K,V> sl = xpr.left, sr = xpr.right;
                if ((sr == null || !sr.red) &&
                    (sl == null || !sl.red)) {
                    // 若sr節(jié)點(diǎn)為空或者sr節(jié)點(diǎn)是黑色的，且sl節(jié)點(diǎn)為空或者sl節(jié)點(diǎn)是黑色的
                    // 將xpr節(jié)點(diǎn)變成紅色
                    xpr.red = true;
                    // 則將x節(jié)點(diǎn)指向xp節(jié)點(diǎn)向上調(diào)整
                    x = xp;
                }
                else {
                    //sr和sl中存在一個(gè)紅節(jié)點(diǎn)
                    if (sr == null || !sr.red) {
                        //此處說明sl是紅節(jié)點(diǎn),將sl節(jié)點(diǎn)設(shè)置為黑色
                        if (sl != null)
                            sl.red = false;
                        //將xpr節(jié)點(diǎn)設(shè)置為紅色
                        xpr.red = true;
                        //右旋
                        root = rotateRight(root, xpr);
                        //將xpr節(jié)點(diǎn)重新指向xp節(jié)點(diǎn)的右節(jié)點(diǎn)
                        xpr = (xp = x.parent) == null ?
                            null : xp.right;
                    }
                    if (xpr != null) {
                        //如果xpr節(jié)點(diǎn)不為空,讓xpr節(jié)點(diǎn)與xp節(jié)點(diǎn)同色
                        xpr.red = (xp == null) ? false : xp.red;
                        //當(dāng)sr節(jié)點(diǎn)不為空，變成黑色
                        if ((sr = xpr.right) != null)
                            sr.red = false;
                    }
                    //存在xp節(jié)點(diǎn)

                    if (xp != null) {
                        //將xp節(jié)點(diǎn)設(shè)置為黑色
                        xp.red = false;
                        //進(jìn)行左旋
                        root = rotateLeft(root, xp);

                    }
                    //將x節(jié)點(diǎn)指向root進(jìn)行下一次循環(huán)時(shí)跳出
                    x = root;
                }
            }
        }
        else { // symmetric
            //當(dāng)x節(jié)點(diǎn)是右節(jié)點(diǎn)
            if (xpl != null && xpl.red) {
                //當(dāng)xpl節(jié)點(diǎn)存在且為紅色
                //將xpl變?yōu)楹谏瑇p變?yōu)榧t色
                xpl.red = false;
                xp.red = true;
                //右旋
                root = rotateRight(root, xp);
                //將xpl節(jié)點(diǎn)重新指向xp節(jié)點(diǎn)的左節(jié)點(diǎn)
                xpl = (xp = x.parent) == null ? null : xp.left;
            }
            if (xpl == null)
                //如果xpl節(jié)點(diǎn)不存在，則xp節(jié)點(diǎn)沒有子節(jié)點(diǎn)了
                //將x節(jié)點(diǎn)指向xp節(jié)點(diǎn)向上調(diào)整
                x = xp;
            else {
                //sl xpl節(jié)點(diǎn)的左節(jié)點(diǎn)
                //sr xpl節(jié)點(diǎn)的右節(jié)點(diǎn)
                TreeNode<K,V> sl = xpl.left, sr = xpl.right;
                if ((sl == null || !sl.red) &&
                    (sr == null || !sr.red)) {
                    //若sr節(jié)點(diǎn)為空或者sr節(jié)點(diǎn)是黑色的，且sl節(jié)點(diǎn)為空或者sl節(jié)點(diǎn)是黑色的
                    //將xpl節(jié)點(diǎn)變成紅色
                    xpl.red = true;
                    //則將x節(jié)點(diǎn)指向xp節(jié)點(diǎn)向上調(diào)整
                    x = xp;
                }
                else {
                    //sr和sl中存在一個(gè)紅節(jié)點(diǎn)
                    if (sl == null || !sl.red) {
                        //此處說明sr是紅節(jié)點(diǎn),將sr節(jié)點(diǎn)設(shè)置為黑色
                        if (sr != null)
                            sr.red = false;
                        //將xpr節(jié)點(diǎn)設(shè)置為紅色
                        xpl.red = true;
                        //左旋
                        root = rotateLeft(root, xpl);
                        //將xpl節(jié)點(diǎn)重新指向xp節(jié)點(diǎn)的左節(jié)點(diǎn)
                        xpl = (xp = x.parent) == null ?
                            null : xp.left;
                    }
                    //如果xpl節(jié)點(diǎn)存在
                    if (xpl != null) {
                        //使xpl節(jié)點(diǎn)與xp節(jié)點(diǎn)同色
                        xpl.red = (xp == null) ? false : xp.red;
                        //如果sl節(jié)點(diǎn)存在
                        if ((sl = xpl.left) != null)
                            //將sl節(jié)點(diǎn)變?yōu)楹谏?/span>

                            sl.red = false;
                    }
                    // 如果xp節(jié)點(diǎn)存在
                    if (xp != null) {
                        // 將xp節(jié)點(diǎn)設(shè)置為黑色
                        xp.red = false;
                        // 右旋
                        root = rotateRight(root, xp);
                    }
                    // 將x節(jié)點(diǎn)指向root進(jìn)行下一次循環(huán)時(shí)跳出
                    x = root;
                }
            }
        }
    }
}


復(fù)制代碼

線程安全

HashMap 不是線程安全的集合，如果要使用線程安全的 k-v 集合可以使用 CurrentHashMap.

注意事項(xiàng)

使用 Map 的方法 keySet()/values()/entrySet()返回集合對象時(shí)，不可以對其進(jìn)行添加元素操作，否則會(huì)拋出 UnsupportedOperationException 異常。

集合初始化時(shí)，指定集合初始值大小解釋：HashMap 使用 HashMap(int initialCapacity) 初始化，如果暫時(shí)無法確定集合大小，那么指定默認(rèn)值（16）即可。initialCapacity = (需要存儲(chǔ)的元素個(gè)數(shù) / 負(fù)載因子) + 1。注意負(fù)載因子（即 loader factor）默認(rèn)為 0.75，如果暫時(shí)無法確定初始值大小，請?jiān)O(shè)置為 16（即默認(rèn)值）舉例：HashMap 需要放置 1024 個(gè)元素，由于沒有設(shè)置容量初始大小，隨著元素增加而被迫不斷擴(kuò)容， resize()方法總共會(huì)調(diào)用 8 次，反復(fù)重建哈希表和數(shù)據(jù)遷移。當(dāng)放置的集合元素個(gè)數(shù)達(dá)千萬級(jí)時(shí)會(huì)影響程序性能。

使用 entrySet 遍歷 Map 類集合 KV，而不是 keySet 方式進(jìn)行遍歷。說明：keySet 其實(shí)是遍歷了 2 次，一次是轉(zhuǎn)為 Iterator 對象，另一次是從 hashMap 中取出 key 所對應(yīng)的value。而 entrySet 只是遍歷了一次就把 key 和 value 都放到了 entry 中，效率更高。如果是 JDK8，使用Map.forEach 方法。values()返回的是 V 值集合，是一個(gè) list 集合對象；keySet()返回的是 K 值集合，是一個(gè) Set 集合對象；entrySet()返回的是 K-V 值組合集合。

Map 類集合 K/V 能不能存儲(chǔ) null 值的情況，如下表格：

集合類	Key	Value	Super	說明
hashtable	不允許為 null	不允許為 null	Dictionary	線程安全
ConcurrentHashMap	不允許為 null	不允許為 null	AbstractMap	鎖分段技術(shù)（JDK8: CAS）
TreeMap	不允許為 null	允許為 null	AbstractMap	線程不安全
HashMap	允許為 null	允許為 null	AbstractMap	線程不安全

由于 HashMap 的干擾，很多人認(rèn)為 ConcurrentHashMap 是可以置入 null 值，而事實(shí)上，存儲(chǔ)null 值時(shí)會(huì)拋出 NPE 異常

本文總結(jié)

本文主要是說了 hashmap 的初始化過程，以及 hashcode 的計(jì)算方式。對于紅黑樹轉(zhuǎn)化這部分只代碼做了一些簡單的代碼翻譯。
對于 hashmap 紅黑樹這塊邏輯由于涉及到數(shù)據(jù)結(jié)構(gòu)，以后再希望有時(shí)間在做一篇文章單獨(dú)描述。
對于 hashmap 拓容，以及紅黑樹轉(zhuǎn)鏈表部分也會(huì)在后面的更新中補(bǔ)充。

參考資料

www.zhihu.com/question/20…
www.jianshu.com/p/2c7a4a4e1…
blog.csdn.net/weixin_4234…

作者：老鄭_
鏈接：https://juejin.cn/post/6996999840743817224
來源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

HashMap 的設(shè)計(jì)與優(yōu)化

初始化