跳表是一种数据结构。它允许快速查询一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)。
线性表这种数据有两种具体实现, 数组和链表。具体的内容之前的文章里也有说过，可以翻翻看哇~。在这里两种数据结构中，数组的优点是查找速度快,而链表的优点是增删的效率高，这也是我们常说的。其实，非也。
数组是一种内存连续的数据结构,其优点是可以通过首地址+N*(sizeOf(Node)) 来快速获取指定位置上的元素.假如我们不知道指定元素的位置呢?
链表是一种非内存连续的数据，其优点是通过改变指针地址来快速增减元素。很明显的问题，你首先要知道你要增加/删除的目标元素是哪个! 所以会浪费 O(n) 的查询时间。
要论效率, 那就要说平衡树(AVL)了。增删查的效率都是 O(logN)。 但是这种数据结构, 原理比较复杂,实现起来那不是比较复杂了，那是相当复杂。增删操作，都需要其依靠平衡操作引发子树的调整。
跳表(skip list) 全称 跳跃链表。 是一种类链表的数据结构。
跳表的性能和平衡树的性能是一样的，在插入，删除，搜索的时间复杂度都是 O(n), 是一种利用空间换时间的数据结构。
跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它。
这里，先给大家看一个可能的跳表结构
现在我要告诉你，上面的跳表是由下面的跳表经过层层优化得来的。
下面我们针对上面的跳表结构来分析一下。
刚才说过了，链表增删性能罪魁祸首就是查找操作! 对于查找操作，效率最高的莫过于二分查找了。但是对于第一个有序链表中是无法使用二分查找的。但是呢，我们可以随机抽选中其中的几个元素，组成一个新的链表。就像下面这样。
假设我们要找5这个元素,在单独的有序链表中，我们必须从头结点依次遍历到 5 这个节点。路径为1->2->3->4->5,下图中黄色线路径。,现在，我们只需要从 1->2->4->5.下图中紫色线路径。既然我们可以原来的链表抽象出一个新的链表, 那我们还可以从新的链表中再抽象出一个新的链表。这样的话，就直接可以 1->4->5,就可以查到一个我们的目标节点了。
如果你看到这里，我要告诉你一个重要的概念了。
层：就是我们假设的抽象出来的新链表。
可能你很好奇, 层我们应该怎么存储呢? 很简单啊！
以后我们每个链表的元素是怎么定义的??
typedef struct NODE {
T data;
Node *next;
} node;
我们只需要将 指向下一个元素的指针改成一个指针数组就可以了！
typedef struct NODE {
T data;
/// 指向后继元素的指针数组
struct Node *next[i];
} node;
了解了怎么存储之后，那怎样确定某个节点有几层呢? 这里我告诉你吧，随机的！怎么随机的呢? 就是通过随机数来确定的，也就是我们常说的 抛硬币的形式。 比如下面的这段代码.
/**
* 生成一个随机数
* @return 一个随机数
*/
int random_level() {
int level = 1;
while (rand() % 2) {
level++;
}
level = (level < MAX_LEVEL) ? level : MAX_LEVEL;
return level;
}
那我们就尝试着实现一个跳表。
/// 节点
NODE {
T data,
/// 指向下一个节点的数组，从1开始。
/// 数组中的每个元素对应该层的下一个节点
/// next[1],是第一层的下一个节点的地址。
/// next[2] 是第二层的下一个节点的地址。
NODE []next;
}
/// 跳表
SKIP_LIST{
NODE head;
/// 该跳表的层数
int level;
}
主要逻辑是: 从高层开始查找直到找到等于指定元素的节点E 或者第一个大于指定元素的节点G。如果是节点E，那么直接返回就好了。如果是G节点, 那么就以G节点的前一个节点L,在下一层进行查找，重复上面的逻辑，直到找到节点E，或者到达跳表的结尾。
比如下图中查找 5 的过程为:
如下面的伪代码。
search() {
/// i 表示层数，从最高层开始查找 。
for (; i >= 0; i--) {
while ((q = p->next[i]) && q->k < k) {
p = q;
}
if (q && k == q->data) {
return &(q->data);
}
}
}
上面分析可以得出来，跳表是一个多层的有序链表。所以我们对于每一层都像操作普通链表一样就可以了。就像下面的这样:
insert () {
// 找到要插入的节点位置。
// level是本跳表的层数
for (i = level-1; i >= 0; i--) {
///遍历该层小于指定值的前一个元素
while ((q = p->next[i]) && q->k < k) {
p = q;
}
/// 新节点的前一个节点的层指针。
update[i] = p;
}
// 随机生成该节点的层数,如果生成的层数大于当前层，需要更新跳表中记录的level值。
new_level = rand_level();
if(new_level > level) {
level = new_level;
}
// 生成新的节点，并针对每一层执行普通链表的插入操作。
new_node = create_new_node();
for (i = level - 1; i >= 0; i--) {
/// 下面两行代码就是普通连接的增加方法。
/// 新节点的前一个节点的第i层的节点。
new_node->next[i] = update[i]->next[i];
update[i]->next[i] = q;
}
}
主要逻辑是该节点的每一层都要删除.
即对每一层,都要 要删除节点的上一个节点指向要删除节点的下一个节点。
del() {
/// 找到要删除的节点
for (; i >= 0; --i) {
while ((q = p->next[i]) && q->k < k) {
p = q;
}
update[i] = p;
}
}
跳表实现Java
因为跳表的时间复杂度和跳表的层数以及该层上的节点数和节点分布的位置有关，而这些因素都是随机的。 此中涉及了很多复杂的概率统计学知识。所以我就摘自维基百科中的说明，如下:
如果看的不是很清晰，也可以这么想：
如果每两个节点抽出一个节点作为上一级索引的节点，那第一级索引的节点个数大约就是 n/2 ,第二级索引是 n/4, 第三级就是 n/8。 也就是说 第 k 级索引节点个数是 n/(2^k);
假设,我们有 h 层, 最高层索引有2个节点,那么， 就是 n/(2^k)=2, 那么 ，这个链表的高度就是log2N . 如果每一层要遍历 m 个节点,那么在跳表中查询一个数据的时间复杂度就是O(m*logN).
由于随机分布的存在，我们可以把m当做一个常数, 所以, 时间复杂度大致可以认为是 O(logN)
根据整体代码实现来看, 我们使用了链表的形式来实现. 其中，next 改成了数组用来存储下一节点的指针,并没有真正的存储对象,. 也就是说,其实我们并没有使用很多的内存, 当然，比一般的链表还是要多一些的。对于我们存储的对象来讲，用于存储指针的内存直接就可以忽略了。时间复杂度为 O(N+m),其中 N>>m(N远远大于m).
跳表 与平衡树、哈希表的比较
There are a few reasons:
1.They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
2.A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
3.They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
本文由mdnice多平台发布