跳跃表学习笔记

跳跃表(Skip List)，是一种基于概率，提供了查找、插入、删除近似于O(logN)性能的数据结构。

这篇文章是学习跳跃表的一个记录，包含了跳跃表的原理以及其Java实现

介绍

跳跃表(Skip List)，是一种基于概率，提供了查找、插入、删除近似于O(logN)性能的数据结构。

在线性数据结构中，查找、插入、删除性能均为O(N)，当数据量比较大的时候，是非常不乐观的，因此，科学家们相处了各种各样的数据结构来进行优化，将线性的数据结构进行一系列转换，从而得到在理想情况下查找、插入、删除性能均为或近似为O(logN)的数据结构，前面提到的AVL、红黑树是通过平衡(旋转、变色)等将线性数据结构转换为平衡树，从而利用平衡树的特性来实现O(logN)的复杂度

除了平衡树之外，还有另外一种数据结构，跳跃表，采取另类的思路来实现同样的性能优化，平衡树等牺牲的是部分的操作性能，而跳跃表牺牲的则是空间

跳跃表可以达到与红黑树等类似的性能，并且实现起来相对简单，虽然消耗部分空间，但也具有一定的应用场景，例如redis中的sorted set、Java中的ConcurrentSkipListMap就是通过跳跃表来实现的

原理

跳跃表本质上是基于链表，并且跳跃表中的元素是有序的(默认根据key递减)

传统的链表查找、插入、删除操作都是O(N)，跳跃表对其进行了优化，为原来的链表建立多个层次(基于概率函数)的索引，每个层次的索引依次递减(通过概率来控制，而非严格的数量关系)，从而建立了一个基于链表的性能卓越的跳跃表数据结构，如下图所示：

最底层黄色的节点是实际上真正的数据节点，从最底层往上的每一个层次都是下一个层次的索引

查找节点

在查找的时候，从最head节点出发，在最顶层开始往右边查找，直到第一个不小于目标值的节点出现，说明目标节点位于当前节点区间，从上图中也可以看到，最顶层的索引是非常稀疏的，所以最上层节点的查找速度是非常快的，然后从当前节点往下一层次查找，重复上述步骤，直到到达最底层

举个栗子：查找节点8

1. head的最顶层(第4层)出发，此时已经到达第四层的末尾处
2. 从第3层出发，1<8，4<8,6<8，此时已经到达第三层的末尾处
3. 从第二层key为6的节点出发，9>8，继续往下一层查找
4. 从第一层key为6的节点出发，6<8，7<8,8=8，找到目标节点

可以看到，此时仅仅需要4次查找，而链表本身的长度为10

插入节点

插入节点的前部分操作与查找节点一样，先找到离目标节点最近的节点(目标节点或前一个节点)，然后插入目标节点，根据概率函数，计算当前节点应该所占有的层次，然后依次补充将每个层次对应的索引链表连接起来(普通的链表插入操作)

具体插入步骤参见上图

删除节点

删除节点的操作步骤与插入节点类似，只是现在是找到之后，将其从各个层次的索引链表中删除(普通的链表删除操作)

注：以上所有的图片均来自维基百科-跳跃表介绍

实现

从上面的描述以及图片示例，大致上已经能够猜测出实现的代码结构了

ListNode

static class ListNode {
    // key
    private final String key;

    private String value;

    // 当前节点的层次数，由random函数生成
    private Integer level;

    private final ListNode[] nexts;

    public ListNode(String key, String value, Integer level) {
        this.key = key;
        this.value = value;
        this.level = level;
        this.nexts = new ListNode[level];
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "key='" + key + '\'' +
                ", value='" + value + '\'' +
                ", level=" + level +
                '}';
    }
}

SimpleSkipList

/**
 * @author huanfeng
 */
public class SimpleSkipList {

    // 节点的最高层次数
    private static final int MAX_LEVEL = 16;
    
    // 控制每一层的概率
    private static final double RATE = 0.25;

    // 跳跃表的头结点，该节点是空节点
    private ListNode head = new ListNode(null, null, MAX_LEVEL);
    
    private int size = 1;
    
    private Random random = new Random();
    
    private Integer randomLevel() {
        int level = 1;
        while (level < MAX_LEVEL &&
               Double.compare(random.nextDouble(), RATE) < 0) {
            level++;
        }
        return level;
    }
}

get：获取元素

public ListNode get(String key) {
    ListNode preNode = head;
    int level = preNode.level;

    // 注意这里查找出来的是目标key的前一个节点
    // 从最高一层的索引链表往后、下查找
    for (int i = level - 1; i >= 0; i--) {
        // 判断next.val是否小于当前的key
        while (preNode.nexts[i] != null &&
               preNode.nexts[i].key.compareTo(key) < 0) {
            preNode = preNode.nexts[i];
        }
        // 往下一层继续查找
    }

    // 如果前一个元素存在，并且其next的key等于目标key，说明我们找到了
    if (preNode.nexts[0] != null &&
        preNode.nexts[0].key.compareTo(key) == 0) {
        return preNode.nexts[0];
    }
    return null;
}

put：添加元素

public void put(String key, String value) {
    ListNode preNode = head;

    // 先查找看是否存在，存在则替换
    ListNode currentNode = get(key);
    if (currentNode != null && currentNode.key.compareTo(key) == 0) {
        currentNode.value = value;
        return;
    }

    int level = randomLevel();

    ListNode[] nextHolder = new ListNode[level];

    // 默认新插入的节点都由head指向，并且指向head.next
    // eg:
    //     next = head.next
    //     head -> newNode -> next
    for (int i = 0; i < level; i++) {
        nextHolder[i] = head;
    }

    for (int i = level - 1; i >= 0; i--) {
        while (preNode.nexts[i] != null &&
                preNode.nexts[i].key.compareTo(key) < 0) {
            preNode = preNode.nexts[i];
        }
        // 获取当前层次的next
        nextHolder[i] = preNode;
    }

    ListNode newNode = new ListNode(key, value, level);

    for (int i = 0; i < level; i++) {
        // 将当前节点插入到所有层次中
        // node的第i层的next = 目标节点的i层的next
        newNode.nexts[i] = nextHolder[i].nexts[i];
        // 目标节点的i层的next指向当前的node
        nextHolder[i].nexts[i] = newNode;
    }

    head.level = Math.max(level, head.level);
    size++;
}

remove

public ListNode remove(String key) {

    ListNode preNode = head;
    int level = preNode.level;

    ListNode[] nextHolder = new ListNode[level];

    for (int i = level - 1; i >= 0; i--) {
        while (preNode.nexts[i] != null &&
               preNode.nexts[i].key.compareTo(key) < 0) {
            preNode = preNode.nexts[i];
        }
        nextHolder[i] = preNode;
    }

    // 找不到
    if (preNode.nexts[0] == null ||
        preNode.nexts[0].key.compareTo(key) != 0) {
        return null;
    }

    // 注意这里的步骤是必须的，因为跳跃表的level是随机的
    // 因此，不是preNode的每一层的next都是指向目标节点
    for (int i = level - 1; i >= 0; i--) {
        if (nextHolder[i].nexts[i] != null &&
            nextHolder[i].nexts[i].key.compareTo(key) == 0) {
            nextHolder[i].nexts[i] = nextHolder[i].nexts[i].nexts[i];
        }
    }
    return preNode.nexts[0];
}