目的

深入講解HashMap源碼藕溅，如題，將從put(K key, V value)方法調(diào)用開(kāi)始

put方法

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

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

當(dāng)傳入一個(gè)key和value時(shí)，第一步將調(diào)用hash(Object key)方法計(jì)算key的哈希值，返回int類型。內(nèi)部調(diào)用key的hashCode()返回32位int類型的哈希值宪拥，同時(shí)將獲取的哈希值無(wú)符號(hào)向右移動(dòng)16位，再和原來(lái)的32位哈希值進(jìn)行異或運(yùn)算得到一個(gè)新的哈希值作為hash(Object key)的返回值返回

這里會(huì)有一個(gè)問(wèn)題铣减，為什么要無(wú)符號(hào)右移16位之后再和原來(lái)的進(jìn)行異或運(yùn)算再返回她君？
這里涉及到獲取哈希值后計(jì)算存放在數(shù)組中的哪一個(gè)下標(biāo)上，稍后會(huì)在文章結(jié)尾進(jìn)行說(shuō)明

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)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

put(K key, V value)內(nèi)部調(diào)用putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)葫哗，首先判斷table（最終存放結(jié)果的數(shù)據(jù)結(jié)構(gòu)）是否為空缔刹，如果是則調(diào)用resize()進(jìn)行初始化

resize()既是table的初始化方法，同時(shí)也是table的擴(kuò)容方法劣针，將在后面一小節(jié)會(huì)進(jìn)行講解

初始化完成后將table賦值給tab并將table的長(zhǎng)度賦值給n校镐，接著將長(zhǎng)度n - 1和前面計(jì)算出來(lái)的key的哈希值hash進(jìn)行與運(yùn)算計(jì)算出key應(yīng)該存放在table的哪個(gè)下標(biāo)上

這里和我們想象的不太一樣，按照我們的想法是直接將算好的哈希值hash和數(shù)組長(zhǎng)度n進(jìn)行取模運(yùn)算就可以得出key將落在哪個(gè)下標(biāo)上捺典，但是JDK中并沒(méi)有采用這種算法鸟廓，而是采用了一種更加高效的位運(yùn)算來(lái)完成，下面將詳細(xì)講解這種算法和限制

· JDK位運(yùn)算計(jì)算下標(biāo)位置

當(dāng)table初始化時(shí)長(zhǎng)度為16（詳解下面resize小節(jié)）轉(zhuǎn)化成二進(jìn)制00000000000000000000000000010000減1得00000000000000000000000000001111由于數(shù)組是從0開(kāi)始進(jìn)行計(jì)算此時(shí)二進(jìn)制表示的范圍正好是0 ~ 15襟己，這時(shí)再將上面key計(jì)算的hash進(jìn)行與運(yùn)算（兩者為1則為1引谜，否則為0）即可得出一個(gè)0 ~ 15范圍內(nèi)的數(shù)字，這個(gè)數(shù)字就是key將要存放的下標(biāo)位置擎浴。比如：

   hash:10000100011100010000011110000001
   n-1 :00000000000000000000000000001111
outcome:00000000000000000000000000000001

上面隨機(jī)寫的一個(gè)hash员咽，由于n-1的出的二進(jìn)制限制，hash相對(duì)于n-1中為0的位將全部被忽略贮预，只有當(dāng)n-1的位上是1時(shí)相對(duì)應(yīng)的hash位才有計(jì)算的意義贝室，例子中最終結(jié)果是00000000000000000000000000000001轉(zhuǎn)十進(jìn)制得1則該key將存放到table中下標(biāo)為1的位置上

· JDK位運(yùn)算計(jì)算下標(biāo)位置算法的限制

為了能使上述算法成立，n的值必須是2的N次冪仿吞，由于int類型為32位滑频，所以N的取值范圍為0 ~ 31，即2^0~31茫藏。在二進(jìn)制中表現(xiàn)則是在所有的位中最多只有一位是1其他的都必須為0误趴，因?yàn)榧僭O(shè)n為3時(shí)（不是2的N次冪），二進(jìn)制為00000000000000000000000000000011此時(shí)減1得到00000000000000000000000000000010再和hash進(jìn)行與運(yùn)算的時(shí)候只能得出0或者2的下標(biāo)务傲，永遠(yuǎn)不可能得出1的下標(biāo)凉当，顯然是有問(wèn)題的，如下

   hash:10000100011100010000011110000001
   n-1 :00000000000000000000000000000010
outcome:00000000000000000000000000000000

   hash:10000100011100010000011110000010
   n-1 :00000000000000000000000000000010
outcome:00000000000000000000000000000010

我們知道new HashMap(3)時(shí)是可以自定義初始化長(zhǎng)度的售葡，JDK為了保證n永遠(yuǎn)是2的N次冪看杭，當(dāng)我們傳入了不是2的N次冪時(shí)，JDK會(huì)在構(gòu)造函數(shù)中調(diào)用tableSizeFor(int cap)檢查并重置傳入的長(zhǎng)度挟伙，重置完成的長(zhǎng)度大于等于自定義初始化長(zhǎng)度并保證是2的N次冪

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

解釋下上面的算法楼雹，以長(zhǎng)度為3作為例子，二進(jìn)制為00000000000000000000000000000011此時(shí)減1得00000000000000000000000000000010尖阔，此時(shí)無(wú)符號(hào)向右移動(dòng)一位得00000000000000000000000000000001再和原來(lái)減1后得到的n進(jìn)行與運(yùn)算得00000000000000000000000000000011再無(wú)符號(hào)向右移動(dòng)兩位得00000000000000000000000000000000
再和最后的結(jié)果n進(jìn)行與運(yùn)算得00000000000000000000000000000011贮缅，重復(fù)上述動(dòng)作移動(dòng)四位再進(jìn)行與運(yùn)算，移動(dòng)八位再進(jìn)行與運(yùn)算介却，移動(dòng)16位再進(jìn)行與運(yùn)算谴供，最終得00000000000000000000000000000011，最后判斷是否大于允許的最大長(zhǎng)度齿坷，不大于則加1得00000000000000000000000000000100桂肌，轉(zhuǎn)為十進(jìn)制為4，計(jì)算過(guò)程如下

      n :00000000000000000000000000000011
  n - 1 :00000000000000000000000000000010
n >>> 1 :00000000000000000000000000000001
      n :00000000000000000000000000000011
n >>> 2 :00000000000000000000000000000000
      n :00000000000000000000000000000011
n >>> 4 :00000000000000000000000000000000
      n :00000000000000000000000000000011
n >>> 8 :00000000000000000000000000000000
      n :00000000000000000000000000000011
n >>> 16:00000000000000000000000000000000
      n :00000000000000000000000000000011
  n + 1 :00000000000000000000000000000100

這里在計(jì)算前有一個(gè)減1的操作永淌，到最后有一個(gè)加1的操作崎场，是為了使最后得出來(lái)的長(zhǎng)度能大于等于我們所自定義的長(zhǎng)度，如果不這樣操作的話不能保證計(jì)算后得出的長(zhǎng)度一定大于等于我們所自定義的長(zhǎng)度

回到putVal方法遂蛀，當(dāng)計(jì)算完得出key所要存放的下標(biāo)時(shí)谭跨，判斷該鏈表上是否為空，為空則直接new一個(gè)Node并放入數(shù)組相對(duì)應(yīng)的下標(biāo)中李滴，不為空則將當(dāng)前下標(biāo)的鏈表賦值給p然后判斷當(dāng)前鏈表頭的hash值和key是否相等螃宙，相等則執(zhí)行替換，不相等則繼續(xù)判斷p是否是TreeNode節(jié)點(diǎn)（紅黑樹(shù)數(shù)據(jù)結(jié)構(gòu)）悬嗓，HashMap中為否污呼，此時(shí)走到最后的else邏輯，循環(huán)遍歷鏈表p判斷是否有相同的key有則替換包竹，無(wú)則新增燕酷。當(dāng)else走完后，在方法最后會(huì)計(jì)算整個(gè)HashMap的元素總數(shù)size和閾值threshold（后面resize()那節(jié)將會(huì)講解如何計(jì)算出來(lái)的）進(jìn)行比較周瞎，如果大于threshold則會(huì)調(diào)用resize()進(jìn)行擴(kuò)容

注意Ｃ缢酢！声诸！在else邏輯里面循環(huán)遍歷鏈表p中binCount記錄著當(dāng)前鏈表循環(huán)到了第幾個(gè)酱讶，也表示當(dāng)前存在多少個(gè)元素，當(dāng)元素個(gè)數(shù)binCount大于等于TREEIFY_THRESHOLD（常量8） - 1時(shí)彼乌，即binCount大于等于7時(shí)泻肯，binCount從0開(kāi)始計(jì)算渊迁，當(dāng)為7時(shí)表示第8個(gè)元素，此時(shí)會(huì)將鏈表p轉(zhuǎn)換成為紅黑樹(shù)

resize方法

resize()方法除了對(duì)Hashmap進(jìn)行擴(kuò)容外還有對(duì)Hashmap進(jìn)行初始化

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) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

當(dāng)table為空時(shí)且new HashMap()時(shí)沒(méi)有指定初始化長(zhǎng)度灶挟，這時(shí)代碼22 ~ 24行獲取初始化的默認(rèn)值琉朽，默認(rèn)長(zhǎng)度newCap = DEFAULT_INITIAL_CAPACITY = 1 << 4 = 16，閾值為newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY) = 12稚铣，DEFAULT_LOAD_FACTOR的值是0.75f也就是會(huì)把初始化長(zhǎng)度的三分之一作為閾值箱叁，然后創(chuàng)建table并返回

當(dāng)添加的元素總個(gè)數(shù)超過(guò)閾值時(shí)則會(huì)調(diào)用resize()進(jìn)行擴(kuò)容，這時(shí)代碼11 ~ 13行對(duì)原來(lái)的長(zhǎng)度和閾值同時(shí)向左移動(dòng)一位（相當(dāng)于乘以2）惕医，相對(duì)第一次初始化的長(zhǎng)度16和閾值12擴(kuò)容后就長(zhǎng)度為32閾值為24耕漱，并用新的長(zhǎng)度創(chuàng)建新的table后，將原來(lái)的舊數(shù)據(jù)遷移到新的table上

這里同樣JDK并沒(méi)有使用我們想到的方法抬伺，即輪詢舊的table并讓每個(gè)key的hash和新的長(zhǎng)度n進(jìn)行重新計(jì)算螟够，得出在新table中的下標(biāo)并設(shè)值，只有當(dāng)舊table的鏈表個(gè)數(shù)只有1個(gè)時(shí)才是使用我們所想的方法沛简，即代碼35 ~ 36行齐鲤。如果鏈表的長(zhǎng)度超過(guò)1個(gè)時(shí)則走else代碼，接下來(lái)詳細(xì)對(duì)else中的代碼進(jìn)行講解

首先要明白一點(diǎn)＝烽埂８肌！同一個(gè)鏈表上的元素在舊的長(zhǎng)度上面相對(duì)應(yīng)的有效hash位的值是相同的捧灰，假設(shè)我們的初始化長(zhǎng)度為16淆九，擴(kuò)容后的長(zhǎng)度為32，其中一條鏈表上面有兩個(gè)元素毛俏，hash分別為00000100001010100100000000010011炭庙、00000100101010110000010000000011，兩個(gè)元素在同一條鏈表上煌寇，舊長(zhǎng)度為16化為二進(jìn)制并減1得00000000000000000000000000001111那么只有后四位會(huì)進(jìn)行計(jì)算焕蹄，也就是只有后四位為有效hash位，所以只有新元素的有效hash位也就是后四位為0011時(shí)才會(huì)獲得同一個(gè)下標(biāo)和上面兩個(gè)元素在同一個(gè)鏈表中阀溶。

明白后我們接著看腻脏，接下來(lái)的計(jì)算會(huì)有點(diǎn)神奇！Ｒ汀永品！當(dāng)長(zhǎng)度從16擴(kuò)展到32時(shí)，32的二進(jìn)制為00000000000000000000000000100000減1得00000000000000000000000000011111這時(shí)會(huì)發(fā)現(xiàn)長(zhǎng)度為16減1后的二進(jìn)制的后四位和32減1的后四位相同击纬，那么也就是說(shuō)決定舊元素在新table中鼎姐，需要增加多少才能算出在新table中的準(zhǔn)確下標(biāo)位置，這個(gè)由最左邊的1決定
比如上面的兩個(gè)hash，其中一個(gè)是00000100001010100100000000010011那么后四位決定了它在舊table中的下標(biāo)為3炕桨，那么新table中需要增加多少才能算出準(zhǔn)確下標(biāo)位置由hash從右往左數(shù)第5位決定饭尝，它上面是1，該位在二進(jìn)制中表示16谋作，所以該hash在新table中的準(zhǔn)確下標(biāo)是原本的位置3加上需要移動(dòng)的長(zhǎng)度16等于19芋肠。第二個(gè)hash的二進(jìn)制是00000100101010110000010000000011乎芳，從右往左數(shù)第5位是0遵蚜，所以移動(dòng)的長(zhǎng)度為0，故在新的table中下標(biāo)保持不變奈惑，還是原來(lái)的位置吭净，那如何才能知道從右往左數(shù)第5位是0還是1，只需要將舊table的長(zhǎng)度轉(zhuǎn)成二進(jìn)制再和hash進(jìn)行計(jì)算即可

ｋ鹊椤＜叛场！也就是說(shuō)在同一個(gè)鏈表中要么就是保持原來(lái)的位置不變原在，要么就是增加移動(dòng)舊table的長(zhǎng)度作為新table中的位置

此時(shí)再來(lái)看代碼就簡(jiǎn)單多了友扰，現(xiàn)在的邏輯就變成了同一條鏈表上的元素，要么保持原來(lái)的位置庶柿，要么移動(dòng)相對(duì)應(yīng)的長(zhǎng)度村怪。JDK中創(chuàng)建了兩個(gè)鏈表來(lái)保存保持不變的元素loHead和需要移動(dòng)相對(duì)應(yīng)的長(zhǎng)度的鏈表hiHead，接著用舊table長(zhǎng)度的二進(jìn)制便能計(jì)算出是否需要移動(dòng)浮庐，再添加到相對(duì)應(yīng)的鏈表中甚负，最后再存放到新table中

resize()要注意，當(dāng)結(jié)構(gòu)為紅黑樹(shù)時(shí)审残，元素個(gè)數(shù)小于等于6時(shí)會(huì)被轉(zhuǎn)化回鏈表梭域，由UNTREEIFY_THRESHOLD = 6常量定義，
除了resize()還有remove(Object key)也有可能將紅黑樹(shù)轉(zhuǎn)化回鏈表

remove方法

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

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;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        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) {
            if (p instanceof TreeNode)
                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)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;
            --size;
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

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;
    TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    if (pred == null)
        tab[index] = first = succ;
    else
        pred.next = succ;
    if (succ != null)
        succ.prev = pred;
    if (first == null)
        return;
    if (root.parent != null)
        root = root.root();
    if (root == null
        || (movable
            && (root.right == null
                || (rl = root.left) == null
                || rl.left == null))) {
        tab[index] = first.untreeify(map);  // too small
        return;
    }
    TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    if (pl != null && pr != null) {
        TreeNode<K,V> s = pr, sl;
        while ((sl = s.left) != null) // find successor
            s = sl;
        boolean c = s.red; s.red = p.red; p.red = c; // swap colors
        TreeNode<K,V> sr = s.right;
        TreeNode<K,V> pp = p.parent;
        if (s == pr) { // p was s's direct parent
            p.parent = s;
            s.right = p;
        }
        else {
            TreeNode<K,V> sp = s.parent;
            if ((p.parent = sp) != null) {
                if (s == sp.left)
                    sp.left = p;
                else
                    sp.right = p;
            }
            if ((s.right = pr) != null)
                pr.parent = s;
        }
        p.left = null;
        if ((p.right = sr) != null)
            sr.parent = p;
        if ((s.left = pl) != null)
            pl.parent = s;
        if ((s.parent = pp) == null)
            root = s;
        else if (p == pp.left)
            pp.left = s;
        else
            pp.right = s;
        if (sr != null)
            replacement = sr;
        else
            replacement = p;
    }
    else if (pl != null)
        replacement = pl;
    else if (pr != null)
        replacement = pr;
    else
        replacement = p;
    if (replacement != p) {
        TreeNode<K,V> pp = replacement.parent = p.parent;
        if (pp == null)
            root = replacement;
        else if (p == pp.left)
            pp.left = replacement;
        else
            pp.right = replacement;
        p.left = p.right = p.parent = null;
    }

    TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);

    if (replacement == p) {  // detach
        TreeNode<K,V> pp = p.parent;
        p.parent = null;
        if (pp != null) {
            if (p == pp.left)
                pp.left = null;
            else if (p == pp.right)
                pp.right = null;
        }
    }
    if (movable)
        moveRootToFront(tab, r);
}

remove(Object key)的話沒(méi)有什么好說(shuō)的搅轿，通過(guò)獲取要?jiǎng)h除的key的hash計(jì)算出在table中的那個(gè)下標(biāo)病涨，輪詢?cè)撓聵?biāo)上的鏈表比較并進(jìn)行移除并返回被刪除的key的值

需要注意的是，在remove(Object key)中當(dāng)數(shù)據(jù)結(jié)構(gòu)不是鏈表而是紅黑樹(shù)的時(shí)候璧坟，當(dāng)紅黑樹(shù)的元素個(gè)數(shù)小于等于6時(shí)既穆，也會(huì)把紅黑樹(shù)轉(zhuǎn)化回鏈表結(jié)構(gòu)，但在remove(Object key)中這個(gè)小于等于6的說(shuō)法也不是一定是絕對(duì)的沸柔，因?yàn)榕袛嗍欠駥⒓t黑樹(shù)轉(zhuǎn)化回鏈表的依據(jù)是紅黑樹(shù)的root節(jié)點(diǎn)的左子樹(shù)是否為空或者root節(jié)點(diǎn)的右子樹(shù)是否為空或者root節(jié)點(diǎn)的左子樹(shù)的左子樹(shù)是否為空循衰，這里不同于resize()有可能出現(xiàn)小于6但依然是紅黑樹(shù)，只能說(shuō)最理想最快會(huì)被轉(zhuǎn)化回鏈表的情況是root節(jié)點(diǎn)的左子樹(shù)的左子樹(shù)為空其他均不為空褐澎，這時(shí)刪除元素后的紅黑樹(shù)的個(gè)數(shù)等于6会钝，如下圖，代碼為67 ~ 71行

刪除元素后最理想最快被轉(zhuǎn)回鏈表的紅黑樹(shù)結(jié)構(gòu)

回顧

回到文章之前，我們還有一個(gè)問(wèn)題沒(méi)有回答迁酸，為什么要無(wú)符號(hào)右移16位之后再和原來(lái)的哈希值進(jìn)行異或運(yùn)算再返回計(jì)算后的值作為hash先鱼？
這里首先需要說(shuō)明hashCode是一個(gè)32位int類型，分為高16位（從左往右數(shù)16位）和低16位（從右往左數(shù)16位）奸鬓，無(wú)符號(hào)右移16位意味著刪除低16位后將高16位向右移動(dòng)焙畔，高16位變成了低16位，而原來(lái)的高16位用0填充串远，這是考慮到如果低16位一直重復(fù)宏多，而高16位不重復(fù)，那么在數(shù)據(jù)量少的情況下都是低16位在起到?jīng)Q定下標(biāo)的作用澡罚，所以為了防止這種情況的發(fā)生伸但，JDK將高16位的影響帶到低16位中進(jìn)行一個(gè)異或運(yùn)算，使得得出來(lái)的hash盡可能的離散

總結(jié)

至此留搔，HashMap的源碼解析結(jié)算更胖，紅黑樹(shù)部分并沒(méi)有講解，因?yàn)橐仓皇菙?shù)據(jù)結(jié)構(gòu)上面的存儲(chǔ)方式不同而已

傳送門

GitHub該系列教程項(xiàng)目地址隔显，同步更新：
https://github.com/ChenZhiB/tutorial