台中電動車-立刻預約試騎，購車享優惠

提供電動自行車.電動腳踏車.四輪代步車.三輪代步車，不限里程，永久保固，再享15期分期0利率。

曹工說JDK源碼（3）–ConcurrentHashMap，Hash算法優化、位運算揭秘

由 · 已發表 · 已更新

hashcode，有點講究

什麼是好的hashcode，一般來說，一個hashcode，一般用int來表示，32位。

下面兩個hashcode，大家覺得怎麼樣？

0111 1111 1111 1111 1111 1111 1111 1111  ------A
1111 1111 1111 1111 1111 1111 1111 1111  ------B

只有第32位（從右到左）不一樣，好像也沒有所謂的好壞吧？

那，我們再想想，hashcode一般怎麼使用呢？在hashmap中，由數組+鏈表+紅黑樹組成，其中，數組乃重中之重，假設數組長度為2的n次方，（hashmap的數組，強制要求長度為2的n次方），這裏假設為8.

大家又知道，hashcode 對 8 取模，效果等同於 hashcode & (8 – 1)。

那麼，前面的A 和 （8 – 1）相與的結果如何呢？

0111 1111 1111 1111 1111 1111 1111 1111  ------A
0000 0000 0000 0000 0000 0000 0000 0111  ------ 8 -1
    相與
0000 0000 0000 0000 0000 0000 0000 0111  ------ 7

結果為7，也就是，會放進array[7]。

大家再看B的計算過程：

1111 1111 1111 1111 1111 1111 1111 1111  ------B
0000 0000 0000 0000 0000 0000 0000 0111  ------ 8 -1
    相與
0000 0000 0000 0000 0000 0000 0000 0111  ------ 7

雖然B的第32位為1，但是，奈何和我們相與的隊友，7，是個垃圾。

前面的高位，全是0。

ok，你懂了嗎，數組長度太小了，才8，導致前面有29位都是0；你可能覺得一般容量不可能這麼小，那假設容量為2的16次方，容量為65536，這下不是很小了吧，但即使如此，前面的16位也是0.

所以，問題明白了嗎，我們計算出來的hashcode，低位相同，高位不同；但是，因為和我們進行與計算的隊友太過垃圾，導致我們出現了hash衝突。

ok，我們怎麼來解決這個問題呢？

我們能不能把高位也參与計算呢？自然，是可以的。

hashmap中如何優化

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

這裏，其實分了3個步驟：

  1. 計算hashcode，作為操作數1

    h = key.hashCode()

  2. 將第一步的hashcode，右移16位，作為操作數2

    h >>> 16

  3. 操作數1 和 操作數2 進行異或操作，得到最終的hashcode

還是拿前面的來算，

0111 1111 1111 1111 1111 1111 1111 1111  ------A
0000 0000 0000 0000 0111 1111 1111 1111   ----- A >>> 16
          異或（相同則為0，否則為1）
0111 1111 1111 1111 1000 0000 0000 0000    --- 2147450880

這裏算出來的結果是 2147450880，再去對 7 進行與運算：

0111 1111 1111 1111 1000 0000 0000 0000    --- 2147450880  
0000 0000 0000 0000 0000 0000 0000 0111  ------ 8 -1
          與運算
0000 0000 0000 0000 0000 0000 0000 0000  ------ 0

這裏的A，算出來，依然在array[0]。

再拿B來算一下：

1111 1111 1111 1111 1111 1111 1111 1111  ------ B
0000 0000 0000 0000 1111 1111 1111 1111   ----- B >>> 16
          異或（相同則為0，否則為1）
1111 1111 1111 1111 0000 0000 0000 0000    --- -65536
0000 0000 0000 0000 0000 0000 0000 0111  ------ 7   
         與運算
0000 0000 0000 0000 0000 0000 0000 0000  ------- 0

最終算出來為0，所以，應該放在array[0]。

恩？算出來兩個還是衝突了，我只能說，我挑的数字真的牛逼，是不是該去買彩票啊。。

總的來說，大家可以多試幾組數，下邊提供下源代碼：

public class BinaryTest {
    public static void main(String[] args) {
        int a = 0b00001111111111111111111111111011;
        int b = 0b10001101111111111111110111111011;

        int i = tabAt(32, a);
        System.out.println("index for a:" + i);

        i = tabAt(32, b);
        System.out.println("index for b:" + i);

    }

    static final int tabAt(int  arraySize, int hash) {

        int h = hash;
        int finalHashCode = h ^ (h >>> 16);
        int i = finalHashCode & (arraySize - 1);

        return i;
    }
}

雖然說，我測試了幾個数字，還是有些衝突，但是，你把高16位弄進來參与計算，總比你不弄進來計算要好吧。

大家也可以看看hashmap中，hash方法的註釋：

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */

裏面提到了2點：

So we apply a transform that spreads the impact of higher bits downward.

所以，我們進行了一個轉換，把高位的作用利用起來。

we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as

to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

我們僅僅異或了從高位移動下來的二進制位，用最經濟的方式，削減系統性能損失，同樣，因為數組大小的限制，導致高位在索引計算中一直用不到，我們通過這種轉換將其利用起來。

ConcurrentHashMap如何優化

在concurrentHashMap中，其主要是：

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode());

這裏主要是使用spread方法來計算hash值：

    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
    }

大家如果要仔細觀察每一步的二進制，可以使用下面的demo：


    static final int spread(int h) {
        	// 1
            String s = Integer.toBinaryString(h);
            System.out.println("h:" + s);
    
        	// 2
            String lower16Bits = Integer.toBinaryString(h >>> 16);
            System.out.println("lower16Bits:" + lower16Bits);
    
        	// 3
            int temp = h ^ (h >>> 16);
            System.out.println("h ^ (h >>> 16):" + Integer.toBinaryString(temp));
    
        	// 4
            int result = (temp) & HASH_BITS;
            System.out.println("final:" + Integer.toBinaryString(result));
    
    
            return result;
        }

這裏和HashMap相比，多了點東西，也就是多出來了：

& HASH_BITS;

這個有什麼用處呢？

因為(h ^ (h >>> 16))計算出來的hashcode，可能是負數。這裏，和 HASH_BITS進行了相與：

static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

1111 1111 1111 1111 1111 1111 1111 1111   假設計算出來的hashcode為負數，因為第32位為1
0111 1111 1111 1111 1111 1111 1111 1111       0x7fffffff
    進行相與
0111 ..................................

​ 這裏，第32位，因為0x7fffffff的第32位，總為0，所以相與后的結果，第32位也總為0 ，所以，這樣的話，hashcode就總是正數了，不會是負數。

concurrentHashMap中，node的hashcode，為啥不能是負數

當hashcode為正數時，表示該哈希桶為正常的鏈表結構。

當hashcode為負數時，有幾種情況：

ForwardingNode

此時，其hash值為：

    static final int MOVED     = -1; // hash for forwarding nodes

當節點為ForwardingNode類型時（表示哈希表在擴容進行中，該哈希桶已經被遷移到了新的臨時hash表，此時，要get的話，需要去臨時hash表查找；要put的話，是不行的，會幫助擴容）

TreeBin

    static final int TREEBIN   = -2; // hash for roots of trees

表示，該哈希桶，已經轉了紅黑樹。

擴容時的位運算

    /**
     * Returns the stamp bits for resizing a table of size n.
     * Must be negative when shifted left by RESIZE_STAMP_SHIFT.
     */
    static final int resizeStamp(int n) {
        return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
    }

這裏，假設，n為4，即，hashmap中數組容量為4.

  • 下面這句，求4的二進製表示中，前面有多少個0.

    Integer.numberOfLeadingZeros(n)

    表示為32位后，如下

    0000 0000 0000 0000, 0000 0000 0000 0100

    所以，前面有29個0，即，這裏的結果為29.

  • (1 << (RESIZE_STAMP_BITS – 1)

    這一句呢，其中RESIZE_STAMP_BITS 是個常量，為16. 相當於，把1 向左移動15位。

    二進製為：

    1000 0000 0000 0000   -- 1 << 15

最終結果：

0000 0000 0000 0000 0000 0000 0001 1101   -- 29
0000 0000 0000 0000 1000 0000 0000 0000   -- 1 << 15
進行或運算

0000 0000 0000 0000 1000 0000 0001 1101   --  相當於把29的第一位，變成了1，其他都沒變。

所以，最終結果是，

這個數，換算為10進制，為32972，是個正數。

這個數，有啥用呢？

在addCount函數中，當整個哈希表的鍵值對數量，超過sizeCtl時（一般為0.75 * 數組長度），就會觸發擴容。

java.util.concurrent.ConcurrentHashMap#addCount
    
int sc =  sizeCtl;
boolean bSumExteedSizeControl = newBaseCount >= (long) sc;
// 1
if (bContinue) {
    int rs = resizeStamp(n);
    // 2
    if (sc < 0) {
        if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
            transferIndex <= 0)
            break;
        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
            transfer(tab, nt);
    }
    // 3
    else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                   (rs << RESIZE_STAMP_SHIFT) + 2))
        transfer(tab, null);
    newBaseCount = sumCount();
} else {
    break;
}

  • 1處，如果擴容條件滿足

  • 2處，如果sc小於0，這個sc是啥，就是前面說的sizeCtl，此時應該是等於：0.75 * 數組長度，不可能為負數

  • 3處，將sc（此時為正數），cas修改為：

    (rs << RESIZE_STAMP_SHIFT) + 2)

    這個數有點意思了，rs就是前面我們的resizeStamp得到的結果。

    按照前面的demo，我們拿到的結果為：

    0000 0000 0000 0000 1000 0000 0001 1101   --  相當於把29的第一位，變成了1，其他都沒變。

    因為

    private static int RESIZE_STAMP_BITS = 16;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;

    所以，RESIZE_STAMP_SHIFT 為16.

    0000 0000 0000 0000 1000 0000 0001 1101   --  相當於把29的第一位，變成了1，其他都沒變。
1000 0000 0001 1101 0000 0000 0000 0000 ---   左移16位，即   rs << RESIZE_STAMP_SHIFT
1000 0000 0001 1101 0000 0000 0000 0010    -- (rs << RESIZE_STAMP_SHIFT) + 2)

    最終，這個數，第一位是 1，說明了，這個數，肯定是負數。

    大家如果看過其他人寫的資料，也就知道，當sizeCtl為負數時，表示正在擴容。

    所以，這裏

    if (U.compareAndSwapInt(this, SIZECTL, sc,
                            (rs << RESIZE_STAMP_SHIFT) + 2))

    這句話就是，如果當前線程成功地，利用cas，將sizeCtl從正數，變成負數，就可以進行擴容。

    擴容時，其他線程怎麼執行

    // 1
if (bContinue) {
    int rs = resizeStamp(n);
    // 2
    if (sc < 0) {
        // 2.1
        if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
            transferIndex <= 0)
            break;
        // 2.2
        if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
            transfer(tab, nt);
    }
    // 3
    else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                   (rs << RESIZE_STAMP_SHIFT) + 2))
        transfer(tab, null);
    newBaseCount = sumCount();
} else {
    break;
}

    此時，因為上面的線程觸發了擴容，sc已經變成了負數了，此時，新的線程進來，會判斷2處。

    2處是滿足的，會進入2.1處判斷，這裏的部分條件看不懂，大概是：擴容已經結束，就不再執行，直接break

    否則，進入2.2處，輔助擴容，同時，把sc變成sc + 1，增加擴容線程數。

總結

時間倉促，如有問題，歡迎指出。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※別再煩惱如何寫文案,掌握八大原則!

※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!

※超省錢租車方案

※教你寫出一流的銷售文案?

※網頁設計最專業,超強功能平台可客製化

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

標籤：

您可能也會喜歡…