java.util.concurrent.ConcurrentHashMap整体为Segment数组,concurrentLevel为初始化参数,2^(sshift-1)^ < concurrentLevel <= 2^sshift^,Segment数组的大小ssize = 2^sshift^,

1
2
3
4
5
6
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}

ssize * (c - 1) < initialCapacity <= ssize * c,每个数组元素Segment的容量cap与c的大小关系,和ssize与concurrentLevel的大小关系一致,

1
2
3
4
5
6
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;

初始化时,使用UNsafe.putOrderedObject将新建Segment存入数组的0下标处,

1
2
3
4
5
6
7
8
9
10
Class sc = Segment[].class;
SBASE = UNSAFE.arrayBaseOffset(sc);
ss = UNSAFE.arrayIndexScale(sc);
SSHIFT = 31 - Integer.numberOfLeadingZeros(ss);
// create segments and 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]

使用put方法添加新的键值对时,仍然先计算key的哈希值,hash方法与HashMap中的hash方法类似,添加了再哈希步骤,其目的是为了减少哈希冲突,使元素能够均匀的分布在不同的Segment上,从而提高容器的存取效率,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private int hash(Object k) {
int h = hashSeed;
if ((0 != h) && (k instanceof String)) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// Spread bits to regularize both segment and index locations,
// using variant of single-word Wang/Jenkins hash.
h += (h << 15) ^ 0xffffcd7d;
h ^= (h >>> 10);
h += (h << 3);
h ^= (h >>> 6);
h += (h << 2) + (h << 14);
return h ^ (h >>> 16);
}

接着根据哈希值确定数组下标,这里的segmentShiftsegmentMask是初始化时根据sshiftssize确定的,

1
2
3
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
int j = (hash >>> segmentShift) & segmentMask;

反复确认j下标处的Segment是否为空,为空则依照0下标处的Segment新建Segment,使用UNSAFE.compareAndSwapObject更新null为新建Segment,

1
2
3
4
5
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}

接下来的操作之前会尝试对该Segment加锁,Segment整体为HashEntry数组,每个数组元素为HashEntry链表,继续根据哈希值确定数组下标,遍历index下标处的HashEntry链表,

1
2
3
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);

与HashMap中的比较逻辑一致,确定key是否存在,

1
2
3
if ((k = e.key) == key || (e.hash == hash && key.equals(k))) {
//...
}

如果已存在,更新其对应的value;如果未存在,根据键值对新建HashEntry对象,使用UNsafe.putOrderedObject将新建HashEntry存入数组的index下标处。使用get方法获取键对应的值时,不需要对当前Segment加锁,类似地先确定Segment数组下标,再确定HashEntry数组下标,遍历链表,比较确定key是否存在,如果存在返回对应的value;不存在返回null

文章中表述不清的地方可以进一步参考聊聊并发(四)——深入分析ConcurrentHashMap,对于UNsafe类中的方法,可以参考Java中Unsafe类详解