[JDK源码]-J.U.C-ConcurrentSkipListMap

由于作者水平有限，如有什么错误点，多谢指出。

public class ConcurrentSkipListMap extends AbstractMap
    implements ConcurrentNavigableMap, Cloneable, Serializable {
    //链表头部的 特殊值
    private static final Object base_HEADER = new Object();
 
    // 跳表 最顶层索引
    private transient volatile HeadIndex head;

    // 比较器 K按照什么比较
    final Comparator comparator;

     //懒加载的 几个集合
    private transient KeySet keySet;
    
    private transient EntrySet entrySet;
    
    private transient Values values;
    
    private transient ConcurrentNavigableMap descendingMap;
    //保存K-V的节点
    static final class Node {
        final K key;
        volatile Object value;
        volatile Node next;
        //创建节点
        Node(K key, Object value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }
        //创建一个新的标记节点。 标记的区别在于它的值字段指向它自己。  
        //创建新的标记节点，在删除节点时使用，注意这里的节点 k null v 指向它自己
        Node(Node next) {
            this.key = null;
            this.value = this;
            this.next = next;
        }
    }
    // 跳表的索引节点， 层级结构
    static class Index {
        final Node node;
        final Index down;
        volatile Index right;
    }
    //每层 index 索引节点的头节点
    static final class HeadIndex extends Index {
        final int level;
        HeadIndex(Node node, Index down, Index right, int level) {
            super(node, down, right);
            this.level = level;
        }
    }
    //默认构造
    public ConcurrentSkipListMap() {
        this.comparator = null;
        initialize();
    }
}

private void initialize() {
    keySet = null;
    entrySet = null;
    values = null;
    descendingMap = null;
    //初始化头部索引节点 
    head = new HeadIndex(new Node(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 V doPut(K key, V value, boolean onlyIfAbsent) {
    Node z;             // 要添加的节点
    if (key == null)
        throw new NullPointerException();
    Comparator cmp = comparator; //比较器
    outer: for (;;) {//循环  直到插入node节点
        //找到 k要放的的位置的  前一个和后一个节点 b n
        for (Node b = findPredecessor(key, cmp), n = b.next;;) {
            if (n != null) {	//b后边还有节点
                Object v; int c;
                Node f = n.next;	//n的下一个节点
                if (n != b.next)               // n不是 b的下一个节点了  重新开始 
                    break;
                if ((v = n.value) == null) {   // n 被删除了， 帮助删除，重试
                    n.helpDelete(b, f);
                    break;
                }
                if (b.value == null || v == n) // b被删除了
                    break;
                if ((c = cpr(cmp, key, n.key)) > 0) {//当前k 和 n的k比较， 需不需要更新
                    b = n;
                    n = f;
                    continue;
                }
                if (c == 0) {	//二者相等
                    //如果onlyIfAbsent 设置为true，不进行旧值替换，否则替换旧值并返回旧值
                    if (onlyIfAbsent || n.casValue(v, value)) {
                        @SuppressWarnings("unchecked") V vv = (V)v;
                        return vv;
                    }
                    break; // 如果 失败，此时退出当前循环 重试 
                }
            }
			//找到了插入当前的位置
            z = new Node(key, value, n);
            if (!b.casNext(n, z))
                break;         // CAS将b的next修改为z ，失败重试
            break outer;//退出外循环 完成插入
        }
    }
	// 插入成功  是否需要更新索引
    int rnd = ThreadLocalRandom.nextSecondarySeed(); //当前线程获取一个随机数
    if ((rnd & 0x80000001) == 0) { //10000000000000000000000000000001  & 随机数 :最高最低 是不是1
        int level = 1, max;
        while (((rnd >>>= 1) & 1) != 0)//当前节点应该处于的层级  (随机数右移 & 1) 
            ++level;
        Index idx = null;
        HeadIndex h = head;	//索引链表的头节点
        if (level <= (max = h.level)) {	//当前节点的层数 <= 头节点的层数
            for (int i = 1; i <= level; ++i)	
                idx = new Index(z, idx, null);
        }
        else { // 当前层大于 head 的层 
            level = max + 1; // 当前level 设置为 原 + 1
            //创建层级索引 数组
            @SuppressWarnings("unchecked")Index[] idxs =
                (Index[])new Index[level+1];
            for (int i = 1; i <= level; ++i)//创建层级索引	
                idxs[i] = idx = new Index(z, idx, null);
            for (;;) {// 更新头节点
                h = head;	//原头节点
                int oldLevel = h.level;//原 层
                if (level <= oldLevel) // 如果已经 小于了 原层，表示其他线程更新了  退出
                    break;
                HeadIndex newh = h;
                Node oldbase = h.node;	//原头节点指向的 node
                for (int j = oldLevel+1; j <= level; ++j)//创建每一层 索引的头节点
                    // 头节点的 right 节点指向当前 idxs[j]   层数为j
                    newh = new HeadIndex(oldbase, newh, idxs[j], j);
                if (casHead(h, newh)) {//更新索引节点的 头节点
                    h = newh;	//h为最新的头节点
                    idx = idxs[level = oldLevel]; //当前索引节点为 level 下标处的节点
                    break;
                }
            }
        }
        // 找到插入点并拼接进去	
        splice: for (int insertionLevel = level;;) {//从最顶层 level开始
            int j = h.level;	//头节点的层数
            for (Index q = h, r = q.right, t = idx;;) {//循环直到插入成功
                if (q == null || t == null)//头节点或者刚 创建的节点已经被删除
                    break splice;
                if (r != null) {//q 是不是最后一个
                    Node n = r.node;
                    // 比较当前K 和 right索引的 node节点的 V的值
                    int c = cpr(cmp, key, n.key);
                    if (n.value == null) {//如果 n的V为空
                        if (!q.unlink(r))//q的 next指向 r的next  失败重试  成功 获取新的 right节点
                            break;
                        r = q.right;
                        continue;
                    }
                    if (c > 0) {
                        q = r;	//更新q为右边索引
                        r = r.right;//r 更新为原来r 的 right 节点
                        continue;
                    }
                }
				//头节点的层 等于 待插入的 层
                if (j == insertionLevel) {
                    if (!q.link(r, t))// 节点插入q r 中间
                        break; // 失败重试
                    if (t.node.value == null) {//node 节点被删除 调用findNode - 删除中间被删除的节点，然后停止索引节点插入
                        findNode(key);
                        break splice;
                    }
                    //全部插入完成
                    if (--insertionLevel == 0)
                        break splice;
                }
				//从 索引头节点往下寻找 找到正确的插入的 层
                if (--j >= insertionLevel && j < level)
                    t = t.down;
                q = q.down;	//层 下移
                r = q.right;//获取新的 right节点
            }
        }
    }
    return null;
}

首先通过 head索引节点获取到层级的 头节点然后 这个节点找到 下一个索引节点 去判断

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

private V doGet(Object key) {
    if (key == null)
        throw new NullPointerException();
    Comparator cmp = comparator;
    outer: for (;;) {
        //findPredecessor 找到小于给定K 的前一个节点  以及下一个节点 n
        for (Node b = findPredecessor(key, cmp), n = b.next;;) {
            Object v; int c;
            if (n == null)//b是最后一个节点 退出
                break outer;
            Node f = n.next; 	//获取n的下一个节点
            if (n != b.next)                // b的next发生了改变
                break;
            if ((v = n.value) == null) {    // n删除了
                n.helpDelete(b, f);
                break;
            }
            if (b.value == null || v == n)  // b 删除了
                break;
            if ((c = cpr(cmp, key, n.key)) == 0) {//比较n的k和传入的k， 如果相同返回 V值
                @SuppressWarnings("unchecked") V vv = (V)v;
                return vv;
            }
            if (c < 0)//表示K 的值小于 n的值，表示链表中 不存在
                break outer;
            b = n;//往后继续查找
            n = f;
        }
    }
    return null;
}
//找到小于给定K的前一个节点 
private Node findPredecessor(Object key, Comparator cmp) {
    if (key == null)
        throw new NullPointerException(); // don't postpone errors
    for (;;) {
        //索引节点的头节点 和 right 节点
        for (Index q = head, r = q.right, d;;) {
            if (r != null) {//右节点存在
                Node n = r.node;
                K k = n.key;	
                if (n.value == null) { //n被删除了
                    if (!q.unlink(r))	//尝试断开r
                        break;           
                    r = q.right;         // 读取新的右节点
                    continue;
                }
                if (cpr(cmp, key, k) > 0) { // 当前K 大于节点 n的值，根据索引节点往后查找
                    q = r;
                    r = r.right;
                    continue;
                }
            }
            //下一层找，如果是最后溢出 q.node 就是找到的节点
            if ((d = q.down) == null)
                return q.node;
            q = d;// 更新q 下降后的
            r = d.right; //右  也更新
        }
    }
}

public V remove(Object key) {
    return doRemove(key, null);
}
final V doRemove(Object key, Object value) {
    if (key == null)
        throw new NullPointerException();
    Comparator cmp = comparator;
    outer: for (;;) {
        //先找到 给定K 的  前面的节点b 和 后面 n
        for (Node b = findPredecessor(key, cmp), n = b.next;;) {
            Object v; int c;
            if (n == null) //n 不存在
                break outer;
            Node f = n.next;	//n的 next  f
            if (n != b.next)                    // n 不是 b的next了
                break;
            if ((v = n.value) == null) {        // n被删 
                n.helpDelete(b, f);
                break;
            }
            if (b.value == null || v == n)      // b 被删
                break;
            if ((c = cpr(cmp, key, n.key)) < 0) //如果 n 的K 大于 给定的K，n不是要找的k
                break outer;
            if (c > 0) {//n的K 小于给定的K， 可能其他线程插入了比K小的，往前找，更新 b n
                b = n;
                n = f;
                continue;
            }
            //如果 value 不为空  和当前n 的value 比较，不等退出
            if (value != null && !value.equals(v))
                break outer;
            if (!n.casValue(v, null)) //n的value 设置为null 
                break;
            if (!n.appendMarker(f) || !b.casNext(n, f))//清除， b的next设置为 f
                findNode(key);                  // 如果其他线程完成了  findNode(返回满足当前K的节点，并删除沿途发现的已经被删除的节点)
            else {
                findPredecessor(key, cmp);     // 删除成功  findPredecessor(删除n的索引节点)
                if (head.right == null)
                    tryReduceLevel();
            }
            @SuppressWarnings("unchecked") V vv = (V)v;
            return vv;
        }
    }
    return null;
}

就是通过Map 来实现的

public class ConcurrentSkipListSet
    extends AbstractSet
    implements NavigableSet, Cloneable, java.io.Serializable {
    public ConcurrentSkipListSet() {
        m = new ConcurrentSkipListMap();
    }
    public boolean add(E e) {
    	return m.putIfAbsent(e, Boolean.TRUE) == null;
	}
    
    public boolean remove(Object o) {
    	return m.remove(o, Boolean.TRUE);
	}
    
    public boolean contains(Object o) {
        return m.containsKey(o);
    }
    
    
}