JDK的跳表源码实现分析

JDK源码中的跳表实现类： ConcurrentSkipListMap和ConcurrentSkipListSet。其中ConcurrentSkipListSet的实现是基于ConcurrentSkipListMap。因此下面具体分析ConcurrentSkipListMap的实现：

 

    

//查找指定Key的前置节点
  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) {

                    Node<K,V> n = r.node;

                    K k = n.key;

                    if (n.value == null) { 

                        if (!q.unlink(r))  // 如果节点r=q.right为空，则删除该节点r，即把节点q.right指向r.right.

                            break;           // restart 然后跳出本次循环，从头节点开始继续循环。

                        r = q.right;         // reread r 

                        continue;

                    }

                    if (cpr(cmp, key, k) > 0) {// 通过Key值于当前节点的right节点比较，如果Key值较大，则继续往右比较

                        q = r;

                        r = r.right;

                        continue;

                    }

                }

                if ((d = q.down) == null)  // 如果当前节点的down为空，则当前链表为最底层链表，该节点的值<=key，此即为查询结果。

                    return q.node;

                q = d;              // 如果Key值不比当前节点的right节点大，则继续往下比较

                r = d.right;

            }

        }

    }



// 根据Key查找对应的节点



private Node<K,V> findNode(Object key) {

        if (key == null)

            throw new NullPointerException(); // don't postpone errors

        Comparator<? super K> cmp = comparator;

        outer: for (;;) {

            for (Node<K,V> b = findPredecessor(key, cmp), n = b.next;;) {//从key的前置节点开始查找

                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  下一个节点为null,则删除该节点，重新开始查找

                    n.helpDelete(b, f);

                    break;

                }

                if (b.value == null || v == n)  // b is deleted

                    break;

                if ((c = cpr(cmp, key, n.key)) == 0)  //查找到，则返回结果

                    return n;

                if (c < 0)

                    break outer;

                b = n;

                n = f;

            }

        }

        return null;

    }





 private V doGet(Object key) 方法的实现于findNode一致，只是返回值为Value的复制。








/**

     * 

     * Main insertion method.  Adds element if not present, or

     * replaces value if present and onlyIfAbsent is false.

     * @param key the key

     * @param value the value that must be associated with key

     * @param onlyIfAbsent if should not insert if already present

     * @return the old value, or null if newly inserted

     * 新增一个节点过程：

     * 1，根据新增的节点key值，寻找其合适的插入位置b;

     * 2，如果存在相等的key值，则根据onlyIfAbsent决定是否更新对应的Value值，然后返回;

     * 3，如果不存在相等的key值，则创建一个新的节点，并插入到合适的位置b，此时操作的是跳表的最底层;

     * 4，根据随机函数，决定是否添加上层节点，如果不需要添加，则直接返回null;

     * 5，如果需要添加上层节点，则获取随机值level；

     * 6，如果随机值level不大于当前最大层数，则创建一个从第一层到第level层的新的节点Index链表，其通过down指针连接，right指针都设置为null；

     * 7，如果随机值level大于当前最大层数，则跳表的最大层数加1，然后创建一个从第一层到新的最大层的新的节点Index链表，其通过down指针连接，right指针都设置

     *    为null；然后从旧的最大层数+1到新的最大层数间新增head节点链表，其通过down指针连接，right指针指向刚新增的对应层的Index节点；

     * 8，从旧的最大层数开始往最底层，把新增的index节点插入到合适的位置，即更新其right指针(完善第6步的操作)。至此，完成新增节点的整个过程。

     */

    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;;) {// 根据Key找到前置节点，然后开始查找

                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)) {//如果存在key相等的节点，则如果onlyIfAbsent=false，则通过casValue更新Key对应的Value值。如果onlyIfAbsent=true，则不更新Key对应的Value值，然后返回oldValue。

                            @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);  // 没有查找到对应的Key节点，则新增一个节点

                if (!b.casNext(n, z))  // 把新增的节点z设为当前节点的next节点；原子操作，失败则不断的循环操作

                    break;         // restart if lost race to append to b

                break outer;

            }

        }



        int rnd = ThreadLocalRandom.nextSecondarySeed();

        if ((rnd & 0x80000001) == 0) { // test highest and lowest bits   

                                       //8000000001 = 1000 0000 0000 0000 0000 0000 0000 0001 测试最高位和最低位是否为0

            int level = 1, max;

            while (((rnd >>>= 1) & 1) != 0)   //无符号右移1位，   随机获得level值

                ++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增长1

                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);

                    //idx = new Index<K,V>(z,idx,null);  设置idx值，并设置其down和right值

                    //idxs[i] = idx;                     设置每一层中新增的Index节点，其right值都设为null,down值设置为其下一层的Index节点。



                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)         //设置新增的Head节点，设置其node,down,right和level值

                        newh = new HeadIndex<K,V>(oldbase, newh, idxs[j], j);

                    if (casHead(h, newh)) {        //更新head值成功，则退出无限循环

                        h = newh;                  //h 为新的跳表的head节点

                        idx = idxs[level = oldLevel];   //新增的层中，包含Head和idxs[max]两个节点，其指向关系已经确定，而oldLevel中，还没有设置idxs[level]的前置节点，因此idx = idxs[level = oldLevel],说明需要从此层开始至最底层，设置好idxs[level]的前置节点，下面的代码splice完成该功能。

                        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);//key 根当前node.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))     // 把节点t插入到q和r之间，t即新增的节点idx[level]

                            break; // restart

                        if (t.node.value == null) {

                            findNode(key);

                            break splice;

                        }

                        if (--insertionLevel == 0)//层数往下，如果已到最底层，则退出，最底层的节点值在之前的代码中已经完成插入。

                            break splice;

                    }



                    if (--j >= insertionLevel && j < level)

                        t = t.down; //t值更新，t即新增的节点idx[level]

                    q = q.down;

                    r = q.right;

                }

            }

        }

        return null;

    }








/**

     * Main deletion method. Locates node, nulls value, appends a

     * deletion marker, unlinks predecessor, removes associated index

     * nodes, and possibly reduces head index level.

     *

     * Index nodes are cleared out simply by calling findPredecessor.

     * which unlinks indexes to deleted nodes found along path to key,

     * which will include the indexes to this node.  This is done

     * unconditionally. We can't check beforehand whether there are

     * index nodes because it might be the case that some or all

     * indexes hadn't been inserted yet for this node during initial

     * search for it, and we'd like to ensure lack of garbage

     * retention, so must call to be sure.

     *

     * @param key the key

     * @param value if non-null, the value that must be

     * associated with key

     * @return the node, or null if not found

     */

    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))  //如果value不相等，退出

                    break outer;

                if (!n.casValue(v, null))    //无限循环，直至设置节点的值为null成功,

                    break;



                 //之前已经把当前节点值设为null,之后的删除操作分两步：1，在n和n.next间插入一个删除标记节点

//marker； 2，设置b.next为f；这是由两个原子操作共同完成，如果都正常完成，则直接返回；如果有其中一步失败，

//则调用findNode(key)来继续完成删除null节点的操作；

                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;

    }





         /**

         * 添加一个删除标记节点，设置当前节点的next节点为new Node(f),该新增节点的value值为当前节点f.value=f;

         * Tries to append a deletion marker to this node.

         * @param f the assumed current successor of this node

         * @return true if successful

         */

        boolean appendMarker(Node<K,V> f) {

            return casNext(f, new Node<K,V>(f));

        }





         Node(Node<K,V> next) {

            this.key = null;

            this.value = this;

            this.next = next;

        }








         /**

         * compareAndSet next field

         */

        boolean casNext(Node<K,V> cmp, Node<K,V> val) {

            return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);

        }







         /**

         * 继续完成删除节点过程：

         * Helps out a deletion by appending marker or unlinking from

         * predecessor. This is called during traversals when value

         * field seen to be null.

         * @param b predecessor

         * @param f successor

         */

        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 判断是否为marker节点(f.value=f)

                    casNext(f, new Node<K,V>(f));

                else

                    b.casNext(this, f.next);

            }

        }

 

删除步骤：

1， 删除前，需要删除节点n：

      

2，删除时，先设置n.value= null; 无限循环，直至成功为止；

3，添加删除标记节点marker：

marker 节点的key=null, value=f, next=f;

4，删除该节点n以及标记节点marker:

 

其中步骤2，3，4分别由3个CAS原子操作完成。步骤2保证成功，步骤3或者4只要有一个失败，此时的n.value = null, 因此都可以由节点遍历的操作来继续推进删除过程。

为什么删除操作要分为3步，而不是由一个步骤(步骤4)来完成？因为CAS操作只能保证一个变量操作的原子性。