炸毛的猫
0%

JDK1.7.ConcurrentHashMap中Segment定位

发表于 更新于 分类于

介绍了JDK1.7中ConcurrentHashMap中Segment元素位置与地址的定位过程。

代码片段

先贴一下 JDK1.7 ConcurrentHashMap 构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {
    // 参数校验
    if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    // 校验并发级别大小，大于 1<<16，重置为 65536
    if (concurrencyLevel > MAX_SEGMENTS)
        concurrencyLevel = MAX_SEGMENTS;
    // Find power-of-two sizes best matching arguments
    // 2的多少次方
    int sshift = 0;
    int ssize = 1;
    // 这个循环可以找到 concurrencyLevel 之上最近的 2的次方值
    while (ssize < concurrencyLevel) {
        ++sshift;
        ssize <<= 1;
    }
    // 记录段偏移量
    this.segmentShift = 32 - sshift;
    // 记录段掩码
    this.segmentMask = ssize - 1;
    // 设置容量
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    // c = 容量 / ssize ，默认 16 / 16 = 1，这里是计算每个 Segment 中的类似于 HashMap 的容量
    int c = initialCapacity / ssize;
    if (c * ssize < initialCapacity)
        ++c;
    int cap = MIN_SEGMENT_TABLE_CAPACITY;
    //Segment 中的类似于 HashMap 的容量至少是2或者2的倍数
    while (cap < c)
        cap <<= 1;
    // create segments and segments[0]
    // 创建 Segment 数组，设置 segments[0]
    Segment<K,V> s0 = new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                         (HashEntry<K,V>[])new HashEntry[cap]);
    Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
    UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
    this.segments = ss;
}

SegmentShift作用

Shift指代偏移量，在JDK1.7中，元素先是先找到Segment中，插入Segment内部类HashMap的数组之中。
在初始化的计算中
this.segmentShift = 32 - sshift;
而 sshift 指代了当前l(concurrencylevel)的开方
当 sshift 默认情况为 4
4 与 32 对应的二进制为：
32 16 8 4 2 1
**1 0 0 0 0 0 **
0 0 0 1 0 0
this.segmentShift = 32 - sshift = 0 1 1 0 1 1;

1
2
3
4
5
6
7
8
/**
 * Get the segment for the given hash
 */
@SuppressWarnings("unchecked")
private Segment<K,V> segmentForHash(int h) {
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    return (Segment<K,V>) UNSAFE.getObjectVolatile(segments, u);
}

从这里的函数我们就可以知道segmentShift的意义了，将hash映射至segment数组某一位置！
首先 hash类型为int，为32位二进制数。
h >>> segmentShift 其实是将hash缩小到与当前 concurrencyLevel - 1 同样的二进制位数，也就是取了Hash值的前** Log2( concurrencyLevel) 位数**，由此映射到segment数组之中。

SegmentMask作用

紧接着我们有一部 & segmentMask 操作，而 segmentMask = ssize - 1，此时 ssize = concurrencyLevel，所以segment在普通情况下并没有发生作用，因为它的值为全1，& 操作并不会该改变值。
但如果concurrencyLevel = 0，这时segmentShift = 32，segmentMask = 0，
而 h >>> segmentShift = h，这个时候 & segmentMask 的结果就为0，并没有超出此时segment数组长度。

按地址取分段

接下来的操作即** ( j << SHIFT ) + SBASE**，我们可以先看一下下方的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Unsafe mechanics
private static final sun.misc.Unsafe UNSAFE;
private static final long SBASE;
private static final int SSHIFT;
private static final long TBASE;
private static final int TSHIFT;


static {
    int ss, ts;
    try {
        UNSAFE = sun.misc.Unsafe.getUnsafe();
        Class tc = HashEntry[].class;
        Class sc = Segment[].class;
        TBASE = UNSAFE.arrayBaseOffset(tc);
        //返回数组中第一个元素的偏移地址
        SBASE = UNSAFE.arrayBaseOffset(sc);
        ts = UNSAFE.arrayIndexScale(tc);
        //返回数组中一个元素占用的大小
        ss = UNSAFE.arrayIndexScale(sc);
    } catch (Exception e) {
        throw new Error(e);
    }
    if ((ss & (ss-1)) != 0 || (ts & (ts-1)) != 0)
        throw new Error("data type scale not a power of two");
    // 数组中一个元素占用大小 从左至右有多少个0
    SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
    TSHIFT = 31 - Integer.numberOfLeadingZeros(ts);
}

由此我们猜测，SBASE代表了数组第一个元素的偏移地址，那么 j >> SSHIFT 显然就是代表了当前第j个元素的偏移量。
j >> SSHIFT 是如何计算的呢？
当我们点开numberOfLeadingZeros方法，这个方法返回了传入数从高位到低位有多少个0
以及附带的公式说明：
floor(log2(x)) = 31 - numberOfLeadingZeros(x)
ceil(log2(x)) = 32 - numberOfLeadingZeros(x - 1)
所以SSHIFT即为log2(一个元素的大小)，1 >> SSHIFT 即可以得到每个元素的大小，J >> SSHIFT 即第j个元素的偏移量，再加上SBASE，即可对应到数组中每个元素的位置。

吐槽一下，虽然说位运算更快。。。可是作为读者去看代码。。。。一时半会我是真的绕不过弯。。

补充

举例对公式进行说明：
假设 x = 4，则 numberOfLeadingZeros(4) = 29，那么 31 - 29 即为 2 ，也就是log2(4) 的值。
其实道理也很简单，当 x = 4 时，即 2^n，n = 2，而它的二进制形式为 100，为n+1位2进制数，那么
32 - numberOfLeadingZeros(x) = n + 1 –> 31 - numberOfLeadingZeros(x) = n.
但是如果x不为2^n，则会产生向下取整。

参考：
https://stackoverflow.com/questions/16409674/what-does-segmentmask-mean-in-java-concurrenthashmap
https://javaguide.cn/java/collection/concurrent-hash-map-source-code.html#_3-put