639-跳跃表SkipList-蒲公英云

跳跃表SkipList介绍

在这里插入图片描述

所有的元素都是在最底下（第一层）出现的，然后往上走，会把第一层的某些元素在第二层存储一下，然后再往上走，会把第二层的某些元素在第三层存储一下，以此类推下去。
每一层都是有序的链表，默认从小到大。

哪些元素往上面一层放呢？

在这里插入图片描述
K=1，然后进入while循环，随机数是0或者1，相当于是不断抛硬币的过程，符号我们正态分布的过程。也就是说，抛一万次硬币，得到的结果近似一半正面朝上，一半的正面朝下，符合正态分布的结果。
我们根据抛硬币的方式决定下面这一层的某一个元素是否需要在上一层再存储一遍。
也就是说，从我们的正态分布的角度来看，最终我们可能会把趋于下面这一层的一半的元素提升到上面这一层来。
再往上一层走，就把下面的第二层的所有元素进行抛硬币，然后把近似一半的元素提到第三层再存储一遍。
这样，最终就和我们的二叉树一样了，最顶层可能就1个元素节点。
然后它的下面一层可能是2个，以此类推。
其实，这个过程，搭建起来跳表的过程，元素的组织方式和我们的二叉搜索树是非常相似的。
在这里插入图片描述

跳跃表的查找搜索元素

在这里插入图片描述
可以想象：从根节点开始，因为越往上，元素越少。
因为117大于21，意味着它把21之前的元素就不用比较了，这和我们的二分搜索（二叉搜索树）很相似。
相当于就是从根节点，在每一层找一个合适的节点，然后再往下一层跑。
就是二叉搜索树的搜索方式！！！
在这里插入图片描述

跳跃表的插入

搜索元素是从最上面的那层元素开始搜索的。
如果要插入元素，
在这里插入图片描述
如果我们要插入119这个数字，通过抛硬币，决定119要插几行。
跳表本身是3行，插2行是没有问题的。
在最后一行按序插入，因为要插2行，所以在第二行也插了一个119
假如我们要插入119，但是抛硬币抛出了4层，但是跳表只有3层，但是最终我们也是要插4层的，也就是说，在最上层（第4层）就只有一个数字119
但是如果说，这个跳表只有3层，在插入数字119的时候，抛硬币的结果是5层，在5层里面都要添加119这个数字，但是跳表只有3层，所以我们最终也是只插4层就可以了。
在这里插入图片描述
跳表的层数增长是一层一层增长的，不会一下子多个层，每个层放的数据一样。

K初始化=1，因为一定要在最底层添加元素。然后按照随机进行K++

跳跃表的删除操作

在这里插入图片描述
如果我们要删除元素37，首先得查找，我们是从最上层开始查找，我们在最上层（level3）一下子就找到37这个元素了，既然这个37在level3出现了，那么37肯定还出现在level2和level1中，如果我们在第三层，也就是最上层找到37了，然后往下，把这3个节点都删除了。也就是：在每一层中，把37的前面1个节点的地址域写成37后面的那个节点的地址。
如果我们要删除元素71，首先是查找，在最上层中遍历到37，比37大，再往找的话，已经是末尾节点1了，所以71在level3上不存在，所以从37直接往下走，走到level2层，然后往后走，找到了71，然后就不用往后找了，往下找！因为没有到最底层，所以下面都是71，从上到下，把这个垂直上的71全部删除掉，也就是每一层的71的前一个节点的地址域存储71后一个节点的地址。
在这里插入图片描述

跳跃表的优缺点

在这里插入图片描述

插入元素119只改动这部分的数据：
在这里插入图片描述
如果在并发进行的时候，71前面的这些节点的改动
和71后面的插入元素操作是可以并发执行的，互不影响的。
如果在多线程环境下，并发条件下，使用跳跃表进行线程安全控制的话，如果添加锁，插入119，就不需要给整个跳跃表进行加锁控制了，只需要给71后面这一段添加锁的控制，实现线程互斥就可以了。
但是，对于红黑树来说，红黑树节点着色，以及节点的旋转，它可能影响的是整个树都要改变，红黑树在实现并发安全的时候，插入和删除操作都必须给整个树进行锁的控制了。红黑树在进行并发操作，实现线程互斥，锁的粒度大，而跳跃表实现锁的粒度比较小，更利于并发的效率。

跳跃表在删除元素也是一样的。
在这里插入图片描述
如果我们要删除元素71，也是一样的，对下面这一部分进行加锁控制就可以了
37之前的部分在进行修改的时候是可以并发进行的。

但是对于红黑树来说，如果删除的是一个黑色节点，需要从兄弟节点借一个黑色，如果兄弟节点借不了，把兄弟节点置为红色，然后向上回溯。极端情况就是回溯到根节点，把所有路径上都减少一个根节点，意味着红黑树的删除需要对整个树进行加锁解锁控制。

但是跳跃表相当于红黑树，是在空间换时间，占用内存比较大。红黑树中，所有元素值只是存储一个节点的，但是在跳跃表中，所有的元素不仅仅在最下面那层出现，而且根据抛硬币选出来的元素在上面层进行存储，以此类推上去，模拟了一个二分查找搜索树的过程，简化了红黑树，达到O(logn)的搜索和删除的时间复杂度，而且实现起来比较简单。
在实际应用场景中，跳跃表和红黑树在很多情况下是可以互换的。

redis：非常强大的分布式缓存服务器，源码的数据存储就是跳跃表，增删查是O(logn)。

跳跃表SkipList的代码实现

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<iostream>//cin;
using namespace std; 
#define MAX_LEVEL 10//最大层数  
typedef int KeyType;
typedef int ElemType;
typedef  struct SkipNode  
{
    KeyType key;  
    ElemType value;  
    SkipNode *forward[];//方向指针 
}SkipNode;  
//跳跃表  
typedef  struct
{
    int level;//层数 
    SkipNode *head;//头节点 
}SkipList;  
//创建节点  
SkipNode* BuyNode(int level,int key,int value)  
{
    SkipNode *s=(SkipNode *)malloc(sizeof(SkipNode)+level*sizeof(SkipNode*)); 
    if(NULL == s) exit(1);
    memset(s,0,sizeof(SkipNode)+level*sizeof(SkipNode*));
    s->key=key;    
    s->value=value;    
    return s;    
}  
void Freenode(SkipNode *p)//释放节点 
{
    free(p);
}
SkipList* CreateSkipList()//创建跳跃表 
{
    SkipList *s = (SkipList *)malloc(sizeof(SkipList));  
    if(NULL == s) exit(1);
    memset(s,0,sizeof(SkipList));
    s->level=0;    
    s->head = BuyNode(MAX_LEVEL-1,0,0);    
    for(int i=0;i < MAX_LEVEL;i++)    
    {
        s->head->forward[i]=NULL;    
    }  
    return s;  
}  
//随机产生层数  抛硬币 
int RandomLevel()    
{
    int k=1; 
    //srand(time(NULL));
    while(rand()%2)   
    {
        k++;    
    }
    k=(k<MAX_LEVEL)? k: MAX_LEVEL;  
    return k;    
}  
//插入节点  
bool InsertItem(SkipList *s,int key,int value)  
{
    SkipNode *update[MAX_LEVEL];  
    SkipNode *p, *q = NULL;  
    p = s->head;  
    int k = s->level;  
    //从最高层往下查找需要插入的位置  
    //填充update  
    for(int i=k-1; i >= 0; i--)
    {
        while((q=p->forward[i])&&(q->key<key))  
        {
            p=q;  
        }  
        update[i]=p;  
    }  
    //不能插入相同的key  
    if(q != NULL && q->key == key)  
    {
        return false;  
    }  
    //产生一个随机层数K  
    //新建一个待插入节点q  
    //一层一层插入  
    k=RandomLevel();  
    //更新跳表的level  
    if(k > (s->level))  
    {
        for(int i=s->level; i < k; i++)
        {
            update[i] = s->head;  
        }  
        s->level=k;  
    }  
    q = BuyNode(k,key,value);  
    //逐层更新节点的指针，和普通列表插入一样  
    for(int i=0;i<k;i++)  
    {
        q->forward[i]=update[i]->forward[i];  
        update[i]->forward[i]=q;  
    }  
    return true;  
}  
//搜索指定key的value  
int SearchValue(SkipList *s,int key)  
{
    SkipNode *p,*q=NULL;  
    p=s->head;  
    //从最高层开始搜  
    int k=s->level;  
    for(int i=k-1; i >= 0; i--){
        while((q=p->forward[i])&&(q->key<=key))  
        {
            if(q->key == key)  
            {
                return q->value;  
            }  
            p=q;  
        }  
    }  
    return NULL;  
}  
//删除指定的key  
bool RemoveValue(SkipList *s,int key)  
{
    SkipNode *update[MAX_LEVEL];  
    SkipNode *p,*q=NULL;  
    p=s->head;  
    //从最高层开始搜  
    int k=s->level;  
    for(int i=k-1; i >= 0; i--)
    {
        while((q=p->forward[i])&&(q->key<key))  
        {
            p=q;  
        }  
        update[i]=p;  
    }  
    if(q != NULL &&q->key==key)  
    {
        //逐层删除，和普通列表删除一样  
        for(int i=0; i<s->level; i++)
        {
            if(update[i]->forward[i]==q)
            {
                update[i]->forward[i]=q->forward[i];    
            }  
        }   
        Freenode(q);  
        //如果删除的是最大层的节点，那么需要重新维护跳表的  
        for(int i=s->level - 1; i >= 0; i--)
        {
            if(s->head->forward[i]==NULL)
            {
                s->level--;    
            }    
        }    
        return true;  
    }  
    else  
    {
        return false; 
    }
}  
void PrintSkipList(SkipList *s)//打印 
{
    //从最高层开始打印  
    SkipNode *p,*q=NULL;  
    //从最高层开始搜  
    int k = s->level;  
    for(int i=k-1; i >= 0; i--)  
    {
        p = s->head;  
        while(q = p->forward[i])  
        {
            printf("%d -> ",p->value);  
            p = q;  
        }  
        printf("\n");  
    }  
    printf("\n");  
}  
int main()  
{
    SkipList *s=CreateSkipList();  
    for(int i=1;i<=19;i++)  
    {
        InsertItem(s,i,i*2);  
    }  
    PrintSkipList(s);  
    //搜索  
    int i=SearchValue(s,4);  
    printf("i=%d\n",i);  
    //删除  
    bool b=RemoveValue(s,4);  
    if(b)  
    {
        printf("删除成功\n"); 
    }
    PrintSkipList(s);  
    return 0;  
}

在这里插入图片描述

Java代码实现

在这里插入图片描述

范围查找非常方便，是有序的双向链表实现的，比红黑树效率高。

package com.fixbug;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;
/**
 * 跳跃表的代码实现   java.util.concurrent Java并发包   ConcurrentSkipListSet ConcurrentSkipListMap
 * @param <T>
 */
class SkipList<T extends Comparable<T>>{
    //指向跳跃表最上面一层链表的头节点，相当于二分查找
    private HeadNode<T> head;
    /**
     * 跳跃表的初始化，初始只有一层链表
     */
    public SkipList() {
        this.head = new HeadNode<>(null, null, null, null, null, 1);
    }
    /**
     * 把key添加到跳跃表当中   [key, value]
     * @param key
     */
    public void put(T key){
        //1.在跳跃表中搜索key应该插入的位置
        Node<T> pre = this.head;//头节点
        Node<T> cur = pre.right;//最上层的首元素
        for(;;){
            if(cur != null){
                if(cur.data.compareTo(key) < 0){
    //当前节点比key小
                    pre = cur;//向后推进
                    cur = cur.right;
                    continue;//继续判断当前链表的右边节点，找第一个比key大的节点
                } else if(cur.data.compareTo(key) == 0) {
                    return;//不会重复插入key
                }
            }
            //已经是第一层链表了，那么key应该插入到pre节点的后面
            if(pre.down == null){
                break;
            }
            pre = pre.down;//pre走到下面一层链表
            cur = pre.right;//更新cur指向pre节点的下一个节点
        }
        //2.key应该插入到pre节点的后面。抛硬币决定key需要插入的层数k
        int level = getLevel();
        HeadNode<T> h = this.head;
        if(level > h.level){
     //key添加的层数太多了，最多只增加一层
            level = h.level + 1;
            //生成新的一层链表，链接到跳跃表当中
            h = new HeadNode<>(null, null, this.head, null, null, level);
            this.head.up = h;
            this.head = h;
        }
        //3.层数k <= 跳跃表的层数 : 直接插入   层数k > 跳跃表的层数 : 只增长一层
        Node<T>[] nodeArr = new Node[level];
        Node<T> index = null;
        //先链接up域
        for(int i=0; i < nodeArr.length; ++i){
            nodeArr[i] = index = new Node<>(key, index, null, null, null);
        }
        // 再链接down域
        for(int i=0; i < nodeArr.length-1; ++i){
            nodeArr[i].down = nodeArr[i+1];
        }
        // 插入key
        for(int i = nodeArr.length-1; i >= 0; --i){
            //下面四句代码，类似双向链表的插入操作
            nodeArr[i].right = pre.right;
            nodeArr[i].left = pre;
            pre.right = nodeArr[i];
            if(nodeArr[i].right != null){
                nodeArr[i].right.left = nodeArr[i];
            }
            if(0 == i){
    //所有层数的链表数据都已经添加完成
                break;
            }
            while(pre.up == null){
    //pre往当前链表的前边节点回退，找见第一个可以往上面链表走的节点
                pre = pre.left;
            }
            pre = pre.up;
        }
    }
    /**
     * 跳跃表的删除操作
     * @param key
     */
    public void remove(T key){
        //1. 找到待删除的节点，让cur指向
        Node<T> pre = this.head;
        Node<T> cur = pre.right;
        for(;;){
            if(cur != null){
                if(cur.data.compareTo(key) < 0){
                    pre = cur;
                    cur = cur.right;
                    continue;
                } else if(cur.data.compareTo(key) == 0){
                    break;
                }
            }
            if(pre.down == null){
                break;
            }
            pre = pre.down;
            cur = pre.right;
        }
        //2.删除cur指向的节点
        if(cur == null){
            return;
        }
        //3.开始删除cur指向的节点
        while (cur != null){
            cur.left.right = cur.right;
            if(cur.right != null){
                cur.right.left = cur.left;
            }
            cur = cur.down;
        }
        //4.删除完成后，从上往下检查，把空链表全部释放
        Node<T> h = this.head;
        while (h != null && h.down != null){
            if(h.right == null){
     // 表示当前链表是个空链表
                this.head = (HeadNode<T>) h.down;
                h = h.down;
            } else {
                break;
            }
        }
    }
    /**
     * 跳跃表的查询操作
     * @param key
     * @return
     */
    public boolean query(T key){
        Node<T> pre = this.head;
        Node<T> cur = pre.right;
        for(;;){
            if(cur != null){
                if(cur.data.compareTo(key) < 0){
                    pre = cur;
                    cur = cur.right;
                    continue;
                } else if(cur.data.compareTo(key) == 0){
                    return true;
                }
            }
            if(pre.down == null){
                break;
            }
            pre = pre.down;
            cur = pre.right;
        }
        return false;
    }
    /**
     * 打印每一层链表的内容
     */
    public void show(){
        System.out.println("跳跃表的层数:" + this.head.level);
        Node<T> h = this.head;
        while(h != null){
            Node<T> cur = h.right;
            while(cur != null){
                System.out.printf("%-5d", cur.data);
                cur = cur.right;
            }
            System.out.println();
            h = h.down;
        }
    }
    /**
     * 模拟抛硬币，决定key插入的层数
     * @return
     */
    private int getLevel() {
        int k = 1;
        while(Math.random() >= 0.5){
            k++;
        }
        return k;
    }
    /**
     * 跳跃表节点的类型
     * @param <T>
     */
    static class Node<T extends Comparable<T>>{
        T data;//任何类型都有可能
        Node<T> up;//4个方向
        Node<T> down;
        Node<T> left;
        Node<T> right;
        public Node(T data, Node<T> up, Node<T> down, Node<T> left, Node<T> right) {
            this.data = data;
            this.up = up;
            this.down = down;
            this.left = left;
            this.right = right;
        }
    }
    /**
     * 每一层链表，头节点的类型，用来额外记录层数
     * @param <T>
     */
    static class HeadNode<T extends Comparable<T>> extends Node<T>{
        int level;//跳跃表每一层链表的头节点记录当前链表所处的层数
        public HeadNode(T data, Node<T> up, Node<T> down, Node<T> left, Node<T> right, int level) {
            super(data, up, down, left, right);
            this.level = level;
        }
    }
}
/**
 * 跳跃表代码测试
 */
public class SkipListTest
{
    public static void main( String[] args ) {
        long begin, end;
//        begin = System.currentTimeMillis();
        SkipList<Integer> list = new SkipList<>();
        for (int i = 0; i < 10; i++) {
            list.put((int)(Math.random() * 100));
        }
        list.put(18);
        list.show();
        System.out.println(list.query(18));
        System.out.println();
        list.remove(18);
        list.show();
        System.out.println(list.query(18));
//        end = System.currentTimeMillis();
//        System.out.println("skiplist time:" + (end-begin) + "ms");
//        begin = System.currentTimeMillis();
//        ConcurrentSkipListSet<Integer> set = new ConcurrentSkipListSet<>();
//        for (int i = 0; i < 20000; i++) {
//            set.add((int)(Math.random() * 100));
//        }
//        end = System.currentTimeMillis();
//        System.out.println("ConcurrentSkipListSet time:" + (end-begin) + "ms");
    }
}