By

文章目录
  1. Skip List
    1. 1. overview
    2. 2. 查找
    3. 3. 插入
    4. 4. 更新
    5. 5. 删除
    6. 6. 打印跳表结构
    7. 7. 测试

Skip List

1. overview

  • Skip List是一种经过优化的链表，通过存储了冗余的节点作为跳板指针，提供了O(logn)的增删改查效率
  • 结构与算法过程较红黑树更容易理解，实现也更简单

  • 如果某一层拥有某节点，则其下每一层均有该节点，之间存在指针关联，例如3,5
  • 链表的层数在插入节点时有机会更新，采用丢硬币方法，如果产生的新层数newLevel比原始层数level大，则加一层并且且在新层及其以下层均插入节点，否则，在newLevel至底层间所有层插入节点

存储结构如图所示，红色线条代表查询路径，在跳板指针的帮助下，直接跳过了大部分节点，很容易的可以写出搜索代码

首先给出基础的节点定义与变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
//当前跳表层数
private int level = 1;
//头节点的key
private static final int HEAD_KEY = Integer.MIN_VALUE;
//节点数
private int count = 0;
private Random r;
private static final double PROBABILITY = 0.5;//向上提升一个的概率
//顶层指针
private Node top;
//底层链表指针
private Node bottomHead;
/**
 * 跳表的节点定义
 */
private class Node {
    Node next;
    Node down;
    int key;
    V value;
    int level;
    public Node() {
    }
    public Node(int key, V value) {
        this.key = key;
        this.value = value;
    }
    public Node(int key, V value, int level) {
        this.key = key;
        this.value = value;
        this.level = level;
    }
    public Node(Node node, int level) {
        this.key = node.key;
        this.value = node.value;
        this.level = level;
    }
    public Node(Node node) {
        this.key = node.key;
        this.value = node.value;
    }
}
/**
 * 初始化
 */
private void initList() {
    //空表 初始化
    top = new Node(HEAD_KEY, null);
    bottomHead = top;
}
/**
 * 确定新的层数，随机丢硬币
 *
 * @return
 */
private int newLevel() {
    int level = 0;
    while (r.nextDouble() > PROBABILITY) {
        level++;
    }
    return level;
}

2. 查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 查找节点
 *
 * @param key
 *
 * @return
 */
public Node find(int key) {
    Node p = top;
    if (p == null) {
        return null;
    }
    while (true) {
        while (p.next != null && p.next.key <= key) {
            p = p.next;
        }
        if (p.down != null) {
            p = p.down;
        } else {
            break;
        }
    }
    if (p.key == key) {
        return p;
    }
    return null;
}

3. 插入

  • 如图红色区域所示，插入节点的核心思想，找到需要插入层的新节点位置之前的指针，循环指针完成指针指向即可
  • 插入节点之前需要确认新的随机层数，之后找到开始插入的层，由上到下
  • 注意不要使用每一层都重新查找的方式进行节点插入，可行，但是速度极慢
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    /**
     * 插入
     *
     * @param value
     *
     * @return
     */
    public Node insert(int key, V value) {
        List<Node> noteToUpdate = Lists.newArrayList();
        //迭代各层寻找需要插入key节点的前置节点，放入List
        Node p = top;
        while (true) {
            while (p.next != null && p.next.key <= key) {
                p = p.next;
            }
            noteToUpdate.add(p);
            if (p.down != null) {
                p = p.down;
            } else {
                break;
            }
        }
        //查询是否存在，如果存在，最后一个节点一定是
        Node lastOne = noteToUpdate.get(noteToUpdate.size() - 1);
        if (lastOne.key == key) {
            return lastOne;
        }
        //新层数，如果比现在大，就赋值1，增加一层，否则根据随机值向下寻找插入节点的首层
        int newLevel = newLevel() - level;
        newLevel = newLevel > 0 ? 1 : newLevel;
        Node headNode = top;
        //新层数小于当前层，则从高层开始，每层插入节点即可
        while (newLevel != 0) {
            if (newLevel > 0) {
                Node oldHead = headNode;
                headNode = new Node(HEAD_KEY, null, oldHead.level + 1);
                headNode.down = oldHead;
                top = headNode;
                level++;
                newLevel--;
                //增加新层，则要插入的节点需要增加，放在List头部，节点就是新headNode
                noteToUpdate.add(0, headNode);
                continue;
            }
            if (newLevel < 0) {
                if (headNode.down != null) {
                    headNode = headNode.down;
                    //插入层向下移动，则要插入的节点需要减少，从头开始减少
                    noteToUpdate.remove(0);
                }
                newLevel++;
            }
        }
        //循环各个需要插入的节点进行插入，并配置向下指针
        //此处从末尾节点开始，方便配置down指针
        Node bottomNode = null;
        for (int i = noteToUpdate.size() - 1; i >= 0; i--) {
            Node pre = noteToUpdate.get(i);
            Node preNext = pre.next;
            Node node = new Node(key, value, pre.level);
            pre.next = node;
            node.next = preNext;
            node.down = bottomNode;
            bottomNode = node;
        }
        count++;
        return null;
    }

4. 更新

  • 如图蓝色路径显示，找到该节点，从上到下更新即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
    * 更新
    *
    * @param key
    *
    * @return
    */
   private Node update(int key, V value) {
       Node p = top;
       while (true) {
           while (p.next != null && p.next.key <= key) {
               p = p.next;
           }
           if (p.key == key) {
               break;
           } else {
               if (p.down != null) {
                   p = p.down;
               } else {
                   p = null;
                   break;
               }
           }
       }
       if (p == null) {
           return null;
       }
       Node updated = p;
       while (p != null) {
           updated = p;
           p.value = value;
           p = p.down;
       }
       return updated;
   }

5. 删除

  • 如图紫色路径显示，找到该节点的所有前驱，从上到下更新指向下一个节点即可
  • 同时需要处理空层，将其去除
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * 删除
 *
 * @param key
 *
 * @return
 */
private void delete(int key) {
    Node p = top;
    Node head = p;
    List<Node> noteToUpdate = Lists.newArrayList();
    List<Node> headTodelete = Lists.newArrayList();
    while (true) {
        while (p.next != null && p.next.key < key) {
            p = p.next;
        }
        if (p.next != null && p.next.key == key) {
            noteToUpdate.add(p);
        }
        headTodelete.add(head);
        if (p.down != null) {
            p = p.down;
            head = head.down;
        } else {
            break;
        }
    }
    Node old;
    for (Node node : noteToUpdate) {
        old = node.next;
        node.next = old.next;
        //释放指针
        old.next = null;
        old.down = null;
    }
    for (Node headNode : headTodelete) {
        if (headNode.next == null && null != headNode.down) {
            top = headNode.down;
        }
    }
}

6. 打印跳表结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/**
 * 打印跳表结构
 *
 * @return
 */
private void showNodes() {
    List<V> values = Lists.newArrayList();
    Node headFirst = bottomHead.next;
    while (headFirst != null) {
        values.add(headFirst.value);
        headFirst = headFirst.next;
    }
    Node head = top, p;
    while ((p = head) != null) {
        int lineSepratorCount = 0;
        List<Integer> downPointer = Lists.newArrayList();
        while (p != null) {
            if (p.key == HEAD_KEY) {
                System.out.print("HEAD");
            } else {
                //计算这个value在底层链表中的索引
                int valueIndex = values.indexOf(p.value);
                //计算本次输出需要输出的-----> 如果是底层就是1，如果不是就是本次value序号减去当前行已经输出的---->
                int sepratorCount = head == bottomHead ? 1 : valueIndex + 1 - lineSepratorCount;
                //保存需要输出竖线的索引
                downPointer.add(valueIndex);
                //更新并输出---->
                lineSepratorCount = lineSepratorCount + sepratorCount;
                for (int i = 0; i < sepratorCount; i++) {
                    //如果不是紧接着数值的输出，多输出一个-,用于补位
                    if (sepratorCount > 1 && i < sepratorCount - 1) {
                        printChar(1, '-');
                    }
                    printChar(4, '-');
                    System.out.print(">");
                }
                System.out.print(p.value);
            }
            p = p.next;
        }
        head = head.down;
        //输出竖线
        if (head != null) {
            System.out.println();
            //补位HEAD的输出，输出头节点之间的竖线
            System.out.print(" |  ");
            //输出竖线，如果当前索引在需要输出竖线的List中，则输出竖线，否则输出6个空格
            for (int i = 0; i < lineSepratorCount; i++) {
                printChar(5, ' ');
                if (downPointer.contains(i)) {
                    System.out.print("|");
                } else {
                    printChar(1, ' ');
                }
            }
            System.out.println();
        }
    }
    System.out.println();
}
/**
 * 输出空格
 */
private void printChar(int num, char cahr) {
    for (int i = 0; i < num; i++) {
        System.out.print(cahr);
    }
}

7. 测试

  • 插入应该仍有优化空间
    1
    2
    3
    4
    5
    6
    7
    8
    ArrayList插入时间：174ms , 数量:5000000
    ArrayList搜索时间：18ms
    LinkedList插入时间：2991ms , 数量:5000000
    LinkedList搜索时间：31ms
    SkipList插入时间：3717ms , 数量:5000000,层数：22
    SkipList搜索时间：0ms
    RBtree插入时间：1583ms , 数量:5000000
    RBtree搜索时间：0ms
文章目录
  1. Skip List
    1. 1. overview
    2. 2. 查找
    3. 3. 插入
    4. 4. 更新
    5. 5. 删除
    6. 6. 打印跳表结构
    7. 7. 测试