跳跃表

跳跃列表（也称跳表）是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作须要O(logn)平均时间）。



基本上。跳跃列表是对有序的链表添加上附加的前进链接，添加是以随机化的方式进行的。所以在列表中的查找能够高速的跳过部分列表元素，因此得名。全部操作都以对数随机化的时间进行。

例如以下图所看到的。是一个即为简单的跳跃表。

传统意义的单链表是一个线性结构。向有序的链表中插入一个节点须要O(n)的时间。查找操作须要O(n)的时间。假设我们使用图中所看到的的跳跃表。就能够大大降低降低查找所需时间。

由于我们能够先通过每一个节点的最上层的指针先进行查找，这样子就能跳过大部分的节点。然后再缩减范围，对以下一层的指针进行查找，若仍未找到，缩小范围继续查找。

上面基本上就是跳跃表的思想。每个结点不单单仅仅包括指向下一个结点的指针。可能包括非常多个指向兴许结点的指针，这样就能够跳过一些不必要的结点，从而加快查找、删除等操作。对于一个链表内每一个结点包括多少个指向兴许元素的指针，这个过程是通过一个随机函数生成器得到。这样子就构成了一个跳跃表。

构造

由图不难理解跳跃表的原理，能够看出。跳跃表中的一个节点是有不同数目的后继指针的。

那么问题来了，这详细是怎样实现的？这些节点是怎样构造的？

【分析】

我们不可能为每一种后继指针数目的节点分配一种大小类型的节点，那我们就提取共性，看这些节点有何共通之处。

这些节点可看做由两部分构成：数据域、指针域。

数据域包含key-Value，指针域是后继指针的集合。

那怎样在节点中保存后继指针集合呢？用一个二级指针，分配节点的时候指向动态分配的后继指针数组。这个方法似乎可行，但问题在于我们的节点也是动态分配的，这种话，在释放节点的时候还须要先释放节点中动态分配的数组。

释放操作比較繁琐。

灵光一闪！之前本博客中介绍了一种称为“零数组”的技术，或许能够帮到我们。（详情点击）

零数组是gcc的扩展特性。只是在C99中，能够用类似的声明来实现。

struct Node{

    KeyType      key;

    ValueType    value;

    struct Node* forward[0]; //C99这样玩：struct Node* forward[]

}; 

动态分配节点能够这样写：

(struct Node *)malloc(sizeof(struct Node) + length*sizeof(struct Node*)); //length是后继指针数组的长度

这种话。我们能够像訪问数组那样訪问forward。且释放的时候仅仅释放动态分配的节点就可以。

（forward仅仅是起一个标记的作用）



当然，另一种更通用的技巧，和零数组的思想类似

struct Node{

    KeyType      key;

    ValueType    value;

    struct Node* forward[1];

}; 

我们在这里用符合不论什么C标准的定义，定义一个1个元素的数组，用来占位。然后动态分配一大块空间。我们通过对这个1元素数组的越界訪问，訪问到其后分配的空间。



我们能够定义一个函数专门负责分配不同大小的节点：

void NewNodeWithLevel(const int& level, struct Node& node){

    //新结点空间大小

    int total_size = sizeof(struct Node) + level*sizeof(struct Node*);

    //申请空间

    node = (struct Node)malloc(total_size);

    assert(node != NULL);

}

查找

我们以查找19为例。图解查找过程。

先从最上层的跳跃区间大的层開始查找。从头结点開始。首先和23进行比較，小于23，（此时查找指针在图中“1”位置处）。查找指针到下一层继续查找。

然后和9进行推断，大于9，查找指针再往前走一步和23比較，小于23。（此时查找指针在图中“2”位置处） 此时这个值肯定在9结点和23结点之间。查找指针到下一层继续查找。

然后和13进行推断。大于13，查找指针再往前走一步和23比較，小于23，（此时查找指针在图中“3”位置处）此时这个值肯定在13结点和23结点之间。查找指针到下一层继续查找。

此时，我们和19进行推断。找到了。

好了，看完这个样例，你一定对跳转表的查找操作有了清晰的理解。至于代码实现也不难了。

插入

插入和删除的实现很像对应的链表操作。除了"高层"元素必须在多个链表中插入或删除之外。

插入包括例如以下几个操作：1、查找到须要插入的位置 2、申请新的结点 3、调整指针。

由于找到插入点之后，新生成节点，新节点按概率出如今每层上，故须要保存全部层的后继指针。我们用一个暂时数组保存全部层的插入点处的后继指针。

在寻找插入点的时候就能够完毕赋值。

for(i = list->level; i >= 0; --i){

   while(x->forward[i]->key < key){

       x = x->forward[i];

   }

   update[i] = x;

} 

删除

删除操作类似于插入操作，包括例如以下3步：1、查找到须要删除的结点 2、删除结点  3、调整指针

相同。须要一个暂时数组保存每层的指针域。原理和插入类似。不再赘述。

【关于释放跳转表】

释放表的操作比較简单，仅仅要像单链表一样释放表就可以。

【跳跃表使用概率均衡技术而不是使用强制性均衡，因此，对于插入和删除结点比传统上的平衡树算法更为简洁高效。

】

分析

跳跃列表是按层建造的。底层是一个普通的有序链表。每一个更高层都充当以下列表的“高速跑道”，这里在层 i 中的元素按某个固定的概率 p (通常为0.5或0.25)出如今层 i+1 中。平均起来。每一个元素都在 1/(1-p) 个列表中出现，而最高层的元素（一般是在跳跃列表前端的一个特殊的头元素）在 O(log1/p n) 个列表中出现。

要查找一个目标元素。起步于头元素和顶层列表，并沿着每一个链表搜索。直到到达小于或着等于目标的最后一个元素。

在每一个链表中预期的查找步数显而易见是 1/p。所以查找的整体代价是 O((log1/p n) / p)，当p 是常数时是 O(log n)。通过选择不同 p 值。就能够在查找代价和存储代价之间作出权衡。



跳跃列表不像某些传统平衡树数据结构那样提供绝对的最坏情况性能保证，由于用来建造跳跃列表的扔硬币方法总有可能（虽然概率非常小）生成一个糟糕的不平衡结构。可是在实际中它工作的非常好。随机化平衡方案比在平衡二叉查找树中用的确定性平衡方案easy实现。跳跃列表在并行计算中也非常实用，这里的插入能够在跳跃列表不同的部分并行的进行，而不用全局的数据结构又一次平衡。



【性能】

空间复杂度：O(n)

查找、插入和删除操作的时间复杂度都为: O(logn)

随机跳跃表表现性能也非常不错，节省了大量复杂的调节平衡树的代码。其效率与红黑树、伸展树等这些平衡树能够说相差不大。

但跳跃表还在并发环境下有优势。在并发环境下。假设要更新数据，跳跃表须要更新的部分就比較少，锁的东西也就比較少。所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。

性能也就不如前者了。

应用

了解过Redis的都知道，Redis有一个非常实用的数据结构：SortSet，基于它，我们能够非常轻松的实现一个Top N的应用。

这个SortSet底层就是利用跳表实现的。

跳表也被用在leveldb中。在一些词典结构中中也经经常使用跳表来实现字典，加快查找速度。

总结

【參考】

关于代码參考这里：http://blog.csdn.net/ict2014/article/details/17394259