本文共 13012 字，大约阅读时间需要 43 分钟。

什么是跳表 skiplist ?

跳表可以快速地查找、插入、删除。据说可以替代红黑树。Redis中的有序集合就是用调表来实现的。

• 调表结合了链表和二分查找的思想；
• 由原始链表和一些通过”跳跃“生成的链表组成；
• 第0层是原始链表，越上层”跳跃“的越高，元素越少；
• 上层链表是下层链表的子序列；
• 查找时从上到下，不断缩小搜索范围。

特性

调表有很多层，如果只看0层的话，就是一个有序链表。那么其他层呢？

链表查询的时间复杂度为O(n)

若果在此基础之上，增加一层”索引“，查找就会快一点点。

之前直接查找单链表，比如查询结点7，要经过6个结点。 如果加上索引：

经过4个中间结点，比刚刚在链表中查找快乐一点。

更严谨的结构如下，每一层上的索引都是可以向下走的：

最左边的是header节点，不存值，上襦中的31，出现在了第0,1,2,3层，其实就是一个结点。不是四个结点（这个要看具体的实现，这里是通过数组实现，可以通过下标访问，也可以通过链式实现）。这些层次信息是通过forwards(ArrayList)保存的。因此可以很快的访问到下一层。

如果元素个数很多的话，通常层数也会相应的增加。比如我们再增加以层：

再进行上面的查找7的过程的话如下： 中间只经过了3个结点，比刚刚的查找过程更快乐一点。

这里有必要指出的是，每隔一个结点往上提升一层建立索引只是理想情况，实际上是通过随机层数来实现的。

实现

结构

我们将每个节点及没层上的索引信息封装到一个类中：

private class Node {       //保存值    E data;    //保存了每一层上的节点信息，可能为null    List
   
     forwards;    Node(E data) {           this.data = data;        forwards = new ArrayList<>();        //事先把每一层都置为null，虽然空间利用率没那么高，但是简化了实现        //也可以通过自定义列表(比如B树实现中用到的Vector)来实现，就可以不用下面的操作        for (int i = 0; i <= maxLevel; i++) {               forwards.add(null);        }    }    @Override    public String toString() {           return data == null ? " " : "" + data;    }    /**     * 得到当前节点level层上的下一个(右边一个)节点     *     * @param level     * @return     */    Node next(int level) {           return this.forwards.get(level);    }}
   

farwards保存了每一层上的索引信息，如下图所示，farwards描述了红框的信息，值31通过data属性来保存；

next()方法永凯访问同层的右边一个节点。

查找

查找操作时，从顶层向下，不断缩小搜索范围。

以上图中的查找过程为例：

首先从头节点header开始，并起始于顶层（这里是1）。

第1层： 经由1, 4, 6。由于6的下一个节点（这里指的是右边）是8，二我们要查找的是7，因此小于7的最大节点就是6，我们从此往下到达下一层。

第0层：经由6, 7。从6往右就到了7了。找到。

真个查询的时间复杂度为O(log n)

public Node find(E e) {       if (empty()) {           return null;    }    return find(e, head, curLevel);}private Node find(E e, Node current, int level) {       while (level >= 0) {           current = findNext(e, current, level);        level--;    }    return current;}//返回给定层数中小于e的最大者private Node findNext(E e, Node current, int level) {       Node next = current.next(level);    while (next != null) {           if (e.compareTo(next.data) < 0) {               break;        }        //到这说明e >= next.data        current = next;        next = current.next(level);    }    return current;}

插入

给定上述跳表，假设要插入节点2. 首先需要判断节点2是否已经存在，若存在则返回false。 否则，随机生成 待插入的层数。

/** * 生成随机层数[0,maxLevel) * 生成的值越大，概率越小 * * @return */private int randomLevel() {       int level = 0;    while (Math.random() < PROBABILITY && level < maxLevel - 1) {           ++level;    }    return level;}

这里的PROBABILITY = 0.5。上面的算法的意思是：返回1的概率是1/2；返回2的概率是1/4；返回3的概率是1/8；以此类推。

看成是一个分布的话，第0层包含所有节点，第1层含有1/2的节点，第2层返回1/4的节点，…

主义到这里的最大层数maxLevel，也可以不设置最大层数。

通过这种随机产生层数的方式使得实现起来简单。

假设我们生成的层数是3. 在1和3之间插入节点2，层数是3，也就是节点2跳跃到了第3层。

public boolean add(E e) {       if (contains(e)) {           return false;    }    int level = randomLevel();    if (level > curLevel) {           curLevel = level;    }    Node newNode = new Node(e);    Node current = head;    //插入方向由上到下    while (level >= 0) {           //找到比e小的最大节点        current = findNext(e, current, level);        //将newNode插入到current后面        //newNode的next指针指向该节点的后继        newNode.forwards.add(0, current.next(level));        //该节点的next指向newNode        current.forwards.set(level, newNode);        level--;//每层都要插入    }    size++;    return true;}

示例

假设我们要插入：1, 6, 9, 3, 5, 7, 4, 8

add: 1Level 0:  1add: 6Level 0:  1 6add: 9Level 2:      9Level 1:      9Level 0:  1 6 9add: 3Level 2:    3   9Level 1:    3   9Level 0:  1 3 6 9add: 5Level 2:    3     9Level 1:    3 5   9Level 0:  1 3 5 6 9add: 7Level 2:    3       9Level 1:    3 5     9Level 0:  1 3 5 6 7 9add: 4Level 2:    3         9Level 1:    3   5     9Level 0:  1 3 4 5 6 7 9add: 8Level 2:    3           9Level 1:    3   5       9Level 0:  1 3 4 5 6 7 8 9

删除

跳表的删除相对于平衡二叉树来说是很简单的。

测试代码如下：

public static void main(String[] args) {       Random random = new Random();    int[] values = random.ints(2000, 1, 10000).toArray();    // int[] values = {1, 6, 9, 3, 5, 7, 4, 8};    SkipList
   
     list = new SkipList<>();    for (int value : values) {           //System.out.println("add: " + value);        list.add(value);        //list.print();        //System.out.println();    }        for (int value : values) {           list.remove(value);        System.out.println("remove: " + value);        list.print();        System.out.println();    }}
   

删除的过程可以说是插入过程的逆过程。

前面插入了节点2，如果要删除节点2，那就将它的前驱节点指向它的后继节点。

/** * O(logN)的删除算法 * * @param e * @return */public boolean remove(E e) {       if (empty()) {           return false;    }    boolean removed = false;//记录是否删除    int level = curLevel;    //current用于遍历,pre指向待删除节点前一个节点    Node current = head.next(level), pre = head;    while (level >= 0) {           while (current != null) {               //e < current.data            if (e.compareTo(current.data) < 0) {                   break;            }            //只有e >= current.data才需要继续            //如果e == current.data            if (e.compareTo(current.data) == 0) {                   //pre指向它的后继                pre.forwards.set(level, current.next(level));                //设置删除标记                removed = true;                //跳出循环内层循环                break;            }            pre = current;            current = current.next(level);        }        //继续搜索下一层        level--;        if (level < 0) {               //防止next(-1)            break;        }        //往下一层,从pre开始往下即可，不需要从头(header)开始        current = pre.next(level);    }    if (removed) {           size--;//不要忘记size--        return true;    }    return false;}

示例

插入：1, 6, 9, 3, 5, 7, 4, 8 然后删除它：

before remove:Level 4:            7Level 3:            7 8Level 2:      4     7 8Level 1:      4 5   7 8Level 0:  1 3 4 5 6 7 8 9remove: 1Level 4:          7Level 3:          7 8Level 2:    4     7 8Level 1:    4 5   7 8Level 0:  3 4 5 6 7 8 9remove: 6Level 4:        7Level 3:        7 8Level 2:    4   7 8Level 1:    4 5 7 8Level 0:  3 4 5 7 8 9remove: 9Level 4:        7Level 3:        7 8Level 2:    4   7 8Level 1:    4 5 7 8Level 0:  3 4 5 7 8remove: 3Level 4:      7Level 3:      7 8Level 2:  4   7 8Level 1:  4 5 7 8Level 0:  4 5 7 8remove: 5Level 4:    7Level 3:    7 8Level 2:  4 7 8Level 1:  4 7 8Level 0:  4 7 8remove: 7Level 4: Level 3:    8Level 2:  4 8Level 1:  4 8Level 0:  4 8remove: 4Level 4: Level 3:  8Level 2:  8Level 1:  8Level 0:  8remove: 8Level 4: Level 3: Level 2: Level 1: Level 0:

完整代码

package com.algorithms.list;import java.util.*;/** * 跳表 * * @Author: Yinjingwei * @Date: 2019/7/9/009 21:36 * @Description: */public class SkipList
   
    > implements Iterable
    
      {       //当前层数    private int curLevel;    //头结点，不保存值    private Node head;    //跳表中元素个数    private int size;    //用于生成随机层数    private static final double PROBABILITY = 0.5;    //最大层数,也可以写成通过构造函数注入的方式动态设置    private static final int maxLevel = 8;    public SkipList() {           size = 0;        curLevel = 0;        head = new Node(null);    }    public int size() {           return size;    }    public boolean add(E e) {           if (contains(e)) {               return false;        }        int level = randomLevel();        if (level > curLevel) {               curLevel = level;        }        Node newNode = new Node(e);        Node current = head;        //插入方向由上到下        while (level >= 0) {               //找到比e小的最大节点            current = findNext(e, current, level);            //将newNode插入到current后面            //newNode的next指针指向该节点的后继            newNode.forwards.add(0, current.next(level));            //该节点的next指向newNode            current.forwards.set(level, newNode);            level--;//每层都要插入        }        size++;        return true;    }    //返回给定层数中小于e的最大者    private Node findNext(E e, Node current, int level) {           Node next = current.next(level);        while (next != null) {               if (e.compareTo(next.data) < 0) {                   break;            }            //到这说明e >= next.data            current = next;            next = current.next(level);        }        return current;    }    public Node find(E e) {           if (empty()) {               return null;        }        return find(e, head, curLevel);    }    private Node find(E e, Node current, int level) {           while (level >= 0) {               current = findNext(e, current, level);            level--;        }        return current;    }    public boolean empty() {           return size == 0;    }    /**     * O(logN)的删除算法     *     * @param e     * @return     */    public boolean remove(E e) {           if (empty()) {               return false;        }        boolean removed = false;//记录是否删除        int level = curLevel;        //current用于遍历,pre指向待删除节点前一个节点        Node current = head.next(level), pre = head;        while (level >= 0) {               while (current != null) {                   //e < current.data                if (e.compareTo(current.data) < 0) {                       break;                }                //只有e >= current.data才需要继续                //如果e == current.data                if (e.compareTo(current.data) == 0) {                       //pre指向它的后继                    pre.forwards.set(level, current.next(level));                    //设置删除标记                    removed = true;                    //跳出循环内层循环                    break;                }                pre = current;                current = current.next(level);            }            //继续搜索下一层            level--;            if (level < 0) {                   //防止next(-1)                break;            }            //往下一层,从pre开始往下即可，不需要从头(header)开始            current = pre.next(level);        }        if (removed) {               size--;//不要忘记size--            return true;        }        return false;    }    /**     * 生成随机层数[0,maxLevel)     * 生成的值越大，概率越小     *     * @return     */    private int randomLevel() {           int level = 0;        while (Math.random() < PROBABILITY && level < maxLevel - 1) {               ++level;        }        return level;    }    public boolean contains(E e) {           Node node = find(e);        return node != null && node.data != null && node.data.compareTo(e) == 0;    }    @Override    public Iterator
     
       iterator() {           return new SkipListIterator();    }    private class SkipListIterator implements Iterator
      
        {           Node current = head;        @Override        public boolean hasNext() {               return current.next(0) != null;        }        @Override        public E next() {               current = current.next(0);            return current.data;        }    }    private class Node {           //保存值        E data;        //保存了每一层上的节点信息，可能为null        List
       
         forwards;        Node(E data) {               this.data = data;            forwards = new ArrayList<>();            //事先把每一层都置为null，虽然空间利用率没那么高，但是简化了实现            //也可以通过自定义列表(比如B树实现中用到的Vector)来实现，就可以不用下面的操作            for (int i = 0; i <= maxLevel; i++) {                   forwards.add(null);            }        }        @Override        public String toString() {               return data == null ? " " : "" + data;        }        /**         * 得到当前节点level层上的下一个(右边一个)节点         *         * @param level         * @return         */        Node next(int level) {               return this.forwards.get(level);        }    }    public void print() {           //记录了第0层值对应的索引，从1开始        Map
        
          indexMap = new HashMap<>(); Node current = head.next(0); int index = 1; int maxWidth = 1;//值的最大宽度，为了格式化好看一点 while (current != null) { int curWidth = current.data.toString().length(); if (curWidth > maxWidth) { maxWidth = curWidth;//得到最大宽度 } indexMap.put(current.data, index++); current = current.next(0); } print(indexMap, maxWidth); } private void print(int level, Node current, Map
         
           indexMap, int width) { System.out.print("Level " + level + ": "); int preIndex = 0;//该层前一个元素的索引 while (current != null) { //当前元素的索引 int curIndex = indexMap.get(current.data); if (level == 0) { //第0层直接打印即可 printSpace(curIndex - preIndex); } else { //其他层稍微复杂一点 //计算空格数 //相差的元素个数 + 相差的元素个数乘以宽度 int num = (curIndex - preIndex) + (curIndex - preIndex - 1) * width; printSpace(num); } System.out.printf("%" + width + "s", current.data); preIndex = curIndex; current = current.next(level); } System.out.println(); } /** * 打印num个空格 * * @param num */ private void printSpace(int num) { for (int i = 0; i < num; i++) { System.out.print(' '); } } private void print(Map
          
            map, int width) { //从顶层开始打印 int level = curLevel; while (level >= 0) { print(level, head.next(level), map, width); level--; } } public static void main(String[] args) { //Random random = new Random(); //int[] values = random.ints(2000, 1, 10000).toArray(); int[] values = { 1, 6, 9, 3, 5, 7, 4, 8}; SkipList
           
             list = new SkipList<>(); for (int value : values) { //System.out.println("add: " + value); list.add(value); //list.print(); //System.out.println(); } System.out.println("before remove:"); list.print(); System.out.println(); for (int value : values) { list.remove(value); System.out.println("remove: " + value); list.print(); System.out.println(); } }}
           
          
         
        
       
      
     
    
   

参考