JDK并发工具类源码学习系列——ConcurrentSkipListMap

x33g5p2x  于2021-12-18 转载在 其他  
字(8.1k)|赞(0)|评价(0)|浏览(299)

更多文章请阅读:JDK并发工具类源码学习系列目录。
ConcurrentSkipListMap在JDK并发工具类使用范围不是很广,它是针对某一特殊需求而设计的——支持排序,同时支持搜索目标返回最接近匹配项的导航方法。一般情况下开发者很少会使用到该类,但是如果你有如上的特殊需求,那么ConcurrentSkipListMap将是一个很好地解决方案。
Java Collections Framework中另一个支持排序的Map是TreeMap,两者都是有序的哈希表,但是TreeMap是非线程安全的,当然可以使用Collections.synchronizedSortedMap将TreeMap进行包装,但是性能方面就显得捉急了,毕竟多个线程一起读都需要加锁是不太合理的,至少做到读写分离呀。但是从JDK1.6开始我们就多了一个选择:ConcurrentSkipListMap。这是一个支持高并发度的有序哈希表,并且是无锁的,可在多线程环境下替代TreeMap。
下面我们从几个方面来分析ConcurrentSkipListMap的实现,主要分析ConcurrentSkipListMap的数据结构以及如何实现高并发且无锁读写的。

  • 实现原理
  • 数据结构
  • 常用方法解读
  • 使用场景
实现原理

ConcurrentSkipListMap不同于TreeMap,前者使用SkipList(跳表)实现排序,而后者使用红黑树。相比红黑树,跳表的原理比较容易理解,简单点说就是在有序的链表上使用多级索引来定位元素。下面是简单看看SkipList的原理:

现在假设我们拥有一个有序的列表,如果我们想要在这个列表中查找一个元素,最优的查找算法应该是二分 查找了,但是链表不想数组,链表的元素是非连续的,所以无法使用二分查找来进行高效查找,那么抛开其他查找算法不说,最低效的算法就是从链表头部开始遍历,直至找到要查找的元素,虽说低效但是确是最大化使用了链表的优势——遍历。那么我们有没有可能同时提高查找效率,而且还使用链表的优势呢?跳表就是我们想要的查找算法。其实说白了跳表就是一种多级索引,通过索引链表中的部分值来确定被查找的值所处的范围。

跳表分为多层,层数越高,最高层元素越少,查找时也会越快,但是所占空间也就越多,所以跳表是用空间换时间(可见如果大量数据不是太适用,毕竟内存是有限的)。

跳表结构示意图:

可以看见每一层都是一个有序的链表,而且是原始链表的子集,最底层(level1)是完整的链表结构,越往上链表的元素越少,同时查找也就越快。当我们需要查找一个元素时,会从跳表的最上层链表开始查询,定位元素的大致位置,然后通过向下指针再在下层查找。

跳表查找示意图:

上图是从跳表中查找32的过程。
跳表的查找时间复杂度是:O(log(n)),更多详细关于跳表的介绍可参考:http://kenby.iteye.com/blog/1187303

数据结构

ConcurrentSkipListMap在原始链表的基础上增加了跳表的结构,所以需要两个额外的内部类来封装链表的节点,以及跳表的节点——NodeIndex

Node:链表的节点
static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
}

同ConcurrentHashMap的Node节点一样,key为final,是不可变的,value和next通过volatile修饰保证内存可见性。

Index:跳表的节点
static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;
    volatile Index<K,V> right;
}

Index封装了跳表需要的结构,首先node包装了链表的节点,down指向下一层的节点(不是Node,而是Index),right指向同层右边的节点。node和down都是final的,说明跳表的节点一旦创建,其中的值以及所处的层就不会发生变化(因为down不会变化,所以其下层的down都不会变化,那他的层显然不会变化)。
Node和Index内部都提供了用于CAS原子更新的AtomicReferenceFieldUpdater对象,至于该对象的原理下面是不会深入研究的。

常用方法解读

从API文档可以看到ConcurrentHashMap的方法很多,很多都是一些为了方便开发者的提供的,例如subMap(K, boolean, K, boolean)、headMap(K, boolean)、tailMap(K, boolean)等都是用来返回一个子视图的方法。这里我们主要看看能够表达ConcurrentHashMap实现原理的三个方法:put(K, V)、get(Object)、remove(Object, Object)。
在介绍这三个方法之前,我们先看一个辅助工具方法:comparable(Object)。

/** * If using comparator, return a ComparableUsingComparator, else * cast key as Comparable, which may cause ClassCastException, * which is propagated back to caller. */
// @By Vicky:将key封装成一个Comparable对象
private Comparable<? super K> comparable(Object key) throws ClassCastException {
    if (key == null)
        throw new NullPointerException();
    // @By Vicky:有两种封装方法,如果在构造时指定了comparator,则使用comparator封装key
    // 如果没有指定comparator,则key必须是一个继承自Comparable接口的类,否则会抛出ClassCastException
    // 所以ConcurrentSkipListMap的key要么是继承自Comparable接口的类,如果不是的话需要显示提供comparator进行比较
    if (comparator != null)
        return new ComparableUsingComparator<K>((K)key, comparator);
    else
        return (Comparable<? super K>)key;
}

从上面那个辅助方法可以看到ConcurrentSkipListMap的key必须要能够进行比较,可以有两种方式提供比较方法,代码注释中已提到。

put(K, V)
public V put(K key, V value) {
   if (value == null)
       throw new NullPointerException();
   // @By Vicky:实际调用内部的doPut方法
   return doPut(key, value, false);
}

/** * @By Vicky: * 三个参数,其中onlyIfAbsent表示是否只在Map中不包含该key的情况下才插入value,默认是false */
private V doPut(K kkey, V value, boolean onlyIfAbsent) {
    // 将key封装成一个Comparable对象,便于直接与其他key进行比较
    Comparable<? super K> key = comparable(kkey);
    for (;;) {
        // 从跳表中查找最接近指定key的节点:该节点的key小于等于指定key,且处于最底层
        Node<K,V> b = findPredecessor(key);
        Node<K,V> n = b.next;// b的下一个节点,新节点即将插入到b与n之间
        // 准备插入
        for (;;) {
            if (n != null) {// n==null则说明b是链表的最后一个节点,则新节点直接插入到链表尾部即可
                Node<K,V> f = n.next;// n的下一个节点
                if (n != b.next)               // inconsistent read 此处增加判断,避免链表结构已被修改(针对节点b)
                    break;;
                Object v = n.value;
                if (v == null) {               // n is deleted
                    n.helpDelete(b, f);// 将n从链表移除,b和f分别为n的前继节点与后继节点
                    break;
                }
                // 这里如果v==n说明n是一个删除标记,用来标记其前继节点已被删除,即b已被删除
                // 查看helpDelete()的注释
                if (v == n || b.value == null) // b is deleted
                    break;
                // 比较key,此处进行二次比较是避免链表已发生改变,比如b后面已被插入一个新的节点
                // (findPredecessor时已经比较过b的next节点(n)的key与指定key的大小,因为n的key>指定key才会返回b)
                int c = key.compareTo(n.key);
                if (c > 0) {// 如果指定key>n的key,则判断下一个节点,直到n==null,或者指定key<n的key
                    b = n;
                    n = f;
                    continue;
                }
                if (c == 0) {// 相等,则更新value即可,更新失败,就再来一次,一直到成功为止
                    if (onlyIfAbsent || n.casValue(v, value))
                        return (V)v;
                    else
                        break; // restart if lost race to replace value
                }
                // else c < 0; fall through
            }
            // 创建一个节点,next指向n
            Node<K,V> z = new Node<K,V>(kkey, value, n);
            // 将b的next指向新创建的节点,则新的链表为:b-->new-->n,即将新节点插入到b和n之间
            if (!b.casNext(n, z))
                break;         // restart if lost race to append to b
            // 随机计算一个层级
            int level = randomLevel();
            // 将z插入到该层级
            if (level > 0)
                insertIndex(z, level);
            return null;
        }
    }
}

代码中已经附上了大量的注释,这里再简单的梳理下流程。首先put()方法是调用内部的doPut()方法。Comparable< ? super K&> key = comparable(kkey);这一句将key封装成一个Comparable对象,上面已经介绍了comparable这个方法。接着进入到死循环,循环第一步是调用**findPredecessor(key)**方法,该方法返回一个key最接近指定key的节点(最接近指的是小于等于),该节点是处于最底层的,下面介绍下这个方法的逻辑。

/** * @By Vicky: * 在跳表中查找节点的key小于指定key,且处于最底层的节点,即找到指定key的前继节点 * 基本逻辑是从head(跳表的最高层链表的头结点)开始自右开始查找,当找到该层链表的最接近且小于指定key的节点时,往下开始查找, * 最终找到最底层的那个节点 */
private Node<K,V> findPredecessor(Comparable<? super K> key) {
    if (key == null)
        throw new NullPointerException(); // don't postpone errors
    for (;;) {
        Index<K,V> q = head;// head是跳表的最高层链表的头结点
        Index<K,V> r = q.right;// head的右边节点
        for (;;) {// 循环
            if (r != null) {// r==null说明该层链表已经查找到头,且未找到符合条件的节点,需开始往下查找
                Node<K,V> n = r.node;// r的数据节点
                K k = n.key;// r的key,用于跟指定key进行比较
                if (n.value == null) { // n的value为null,说明该节点已被删除
                    if (!q.unlink(r))// 将该节点从链表移除,通过将其(n)前置节点的right指向其(n)的后置节点
                        break;           // restart
                    r = q.right;         // reread r 移除value==null的n节点之后,继续从n的下一个节点查找
                    continue;
                }
                if (key.compareTo(k) > 0) {// 比较当前查找的节点的key与指定key,如果小于指定key,则继续查找,
                                           // 大于等于key则q即为该层链表最接近指定key的
                    q = r;
                    r = r.right;
                    continue;
                }
            }
            // 到这里有两种情况:1)该层链表已经查找完,仍未找到符号条件的节点 2)找到一个符合条件的节点
            // 开始往下一层链表进行查找
            Index<K,V> d = q.down;
            if (d != null) {// 从下层对应位置继续查找
                q = d;
                r = d.right;
            } else// 如果无下层链表则直接返回当前节点的node
                return q.node;
        }
    }
}

// @By Vicky:将当前节点的right指向succ的right指向的节点,即将succ从链表移除
final boolean unlink(Index<K,V> succ) {
    return !indexesDeletedNode() && casRight(succ, succ.right);
}

该方法的查找逻辑是:从head(跳表的最高层链表的头结点)开始自右开始查找,当找到该层链表的最接近且小于指定key的节点时,往下开始查找,最终找到最底层的那个节点。具体的代码可以看注释,应该说的挺明白的了,针对PUT方法,这个方法返回的节点就是将要插入的节点的前继节点,即新节点将插到该节点后面。下面是查找的示意图。

findPredecessor查找示意图:

findPredecessor()介绍完,我们返回doPut()继续往下走。通过findPredecessor()返回节点b,获取b的next节点赋值n,接着进入死循环。判断n是否为null,n==null则说明b是链表的最后一个节点,则新节点直接插入到链表尾部即可,下面我们来看看n!=null的情况。

Node<K,V> f = n.next;// n的下一个节点
if (n != b.next)     // inconsistent read 此处增加判断,避免链表结构已被修改(针对节点b)
   break;;
Object v = n.value;
if (v == null) {               // n is deleted
    n.helpDelete(b, f);// 将n从链表移除,b和f分别为n的前继节点与后继节点
    break;
}
// 这里如果v==n说明n是一个删除标记,用来标记其前继节点已被删除,即b已被删除
// 查看helpDelete()的注释
if (v == n || b.value == null) // b is deleted
    break;

这里首先判断在这段时间内b的next是否被修改,如果被修改则重新获取。再接着判断n和b是否被删除。这里说下helpDelete()方法,这个方法比较绕。

void helpDelete(Node<K,V> b, Node<K,V> f) {
    /* * Rechecking links and then doing only one of the * help-out stages per call tends to minimize CAS * interference among helping threads. */
    if (f == next && this == b.next) {
        // 判断当前节点是否已添加删除标记,未添加则添加删除标记
        if (f == null || f.value != f) // not already marked
            appendMarker(f);
        else
        // 如果已添加删除标记,则将b的next指向f的next
        // 因为当前节点已添加了删除标记,所以这里的f只是一个标记:value==本事的节点,其next才是链表的下一个节点
        // 这里应该是remove方法相关,涉及到ConcurrentSkipListMap的删除方式
            b.casNext(this, f.next);
    }
}

/** * @By Vicky:为当前节点增加一个删除标记 * 将当前节点的next指向一个新节点,该新节点的next指向f,所以从结构是:当前-->new-->f * 新节点的value就是他自己,参见Node(Node<K,V> next)构造函数 * 即删除标记就是将一个节点与其next节点之间插入一个value就是本事的节点 */
boolean appendMarker(Node<K,V> f) {
    return casNext(f, new Node<K,V>(f));
}

介绍helpDelete()之前,先简单介绍ConcurrentSkipListMap是如何删除一个节点的,其实ConcurrentSkipListMap删除一个节点现将该节点的value值为NULL,然后再为这个节点添加一个删除标记,但是这个操作有可能失败,所以如果一个节点的value为NULL,或者节点有一个删除标记都被认为该节点已被删除。appendMarker()就是用来添加删除标记,helpDelete()是用来将添加了删除标记的节点清除。添加标记和如何清除在代码中的注释已经说的很清楚了,就不多说了。继续看doPut()。

// 比较key,此处进行二次比较是避免链表已发生改变,比如b后面已被插入一个新的节点
// (findPredecessor时已经比较过b的next节点(n)的key与指定key的大小,因为n的key>指定key才会返回b)
int c = key.compareTo(n.key);
if (c > 0) {// 如果指定key>n的key,则判断下一个节点,直到n==null,或者指定key<n的key
    b = n;
    n = f;
    continue;
}
if (c == 0) {// 相等,则更新value即可,更新失败,就再来一次,一直到成功为止
    if (onlyIfAbsent || n.casValue(v, value))
        return (V)v;
    else
        break; // restart if lost race to replace value
}
// else c < 0; fall through

这几句是考虑当我们找到一个最接近指定key的节点之后有可能链表被修改,所以还需要进行二次校验,从b开始往右边查找,直至找到一个key大于指定key的节点,那么新的节点就插入到该节点前面。

// 创建一个节点,next指向n
Node<K,V> z = new Node<K,V>(kkey, value, n);
// 将b的next指向新创建的节点,则新的链表为:b-->new-->n,即将新节点插入到b和n之间
if (!b.casNext(n, z))
    break;         // restart if lost race to append to b
// 随机计算一个层级
int level = randomLevel();
// 将z插入到该层级
if (level > 0)
    insertIndex(z, level);
return null;

这几句就是创建一个新的节点,并插入到原链表中,所有的修改操作都是使用CAS,只要失败就会重试,直至成功,所以就算多线程并发操作也不会出现错误,而且通过CAS避免了使用锁,性能比用锁好很多。

请继续阅读后续部分~~~

相关文章