ConcurrentSkipListMap

在JDK的并发包中，除了常用的哈希表外，还有一种数据结构–跳表。

跳表是一种可以用来快速查找的数据结构，有点类似与平衡树。它们都可以对元素进行快速查找。就查询性能而言，跳表的时间复杂度是O（log n）

跳表的结构图如下：

最底层呢的链表维护了跳表内的所有的元素，每上面一层链表都是下面一层的子集，一个元素插入哪些层是完全随机的。
跳表里面的数据是有序的。
在查找时，可以从*链表开始找，一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这就是说在查找的过程中，搜索是跳跃式的。

我们看跳表的内部实现：

首先是Node ，一个Node表示节点，里面含有两个重要的元素key 和value。每个node还会指向下一个Node，因此还有一个next。

  static final class Node<K,V> {
        final K key;
        volatile Object value;
        volatile Node<K,V> next;

另外一个重要的数据结构是Index， 这个表示索引，它内部包装了Node，同时增加了向下的引用和向右的引用

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

普通方法源码分析：

我们看下put方法：

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

  /**
     * Main insertion method.  Adds element if not present, or
     * replaces value if present and onlyIfAbsent is false.
     * @param kkey 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
     */
    private V doPut(K kkey, V value, boolean onlyIfAbsent) {
        Comparable<? super K> key = comparable(kkey);
  // 将key封装为 Comparable 便于进行比较
        for (;;) {
            Node<K,V> b = findPredecessor(key); 
    //  查找前一个节点
            Node<K,V> n = b.next;// 前一个节点的 后一个节点
  //  即 新节点 插入在b和n之间。
            for (;;) {
                if (n != null) {//n==null 表示 b为最后一个节点
                    Node<K,V> f = n.next;// 为了后面的判断，以防n删除。
                    if (n != b.next)  //如果不等表示 中间已经有元素插入了             // inconsistent read
                        break;
                    Object v = n.value;
                    if (v == null) {               // n is deleted
                        n.helpDelete(b, f);
                        break;
                    }
                    if (v == n || b.value == null) // b is deleted
                        break;
                    int c = key.compareTo(n.key);
                    if (c > 0) { //大于0进行，则判断下一个节点，知道n==null 或者 c＜０
                        b = n;
                        n = f;
                        continue;
                    }
                    if (c == 0) {
                        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);
                if (!b.casNext(n, z))
                    break;         // restart if lost race to append to b
           // 随机计算一个层级     
　　　　　　int level = randomLevel();
                if (level > 0)
                    insertIndex(z, level);
                return null;
            }
        }
    }

接下来我们看下里面的findPredecessor(key)　方法

/**
     * Returns a base-level node with key strictly less than given key,
     * or the base-level header if there is no such node.  Also
     * unlinks indexes to deleted nodes found along the way.  Callers
     * rely on this side-effect of clearing indices to deleted nodes.
     * @param key the key
     * @return a predecessor of 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;　　//从最高层的节点开始遍历
            Index<K,V> r = q.right;//右边的一节点
            for (;;) {
                if (r != null) {
                    Node<K,V> n = r.node;
                    K k = n.key;
                    if (n.value == null) {//表示此节点已删除
                        if (!q.unlink(r))　//删除此节点
                            break;           // restart
                        r = q.right;         // reread r
                        continue;
                    }
                    if (key.compareTo(k) > 0) {// key大　继续循环取下一个节点。
                        q = r;
                        r = r.right;
                        continue;
                    }
                }
　　　　　　　　// 此时key 小于　K ,大于　ｑ的node 的key . 
                Index<K,V> d = q.down;　//查找下一层
                if (d != null) {
                    q = d;
                    r = d.right;
                } else　　// 表示到了最后一层
                    return q.node;
            }
        }
    }