ConcurrentSkipListMap学习

基本数据结构

ConcurrentSkipListMap中主要有三个基本信息
1.节点的基本信息
2.节点的关联信息
3.节点的层级信息

    static final class Node<K,V> {
        final K key;
        volatile Object value;
        volatile Node<K,V> next;
    }
    static class Index<K,V> {
        final Node<K,V> node;
        final Index<K,V> down;
        volatile Index<K,V> right;
    }
    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;
        }
    }

重要字段

下面这些是一些比较重要的字段,先了解下有个印象


    /**
     * Special value used to identify base-level header
     */
    private static final Object BASE_HEADER = new Object();

    /**
     * The topmost head index of the skiplist.
     */
    private transient volatile HeadIndex<K,V> head;

    /**
     * The comparator used to maintain order in this map, or null if
     * using natural ordering.  (Non-private to simplify access in
     * nested classes.)
     * @serial
     */
    final Comparator<? super K> comparator;

    /** Lazily initialized key set */
    private transient KeySet<K> keySet;
    /** Lazily initialized entry set */
    private transient EntrySet<K,V> entrySet;
    /** Lazily initialized values collection */
    private transient Values<V> values;
    /** Lazily initialized descending key set */
    private transient ConcurrentNavigableMap<K,V> descendingMap;

构造函数

接下来是构造函数, 主要负责两件事,第一初始化比较器compator, 第二调用initialize方法

    public ConcurrentSkipListMap() {
        this.comparator = null;
        initialize();
    }

    public ConcurrentSkipListMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
        initialize();
    }

    private void initialize() {
        keySet = null;
        entrySet = null;
        values = null;
        descendingMap = null;
        //注意这个head对象,后续会用到
        head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null),
                                  null, null, 1);
    }


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

辅助方法

这里先介绍个常用的方法, 就是在插入操作的时候,找到应该插入的位置。

    private Node<K,V> findPredecessor(Object key, Comparator<? super K> cmp) {
        if (key == null)
            throw new NullPointerException(); // don't postpone errors
        for (;;) {
            for (Index<K,V> q = head, r = q.right, d;;) {
                if (r != null) {
                    //head的右边节点,定义为r, r的当前节点定义为n
                    Node<K,V> n = r.node;
                    K k = n.key;
                    //如果节点n的value为null,则删除这个节点
                    if (n.value == null) {
                        if (!q.unlink(r))
                            break;           // restart
                        r = q.right;         // reread r
                        continue;
                    }

                    //如果key比n.key大, 右移一位
                    if (cpr(cmp, key, k) > 0) {
                        q = r;
                        r = r.right;
                        continue;
                    }
                }

                //走到这个分支,存在两种情况
                //case1: r节点之前已经是最右边的节点了
                //case2:  插入的key小于r索引当前node节点的key
                if ((d = q.down) == null)
                    //表示q节点在第一层,我们已经找到了插入位置直接返回
                    return q.node;

                //q节点不在第一层,那么按照q=.down节点重新寻找合适的位置    
                q = d;
                r = d.right;
            }
        }
    }

接下来我会举个简单例子, 结合上面的代码和我画的图片来解释下怎么找到插入节点的前一个节点的:

如果我们现在需要插入的node.key为3

按照上面代码分析,首先是 q=head, r=head.right, 我们结合图片以及代码得出 q.node.key = 1, r.node.key=5,

r!=null 并且 r.key 等于5大于3, 这个时候会判断 q.down 是否为 null,我们知道q的层级此刻是2,

那我们现在需要做的是把 q 设成它的下一级, q=q.down, 这个时候 q 的 key 还是1,

r=q.right, r.key 是2,由于刚才没有跳出循环,这个时候我们会从 if(r!=null) 这里重新开始处理,

我们发现 cpr(cmp, key, k) > 0 成立, 这个时候 q 和 r 都需要右移一位,

q 是在第一层,q.down=null 成立, 这个时候我们直接返回 q.node 就好, 所以我们判断出来需要插入 3 的时候前面一个节点的key是2


put方法

插入操作,步骤太长了,大体上可以分为三个步骤,

    //Step1
    private V doPut(K key, V value, boolean onlyIfAbsent) {
        //key校验
        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;;) {
                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) {
                        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;
            }
        }

        //Step2
        int rnd = ThreadLocalRandom.nextSecondarySeed();
        if ((rnd & 0x80000001) == 0) { // test highest and lowest bits
            int level = 1, max;
            while (((rnd >>>= 1) & 1) != 0)
                ++level;
            Index<K,V> idx = null;
            HeadIndex<K,V> h = head;
            if (level <= (max = h.level)) {
                for (int i = 1; i <= level; ++i)
                    idx = new Index<K,V>(z, idx, null);
            }
            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 = idxs[level = oldLevel];
                        break;
                    }
                }
            }
            //Step3
            // 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))
                                break;
                            r = q.right;
                            continue;
                        }
                        if (c > 0) {
                            q = r;
                            r = r.right;
                            continue;
                        }
                    }

                    if (j == insertionLevel) {
                        if (!q.link(r, t))
                            break; // restart
                        if (t.node.value == null) {
                            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;
    }

文章目录
  1. 1. 基本数据结构
  2. 2. 重要字段
  3. 3. 构造函数
  4. 4. 辅助方法
  5. 5. put方法