源码角度了解ConcurrentSkipListMap
文章目录
源码角度了解ConcurrentSkipListMap
ConcurrentSkipListMap的key是有序的，它是基于跳查表来进行实现的map，跳查表可以实现无锁的链表，我们知道链表的操作插入元素的时候直接修改前一个位置的节点，指向这个节点，然后这个节点又指向下一个节点，删除元素的时候直接修改前一个位置的节点指向删除节点的下一个节点，当插入和删除并发执行的时候，可能出现问题，把插入的节点删除。
如图，插入8 ，删除3这个操作同时进行的话，插入8操作的是3的后继节点，删除3操作的是3的前驱节点，这个操作互相感知不到，这样会出现并发的问题，因此ConcurrentSkipListMap使用了跳表，不同的是在节点3删除的时候就进行标记它的后继节点，让后继节点指向一个marker节点，这样插入的时候就判断是否进行了删除节点的操作，从而感知到删除操作。
跳查表的数据结构
* Head nodes Index nodes
* +-+ right +-+ +-+
* |2|---------------->| |--------------------->| |->null
* +-+ +-+ +-+
* | down | |
* v v v
* +-+ +-+ +-+ +-+ +-+ +-+
* |1|----------->| |->| |------>| |----------->| |------>| |->null
* +-+ +-+ +-+ +-+ +-+ +-+
* v | | | | |
* Nodes next v v v v v
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
* | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
* +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+这是源码中描述的数据结构，非常权威😄
put()方法
put()方法的比较复杂，这里大体说一下它的逻辑：从顶层index开始，从左到右，从上到下进行遍历，调用findPredecessor()方法找到插入元素的区间范围[b,n]，然后进行检查校验，因为区间节点可能被其他线程删除
get()方法
get()方法的逻辑和put()方法也差不多，同样是从左到右，从上到下来进行遍历，定位到区间范围[b,n]之后，判断边界值b和n是否被删除，如果没有删除，取出需要的数据，如果删除了就进行清理操作，然后继续查找
remove()方法
remove()方法中调用的是doremove()方法
ConcurrentSkipListMap的doremove()方法：
final V doRemove(Object key, Object value) {
if (key == null)
throw new NullPointerException();
Comparator<? super K> cmp = comparator;
outer: for (;;) {
for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {
Object v; int c;
if (n == null)
break outer;
Node<K,V> f = n.next;
if (n != b.next) // inconsistent read
break;
if ((v = n.value) == null) { // n is deleted
n.helpDelete(b, f);
break;
}
if (b.value == null || v == n) // b is deleted
break;
if ((c = cpr(cmp, key, n.key)) < 0)
break outer;
if (c > 0) {
b = n;
n = f;
continue;
}
if (value != null && !value.equals(v))
break outer;
if (!n.casValue(v, null))
break;
if (!n.appendMarker(f) || !b.casNext(n, f))
findNode(key); // retry via findNode
else {
findPredecessor(key, cmp); // clean index
if (head.right == null)
tryReduceLevel();
}
@SuppressWarnings("unchecked") V vv = (V)v;
return vv;
}
}
return null;
}remove()方法和put()方法类似，也是通过findPredecessor()方法先找到删除的元素所在的区间[b,n]，如果b或n删除了，就调用执行相应的清理逻辑，如果找到了需要被删除的，就对节点的value设置为空，同时在删除节点的下一个指针指向Marker节点，最后我们判断一下是否需要对index的层次降低
ConcurrentSkipListSet
ConcurrentSkipListSet和ConcurrentSkipListMap差不多，相当于ConcurrentSkipListMap的扩展类，ConcurrentSkipListSet的构造方法中创建了ConcurrentSkipListMap对象赋值给成员变量ConcurrentNavigableMap对象，ConcurrentNavigableMap被定义为final类型来保证线程安全，它的元素的值是true，它对元素的其他操作都是调用的ConcurrentSkipListMap的方法
总结
本篇文章介绍了ConcurrentSkipListMap的源码，主要是它的数据结构跳查表的引入和数据结构是怎样的，并通过它的put()方法、get()方法等介绍了跳查表是怎么定位一个元素的，最后讲了它的扩展类ConcurrentSkipListSet，ConcurrentSkipListSet其实是让ConcurrentSkipListMap对象来作为它的成员变量，它对元素的操作都是调用ConcurrentSkipListMap中的方法。
腾讯云开发者
