# ConcurrentSkipListMap

# 原理

跳表：一种加了索引的链表

复杂度：log(n)

以多层链表的形式实现，每一层都下一层的部分节点，可以看成上层是下层的索引。

最底层是全部的数据，按顺序存储的链表。

主要三种节点

  1. 头节点：无数据，有层级属性
  2. 普通节点：数据节点，next指针
  3. 索引节点：数据，next指针，down指针

删除操作

  1. cas将节点值更新为null。表示节点已删除，next指针还需要变更。
  2. cas将next的节点更新为marker节点。
  3. cas将前面节点的next指针指向其后面节点，从而跳过当前节点

# 实现

# 节点实现

static final class Node<K,V> {
    final K key;
    volatile Object value;
    volatile Node<K,V> next;
    
    boolean isMarker() {
        return value == this;
    }
    boolean isBaseHeader() {
        return value == BASE_HEADER;
    }
    
    void helpDelete(Node<K,V> b, Node<K,V> f) {
        if (f == next && this == b.next) {
            if (f == null || f.value != f) // not already marked
                casNext(f, new Node<K,V>(f));
            else
                b.casNext(this, f.next);
        }
    }
  1. 当value==this表示当前节点是个marker节点
  2. 当value等于一个特殊空对象时表示一个头节点
  3. 删除节点，输入前，后两个节点，删除当前节点

删除需要多个阶段，一次调用只处理一个阶段的方法

# 索引节点

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

    final boolean indexesDeletedNode() {
        return node.value == null;
    }
    
    final boolean link(Index<K,V> succ, Index<K,V> newSucc) {
        Node<K,V> n = node;
        newSucc.right = succ;
        return n.value != null && casRight(succ, newSucc);
    }
    final boolean unlink(Index<K,V> succ) {
        return node.value != null && casRight(succ, succ.right);
    }
  1. node.value是null时表示该节点已经删除
  2. link方法表示插入一个后继节点
  3. unlink删除一个索引节点

# 头节点

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

一个特殊的索引节点

# 操作

# 放

# 取

# 删

原理
实现
操作