简介

跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到。

它采用随机技术决定链表中哪些节点应增加向前指针以及在该节点中应增加多少个指针。跳表结构的头节点需有足够的指针域，以满足可能构造最大级数的需要，而尾节点不需要指针域。

采用这种随机技术，跳表中的搜索、插入、删除操作的时间均为O(logn)，然而，最坏情况下时间复杂性却变成O(n)。相比之下，在一个有序数组或链表中进行插入/删除操作的时间为O(n)，最坏情况下为O(n)。

原理

数据结构模型

跳表的原理非常简单，跳表其实就是一种可以进行二分查找的有序链表。跳表的数据结构模型如图:

可以看到，跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。

理想情况

在一个使用有序链表描述的具有n个元素的字典中进行搜索，至多需进行n次比较。如果在链中部节点加一个指针，则比较次数可以减少到n/2+1。搜索时，首先将欲搜索元素与中间元素进行比较。如果欲搜索的元素较小，则仅需搜索链表的左半部分，否则，只要在链表右半部分进行比较即可。

实例

有序链表的快速搜索

图中c所示的结构为跳表（skiplist）。在该结构中有一组有层次的链。0级链是包含所有元素的有序链表，1级链是0级链的一个子集。i级链所包含的元素是i-1级链的子集。图c中，i级链上所有的元素均在i-1级链上。

如图的有序链表中有七个元素。该链表有一个头节点和一个尾节点。节点中的数是该节点的值。对该链表的搜索可能要进行七次比较。可以采用图b中的办法，把最坏情况下的比较次数减少为四次。搜索一个元素时，首先将它与中间元素进行比较，然后根据得到的结果，或者与链的左半部比较或者与右半部比较。例如如果要找值为26的元素，只需查找40左边的元素。如果要查找值为75的元素，那么只对40以后的元素进行搜索即可。

也可以向图c中一样，分别在链表左半部分和右半部分的中间节点再增加一个指针，以便进一步减少最坏情况下的搜索比较次数。在该图中有三条链。0级链就是图a中的初始链，包括了所有七个元素。一级链包括第二，六个元素，而2级链只包括第四个元素。为了寻找值为30的元素，首先与中间元素比较。在2级链中寻找元素所需要的时间为(1)。由于30<40，因此要搜索该链左半部分的中间元素。采用1级链进行搜索所花费的时间为(1)。又因为30>24，故需在0级链中继续进行查找，把该元素与链中下一个元素进行比较。

考察另一个例子。设要查找的元素值为77。首先与40比较，70>40，则在1级链中与75比较。由于77>75，因此在0级链中与75后面的80比较。这时可以得知77不在此字典中。采用图c中的3级链结构，对所有的搜索至多需三次比较。3级链结构允许在有序链表中进行折半搜索。

通常0级链包括n个元素，1级链包括n/2个元素，2级链包括n/4个元素，而每2i个元素有一个i级链指针。当且仅当一个元素在0～i级链上，但不在i+1级（若该链存在）链上时，我们就说该元素是i级链元素。在图c中，40是2级链上唯一的元素而75是1级链元素。20、30、60、80是0级链元素。

级的分配

在级基本的分配过程中，可以观察到，在一般跳表结构中，i-1级链中的元素属于i级链的概率为p。假设有一随机数产生器所产生的数在0到RANDMAX间。则下一次所产生的随机数小于等于CutOff=p*RANDMAX的概率为p。因此，若下一随机数小于等于CutOff，则新元素应在1级链上。现在继续确定新元素是否在2级链上，这由下一个随机数来决定。若新的随机数小于等于CutOff，则该元素也属于2级链。重复这个过程，直到得到一随机数大于CutOff为止。故可以用下面的代码为要插入的元素分配级。