java高並發之ConcurrentSkipListMap的那些事
注意：本文內容基於JDK11，不同版本會有差異
ConcurrentSkipListMap的結構
ConcurrentSkipListMap是以鏈表（自然排序）的形式進行數據存儲的。即在類中通過定義Node內部類來存儲單個節點的數據，通過Node中的next屬性，來記錄鏈表的下一個節點。同時會對Node中記錄的數據創建多級索引。結構總體如圖所示：
源碼解析
本文以put方法來對ConcurrentSkipListMap進行解析。
ConcurrentSkipListMap會在put方法里調用doPut方法。所以doPut()才是最終的實現
以下動圖為doPut方法的動態演示：
對於doPut方法的理解，可以通過調用ConcurrentSkipListMap的put方法。斷點調試，配合說明進行理解加深
關鍵程式碼說明：
/**
*
* @param key
* @param value
* @param onlyIfAbsent 如果已經存在，是否不進行插入（false就是進行插入，true就是不進行插入）
* @return
*/
private V doPut(K key, V value, boolean onlyIfAbsent){
if(key == null){
throw new NullPointerException();
}
//比較器
Comparator<? super K> cmp = comparator;
for(;;){
//頭索引
Index<K,V> h;
Node<K,V> b;
//禁止重排序
VarHandle.acquireFence();
//級別
int levels = 0;
/**
* 在第一次進行put方法時，會對head進行一個初始化操作。head是ConcurrentSkipListMap類的入口。
* 因為是鏈表結構，所以所有的操作都需要從head開始
* 這裡定義了一個null的Node節點，並且把這個Node賦值給Index（Index可以通過查看源碼的內部類），即當前索引所對應的節點就是該Node節點
* 這裡定義的Node不存儲數據，僅僅是作為整個鏈表的開始，可以配合結構圖進行理解
* compareAndSet 原子操作，保證高並發下的原子性。
*/
if( (h = head) == null){
//第一次初始化操作時會進入到這個if里
Node<K,V> base = new Node<K,V>(null, null, null);
h = new Index<K,V>(base, null, null);
b = HEAD.compareAndSet(this, null, h) ? base : null;
}
else{
/**
* 這裡包含了兩個循環
* while循環是對索引的橫向查找，一直找到right為空或者需要插入的key小於已存在的key的索引的位置
* for循環則是進行縱向查找，即查找到多層索引中的最底層索引
* cpr()方法是對兩個key的自然排序比較。本質上使用的是compareTo方法進行比較
*/
for (Index<K,V> q = h, r, d;;){
//通過while循環查找合適的索引位置橫行查找
while((r = q.right) != null){
Node<K,V> p;
K k;
if((p = r.node) == null || (k = p.key) == null || p.val == null){
RIGHT.compareAndSet();
}
else if(cpr(cmp, key, k) > 0){
q = r;
}
else{
break;
}
}
if(( d = q.down) != null){
++levels;
q = d;
}
else{
b = q.node;
break;
}
}
}
if(b != null){
Node<K,V> z = null;
/**
* 這裡通過for循環來查找插入點，即key的值需要大於插入點之前Node的key的值且小於插入點之後Node的key的值
*/
for (;;){
Node<K,V> n, p;
K k;
V v;
int c;
if( (n = b.next) == null){
if(b.key == null){
cpr(cmp, key, key);
}
c = -1;
}
else if((k = n.key) == null){
break;
}
else if((v = n.val) == null){
c = 1;
}
else if((c = cpr(cmp, key, k)) > 0){
//如果key > k
//那麼將n對應的node賦值給b。也就是重置b，將下一個Node的對象賦值到當前的b上
//同時將1賦值給c，然後進入下一次循環
b = n;
}
else {
c = 1;
}
//具體的插入操作就是在這實現的
if(c < 0 && NEXT.compareAndSet(b, n, p = new Node<K,V>(key, value, n))){
z = p;
//跳出本次循環
break;
}
}
if(z != null){
//源碼中使用ThreadLocalRandom.nextSecondarySeed()方法。
// 但是我們無法使用，所以用這個臨時替代。保證不報錯
int lr = ThreadLocalRandom.current().nextInt();
//1/4的概率添加索引
if((lr & 0x3) == 0 ){
int hr = ThreadLocalRandom.current().nextInt();
long rnd = hr << 32 | lr & 0xffffffffL;
//添加之前級別需要下降
int skips = levels;
Index<K,V> x = null;
//for循環表示，當前節點如果需要生成索引，那麼需要根據索引的層級來判斷生產多少層的索引
for(;;){
x = new Index<K,V>(z, x,null);
if (rnd >= 0L || --skips < 0){
break;
}
else{
rnd <<= 1;
}
}
//addIndices是具體索引生成的方法
//該方法返回boolean類型的數據，如果索引生成成功，那麼返回true，如果索引插入失敗，那麼返回false。
//這個if判斷是代表如果當前索引生成成功，那麼在當前索引的基礎上再生成上一級索引（對索引再生成一層索引）。
if(addIndices(h, skips, x, cmp) && skips < 0 && head == h){
Index<K,V> hx = new Index<K,V>(z, x, null);
//生成頭索引
Index<K,V> nh = new Index<K,V>(h.node, h, hx);
HEAD.compareAndSet(this, h, nh);
}
if (z.val == null){
}
}
//元素技術進行+1操作
addCount(1L);
return null;
}
}
}
}
