【Java多线程】JUC集合 03. ConcurrentSkipListMap

ConcurrentSkipListMap

1. 前言

• ConcurrentSkipListMap是线程安全的有序的Map，适用于高并发的场景。
• 不允许空键、值
• ConcurrentSkipListMap和TreeMap的区别：
  • 都是有序的哈希表
  • ConcurrentSkipListMap是线程安全的，而TreeMap是非线程安全的
  • ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。
• 跳表(Skip List)：它是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

2. 源码分析

2.1 数据结构

UML类图：

跳表：

2.2 内部类

• Index

static class Index<K,V> {
    final Node<K,V> node;
    final Index<K,V> down;	//down域
    volatile Index<K,V> right;	//right域

    /**
     * Creates index node with given values.
     */
    Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
        this.node = node;
        this.down = down;
        this.right = right;
    }
}

• HeadIndex

static final class HeadIndex<K,V> extends Index<K,V> {
    final int level;	//层级
    HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) {
        super(node, down, right);
        this.level = level;
    }
}

• Node

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;	//下一个节点，单链表结构

    /**
     * Creates a new regular node.
     */
    Node(K key, Object value, Node<K,V> next) {
        this.key = key;
        this.value = value;
        this.next = next;
    }

    /**
     * Creates a new marker node. A marker is distinguished by
     * having its value field point to itself.  Marker nodes also
     * have null keys, a fact that is exploited in a few places,
     * but this doesn't distinguish markers from the base-level
     * header node (head.node), which also has a null key.
     */
    Node(Node<K,V> next) {	//用于建立标记节点，值为本身，在删除时使用
        this.key = null;
        this.value = this;
        this.next = next;
    }
    //删除结点，在结点后面添加一个marker结点或者将结点和其后的marker结点从其前驱中断开。
    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) { // f为当前结点的后继并且b为当前结点的前驱
            if (f == null || f.value != f) // not already marked  没有被标记  
                // 当前结点后添加一个marker结点，并且当前结点的后继为marker，marker结点的后继为f
                casNext(f, new Node<K,V>(f)); 
            else // f不为空并且f的值为本身
                // 设置b的next域为f的next域
                b.casNext(this, f.next);
        }
    }
}

2.3 核心函数

2.3.1 put(K key, V value)

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    return doPut(key, value, false);
}

put()通过doPut()方法添加键值对：

private V doPut(K key, V value, boolean onlyIfAbsent) {
    Node<K,V> z;             // added node
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    outer: for (;;) {
        for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {//b为先驱结点，n为b的后继结点
            if (n != null) {
                Object v; int c;
                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) {//key大于结点n的key
                    b = n;	//向后移动
                    n = f;
                    continue;
                }
                if (c == 0) {
                    if (onlyIfAbsent || n.casValue(v, value)) {
                        @SuppressWarnings("unchecked") V vv = (V)v;
                        return vv;
                    }
                    break; // restart if lost race to replace value
                }
                // else c < 0; fall through
            }

            z = new Node<K,V>(key, value, n);//新建结点
            if (!b.casNext(n, z))
                break;         // restart if lost race to append to b
            break outer;//跳出外层循环
        }
    }
	// 随机生成种子
    int rnd = ThreadLocalRandom.nextSecondarySeed();
    if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
        int level = 1, max;
        while (((rnd >>>= 1) & 1) != 0) //判断从右到左有多少个连续的1
            ++level;
        Index<K,V> idx = null;
        HeadIndex<K,V> h = head;
        if (level <= (max = h.level)) {
            for (int i = 1; i <= level; ++i)//生成对应的Index结点
                idx = new Index<K,V>(z, idx, null);//从下至上依次赋值，并且赋值了Index结点的down域
        }
        else { // try to grow by one level
            level = max + 1; // hold in array and later pick the one to use
            @SuppressWarnings("unchecked")Index<K,V>[] idxs =
                (Index<K,V>[])new Index<?,?>[level+1];
            for (int i = 1; i <= level; ++i)
                idxs[i] = idx = new Index<K,V>(z, idx, null);
            for (;;) {
                h = head;
                int oldLevel = h.level;
                if (level <= oldLevel) // lost race to add level
                    break;
                HeadIndex<K,V> newh = h;
                Node<K,V> oldbase = h.node;
                for (int j = oldLevel+1; j <= level; ++j)// 为每一层生成一个头结点
                    newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);
                if (casHead(h, newh)) {
                    h = newh;
                    // idx赋值为之前层级的头结点，并将level赋值为之前的层级
                    idx = idxs[level = oldLevel];
                    break;
                }
            }
        }
        // find insertion points and splice in
        splice: for (int insertionLevel = level;;) {
            int j = h.level;
            for (Index<K,V> q = h, r = q.right, t = idx;;) {
                if (q == null || t == null)
                    break splice;
                if (r != null) {
                    Node<K,V> n = r.node;
                    // compare before deletion check avoids needing recheck
                    int c = cpr(cmp, key, n.key);
                    if (n.value == null) {
                        if (!q.unlink(r))//删除r的index结点
                            break;
                        r = q.right;
                        continue;
                    }
                    if (c > 0) {
                        q = r; // 向右寻找
                        r = r.right;
                        continue;
                    }
                }

                if (j == insertionLevel) {
                    if (!q.link(r, t)) //idx 插入q和r之间
                        break; // restart
                    if (t.node.value == null) {//idx结点值为空，需要删除
                        findNode(key);
                        break splice;
                    }
                    if (--insertionLevel == 0)
                        break splice;
                }

                if (--j >= insertionLevel && j < level)//下一层
                    t = t.down;
                q = q.down;
                r = q.right;
            }
        }
    }
    return null;
}

流程如下：

• 根据给定的key从跳表的左上方往右或者往下查找到Node链表的前驱Node结点，这个查找过程会删除一些已经标记为删除的结点
• 找到前驱结点后，开始往后插入查找插入的位置（因为找到前驱结点后，可能有另外一个线程在此前驱结点后插入了一个结点，所以先前查找的前驱现在可能不是要插入的结点的前驱，所以需要往后查找）。
• 随机生成一个种子，判断是否需要增加层级，并且在各层级中插入对应的Index结点。

2.3.2 remove()

public V remove(Object key) {
    return doRemove(key, null);
}

final V doRemove(Object key, Object value) {
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    outer: for (;;) {
         //b为key的前继结点， n为“b的后继节点”(即若key存在于“跳表中”，n就是key对应的节点)
        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;
            }
            // c = 0 的情况
            if (value != null && !value.equals(v))
                break outer;
            if (!n.casValue(v, null)) //当前结点n的value设置为null
                break;
            // 在n结点后添加一个marker结点，并且将b的next域更新为f
            if (!n.appendMarker(f) || !b.casNext(n, f))
                findNode(key);                  // retry via findNode
            else {// 添加节点并且更新均成功
                // 清除跳表中每一层n结点对应的Index结点
                findPredecessor(key, cmp);      // clean index
                if (head.right == null)
                    tryReduceLevel();//减少层级
            }
            @SuppressWarnings("unchecked") V vv = (V)v;
            return vv;
        }
    }
    return null;
}

流程如下：

• 根据key值找到前驱结点，查找的过程会删除一个标记为删除的结点
• 从前驱结点往后查找该结点
• 在该结点后面添加一个marker结点，若添加成功，则将该结点的前驱的后继设置为该结点之前的后继
• 头结点的next域是否为空，若为空，则减少层级。

// 减少跳表层级
private void tryReduceLevel() {
    // 保存头结点
    HeadIndex<K,V> h = head;
    HeadIndex<K,V> d;
    HeadIndex<K,V> e;
    if (h.level > 3 &&
        (d = (HeadIndex<K,V>)h.down) != null &&
        (e = (HeadIndex<K,V>)d.down) != null &&
        e.right == null &&
        d.right == null &&
        h.right == null &&
        casHead(h, d) && // try to set
        h.right != null) // recheck
        casHead(d, h);   // try to backout
}

说明：如果最高的前三个HeadIndex不为空，并且其right域都为null，那么就将level减少1层，并将head设置为之前head的下一层，设置完成后，还有检测之前的head的right域是否为null，如果为null，则减少层级成功，否则再次将head设置为h。

2.3.4 get()

public V get(Object key) {
    return doGet(key);
}

private V doGet(Object key) {
    if (key == null)
        throw new NullPointerException();
    Comparator<? super K> cmp = comparator;
    outer: for (;;) {
        //b - key的前驱结点 n - 当前结点
        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) {//key为当前结点
                @SuppressWarnings("unchecked") V vv = (V)v;
                return vv;
            }
            if (c < 0)
                break outer;
            b = n;	//向后查找
            n = f;
        }
    }
    return null;
}

3. 参考

http://www.cnblogs.com/skywang12345/p/3498556.html

https://www.cnblogs.com/leesf456/p/5512817.html