Java多线程（四）之ConcurrentSkipListMap深入分析 - JAVA

bound = n;
}
//如果一个链表中right没能找到key对应的value，则调整到其down的引用处继续查找
if ((d = q.down) != null) {
q = d;
r = d.right;
} else
break;
}
// 如果通过上面的遍历方式，还没能找到key对应的value，再通过Node.next的方式进行查找
for (n = q.node.next; n != null; n = n.next) {
if ((k = n.key) != null) {
if ((c = key.compareTo(k)) == 0) {
Object v = n.value;
return (v != null) (V)v : getUsingFindNode(key);
} else if (c < 0)
break;
}
}
return null;
}

------------------------------------------------
ConcurrentSkipListMap的删除

通过SkipList的方式进行删除操作：（下图以“删除23”进行说明：）

红色虚线，表示查找的路径，蓝色向右箭头表示right引用；黑色向下箭头表示down引用；

[java]
//remove操作，通过doRemove实现，把所有level中出现关键字key的地方都delete掉
public V remove(Object key) {
return doRemove(key, null);
}
final V doRemove(Object okey, Object value) {
Comparable< super K> key = comparable(okey);
for (;;) {
Node b = findPredecessor(key);//得到key的前驱（就是比key小的最大节点）
Node n = b.next;//前驱节点的next引用
for (;;) {//遍历
if (n == null)//如果next引用为空，直接返回
return null;
Node f = n.next;
if (n != b.next) // 如果两次获得的b.next不是相同的Node，就跳转到第一层循环重新获得b和n
break;
Object v = n.value;
if (v == null) { // 当n被其他线程delete的时候，其value==null，此时做辅助处理，并重新获取b和n
n.helpDelete(b, f);
break;
}
if (v == n || b.value == null) // 当其前驱被delet的时候直接跳出，重新获取b和n
break;
int c = key.compareTo(n.key);
if (c < 0)
return null;
if (c > 0) {//当key较大时就继续遍历
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v))
return null;
if (!n.casValue(v, null))
break;
if (!n.appendMarker(f) || !b.casNext(n, f))//casNext方法就是通过比较和设置b（前驱）的next节点的方式来实现删除操作
findNode(key); // 通过尝试findNode的方式继续find
else {
findPredecessor(key); // Clean index
if (head.right == null) //如果head的right引用为空，则表示不存在该level
tryReduceLevel();
}
return (V)v;
}
}
}

-------------------------------------
ConcurrentSkipListMap的插入

通过SkipList的方式进行插入操作：（下图以“添加55”的两种情况，进行说明：）

在level=2（该level存在）的情况下添加55的图示:只需在level<=2的合适位置插入55即可
--------

在level=4(该level不存在，图示level4是新建的)的情况下添加55的情况：首先新建level4,然后在level<=4的合适位置插入55
-----------
[java]
//put操作，通过doPut实现
public V put(K key, V value) {
if (value == null)
throw new NullPointerException();
return doPut(key, value, false);
}
private V doPut(K kkey, V value, boolean onlyIfAbsent) {
Comparable< super K> key = comparable(kkey);
for (;;) {
Node b = findPredecessor(key);//前驱
Node n = b.next;
//定位的过程就是和get操

Java多线程（四）之ConcurrentSkipListMap深入分析(二)