java - ConcurrentHashMap resizeStamp 方法如何工作？

Question

在ConcurrentHashMap的源码中，有一个方法叫做resizeStamp，代码为:

static final int resizeStamp(int n) {
    return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}

这段代码是如何工作的？

Answer 1

Short Answer: take sc as the result of (resizeStamp(n) << RESIZE_STAMP_SHIFT), the higher 16 bit of sc tells the information that there are at least one thread doing resizing operation on capcity n， the lower 16 bit tells the information that how many theards are doing this resizing concurrently.

说明:

首先，查看 resizeStamp(n) 的文档

/**
 * 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));
}

所以这个函数显然做了两件事

1. 将 n 的前导零数计算为 tmpReuslt
2. 取tmpResult的第16位为 1(注意:RESIZE_STAMP_BITS 是一个等于 16 的常数)

因此 resizeStamp 返回一个 32 位 int 值，其格式为 0000 0000 0000 0000 1xxx xxx xxxx xxxx

正如文档所说，返回结果“左移RESIZE_STAMP_SHIFT时必须为负”。

显然，当第16位设置为1时，左移RESIZE_STAMP_SHIFT后，reuslt的最高位将为1，从而使其成为负数。

那么，第二个问题来了，为什么要这样做，查看addCount(long x, int check) ConcurrentHashMap 中的函数

 // some code here
 if (check >= 0) {
        Node<K,V>[] tab, nt; int n, sc;
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            int rs = resizeStamp(n);
            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);
            }
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                transfer(tab, null);
            s = sumCount();
        }
    }

resizeStamp用于给ConcurrentHashMap中的sizeCtl赋值，通过操作(rs << RESIZE_STAMP_SHIFT) + 2 。

resizeStamp 函数确保 sizeCtl如果

则得到负值

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

执行成功。

• 以及sizeCtl的高16位可以说出信息:哪个尺码n ，调整大小操作正在进行