欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ConcurrentSkipListMap

程序员文章站 2022-06-28 15:46:21
...

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

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

跳表的结构图如下:

ConcurrentSkipListMap

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

我们看跳表的内部实现:

首先是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<0
                        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 ,大于 q的node 的key . 
                Index<K,V> d = q.down; //查找下一层
                if (d != null) {
                    q = d;
                    r = d.right;
                } else  // 表示到了最后一层
                    return q.node;
            }
        }
    }

相关标签: 数据结构 跳表