如何計算，一對key/value應該放在哪一個哈希桶

你們都知道，hashmap底層是數組+鏈表（不討論紅黑樹的狀況），其中，這個數組，咱們通常叫作哈希桶，你們若是去看jdk的源碼，會發現裏面有一些變量，叫作bin，這個bin，就是桶的意思，結合語境，就是哈希桶。java

這裏舉個例子，假設一個hashmap的數組長度爲4（0000 0100），那麼該hashmap就有4個哈希桶，分別爲bucket[0]、bucket[1]、bucket[2]、bucket[3]。node

如今有兩個node，hashcode分別是1（0000 0001），5（0000 0101）. 咱們固然知道，這兩個node，都應該放入第一個桶，畢竟1 mod 4，5 mod 4的結果，都是1。算法

可是，在代碼裏，可不是用取模的方法來計算的，而是使用下面的方式：數組

int entryNodeIndex = (tableLength - 1) & hash;

應該說，在tableLength的值，爲2的n次冪的時候，二者是等價的，可是由於位運算的效率更高，所以，代碼通常都使用位運算，替代取模運算。3d

下面咱們看看具體怎麼計算：指針

此處，tableLength即爲哈希表的長度，此處爲4. 4 - 1爲3，3的二進制表示爲：code

0000 0011blog

那麼，和咱們的1（0000 0001）相與：get

0000 0001 -------- 1
0000 0011 -------- 3（tableLength - 1）
    相與（同爲1，則爲1；不然爲0）
0000 0001 -------- 1

結果爲1，因此，應該放在第1個哈希桶，即數組下標爲1的node。源碼

接下來，看看5這個hashcode的節點要放在什麼位置，是怎麼計算：

0000 0101 -------- 5
0000 0011 -------- 3（tableLength - 1）
    相與（同爲1，則爲1；不然爲0）後結果：
0000 0001 -------- 1

擴容時，是怎麼對一個hash桶進行transfer的

此處，具體的整個transfer的細節，咱們本講不會涉及太多，不過，大致的邏輯，咱們能夠來想想。

之前面爲例，哈希表一共4個桶，其中bucket[1]裏面，存放了兩個元素，假設是a、b，其hashcode分別是1，5.

如今，假設咱們要擴容，通常來講，擴容的時候，都是新建一個bucket數組，其容量爲舊錶的一倍，這裏舊錶爲4，那新表就是8.

那，新表創建起來了，舊錶裏的元素，就得搬到新表裏面去，等全部元素都搬到新表了，就會把新表和舊錶的指針交換。以下：

java.util.concurrent.ConcurrentHashMap#transfer

    private transient volatile Node<K,V>[] nextTable;

	transient volatile Node<K,V>[] table;

if (finishing) {
    // 1
    nextTable = null;
    // 2
    table = nextTab;
    // 3
    sizeCtl = (tabLength << 1) - (tabLength >>> 1);
    return;
}

• 1處，將field：nextTable（也就是新表）設爲null，擴容完了，這個field就會設爲null

• 2處，將局部變量nextTab，賦值給table，這個局部變量nextTab裏，就是當前已經擴容完畢的新表

• 3處，修改表的sizeCtl爲：假設此處tabLength爲4，tabLength << 1 左移1位，就是8；tabLength >>> 1，右移一位，就是2，。8 - 2 = 6，正好就等於 8（新表容量） * 0.75。

  因此，這裏的sizeCtl就是，新表容量 * 負載因子，超過這個容量，基本就會觸發擴容。

ok，接着說，咱們要怎麼從舊錶往新表搬呢？ 那之前面的bucket[1]舉例，遍歷這個鏈表，計算各個node，應該放到新表的什麼位置，不就完了嗎？是的，理論上這麼寫就完事了。

可是，咱們會怎麼寫呢？

用hashcode對新bucket數組的長度取餘嗎？

jdk對效率的追求那麼高，確定不會這麼寫的，咱們看看，它怎麼寫的：

java.util.concurrent.ConcurrentHashMap#transfer

// 1
for (Node<K,V> p = entryNode; p != null; p = p.next) {
    // 2
    int ph = p.hash;
    K pk = p.key;
    V pv = p.val;
    
	// 3
    if ((ph & tabLength) == 0){
        lowEntryNode = new Node<K,V>(ph, pk, pv, lowEntryNode);
    }
    else{
        highEntryNode = new Node<K,V>(ph, pk, pv, highEntryNode);
    }
}

• 1處，即遍歷舊的哈希表的某個哈希桶，假設就是遍歷前面的bucket[1]，裏面有a/b兩個元素，hashcode分別爲1，5那個。

  

• 2處，獲取該節點的hashcode，此處分別爲1，5

• 3處，若是hashcode 和 舊錶長度相與，結果爲0，則，將該節點使用頭插法，插入新表的低位；若是結果不爲0，則放入高位。

  ok，什麼是高位，什麼是低位。擴容後，新的bucket數組，長度爲8，那麼，前面bucket[1]中的兩個元素，將分別放入bucket[1]和bucket[5].

  

  ok，這裏的bucket[1]就是低位，bucket[5]爲高位。

首先，你們要知道，hashmap中，容量老是2的n次方，請緊緊記住這句話。

爲何要這麼作？你想一想，這樣是否是擴容很方便？

之前，hashcode 爲1，5的，都在bucket[1]；而如今，擴容爲8後，hashcode爲1的，仍是在newbucket[1]，hashcode爲5的，則在newbucket[5]；這樣的話，是否是有一半的元素，根本不用動？

這就是我以爲的，最大的好處；另外呢，運算也比較方便，均可以使用位運算代替，效率更高。

好的，那咱們如今問題來了，下面這句的原理是什麼？

if ((ph & tabLength) == 0){
        lowEntryNode = new Node<K,V>(ph, pk, pv, lowEntryNode);
    } else{
        highEntryNode = new Node<K,V>(ph, pk, pv, highEntryNode);
    }

爲啥，hashcode & 舊哈希表的容量， 結果爲0的，擴容後，就會在低位，也就是維持位置不變呢？而結果不爲0的，擴容後，位置在高位呢？

背後的位運算原理（大白話）

代碼裏用的以下判斷，知足這個條件，去低位；不然，去高位。

if ((ph & tabLength) == 0)

仍是用前面的例子，假設當前元素爲a，hashcode爲1，和哈希桶大小4，去進行與運算。

0000 0001  ---- 1
0000 0100  ---- 舊哈希表容量4
&運算（同爲1則爲1，不然爲0）
結果：
0000 0000  ---- 結果爲0

ok，這裏算出來，結果爲0；什麼狀況下，結果會爲0呢？

那咱們如今開始倒推，什麼樣的數，和 0000 0100 相與，結果會爲0？

???? ????  ---- 
0000 0100  ---- 舊哈希表容量
&運算（同爲1則爲1，不然爲0）
結果：
0000 0000  ---- 結果爲0

由於與運算的規則是，同爲1，則爲1；不然都爲0。那麼，咱們這個例子裏，舊哈希表容量爲 0000 0100，假設表示爲2的n次方，此處n爲2，咱們僅有第三位（第n+1）爲1，那若是對方這一位爲0，那結果中的這一位，就會爲0，那麼，整個數，就爲0.

因此，咱們的結論是：假設哈希表容量，爲2的n次方，表示爲二進制後，第n+1位爲1；那麼，只要咱們節點的hashcode，在第n+1位上爲0，則最終結果是0.

反之，若是咱們節點的hashcode，在第n+1位爲1，則最終結果不會是0.

好比，hashcode爲5的時候，會是什麼樣子？

0000 0101  ---- 5
0000 0100  ---- 舊哈希表容量
&運算（同爲1則爲1，不然爲0）
結果：
0000 0100  ---- 結果爲4

此時，5這個hashcode，在第n+1位上爲1，因此結果不爲0。

至此，咱們離答案好像還很遠。ok，不慌，繼續。

假設如今擴容了，新bucket數組，長度爲8.

a元素，hashcode依然是1，a元素應該放到新bucket數組的哪一個bucket裏呢？

咱們用前面說的這個算法來計算：

int entryNodeIndex = (tableLength - 1) & hash;

0000 0001  ---- 1
0000 0111  ---- 8 - 1 = 7
&運算（同爲1則爲1，不然爲0）
結果：
0000 0001  ---- 結果爲1

結果沒錯，確實應該放到新bucket[1]，但怎麼推論出來呢？

// 1
	if ((ph & tabLength) == 0){
        // 2
        lowEntryNode = new Node<K,V>(ph, pk, pv, lowEntryNode);
    }

也就是說，假設一個數，知足1處的條件：(ph & tabLength) == 0，那怎麼推論出2呢，即應該在低位呢？

ok，條件1，前面分析了，能夠得出：

這個數，第n+1位爲0.

接下來，看看數組長度 - 1這個數。

好了，兩個數都有了，

???????0???????   -- 1 節點的hashcode，第n + 1位爲0
000000010000000   -- 2 老數組    
000000100000000   -- 3 新數組的長度，等於老數組長度 * 2
000000011111111   -- 4 新數組的長度 - 1
    
    運算：1和4相與

你們注意看紅字部分，還有框出來的那一列，這一列爲0，致使，最終結果，確定是比2那一行的數字小，2這行，不就是老數組的長度嗎，那你比老數組小；你比這一行小，在新數組裏，就只能在低位了。

反之，若是節點的hashcode，這一位爲1，那麼，最終結果，至少是大於等於2這一行的數字，因此，會放在高位。

參考資料

https://www.jianshu.com/p/2829fe36a8dd