跳跃链表的基本概念初识跳表跳跃列表是一种数据结构,不吹了,快开始品尝这美味的知识吧

跳转链表及其应用是非常热门的问题,深入了解其中的奥秘是非常有益的。让我们停止吹嘘,开始品尝这美味的知识吧!

跳表的基本概念

了解跳过表

跳过列表是一种数据结构。它允许快速查询有序连续元素的链表。跳过列表的平均查找和插入时间复杂度均为 O(log n),优于普通队列的 O(n)。

跳转表是威廉普发明的,发明人对跳转表的评价:跳转表是一种数据结构,在很多应用中可以替代平衡树作为实现方法。

跳跃列表算法具有与平衡树相同的渐近预期时间界限,并且更简单、更快并且使用更少的空间。

这种数据结构由 William Pugh 发明,并首次出现在他 1990 年的论文“Skip Lists: A Probabilistic Alternative to Balanced Trees”中。

大白在谷歌的skip table上找到了一篇作者的论文。如果有兴趣,强烈推荐下载阅读:

看一下本文的摘要部分:

我们从中得到的信息是:skip table在动态搜索过程中使用了非严格的平衡机制,使得插入和删除更加方便快捷。这种非严格的平衡是基于概率的,而不是平衡树。严格平衡。

说到非严格平衡,首先想到的就是红黑树RbTree,它也是使用非严格平衡来避免像AVL那样调整树结构。我不会在这里展开红黑树。看来skip table也是类似的方式。但它是基于概率的。

动态查找数据结构

所谓动态搜索,就是在搜索过程中进行元素的删除和插入,这对搜索的数据结构提出了一定的挑战,因为每次删除和插入都要对数据结构进行调整以保持顺序。

可用于查找的数据结构示例包括:

下面我们来分析一下各种数据结构在处理动态搜索方面的优缺点吧!

数组结构

数组结构简单,内存连续。可以实现二分查找等基于下标的运算。一直认为数组的杀手锏是下标,连续的内存也带来了问题。

插入和删除时面临整体调整,就像在火车站排队买票一样,线头向前一步,塞子后面的人向后移动。这种整体移动操作在数组结构中性能损失很高,在数据量很大时对连续内存的要求很高。当然,这在大内存机器上可能不是问题。

插入6删除5时数组元素的移动如图:

链表结构

链表的结构也比较简单,但是它不需要内存是连续的,也没有下标来加速非连续性。但是,链表在进行删除和插入时,只影响到插入和删除点前后的元素,影响很小。

但是每次找到一个元素,我都需要遍历。即使我知道一个元素大概在哪里,我也只能一步一步地走过它。如果你看到有优化的空间,那你就很厉害了。说也许几年前,跳过手表是你的发明。

删除元素5,插入元素49时的处理如图:

平衡树

平衡树也是处理动态搜索问题的好手。树一般是基于链表实现的,但是树的节点并不是链表的简单线性关系。会有兄弟姐妹、父亲等节点,并且每一层都有层数限制。,你可以看到这棵树实际上是相当复杂的。

节点需要存储很多信息,每个指针都来回指向,复杂的结构增加了调整平衡的难度,不同情况下左右旋转,所以有这样的工程版AVL就像红黑树,但在实际场景中,中国可能不需要这些兄弟姐妹和父亲,这有点像杀鸡杀猪。

红黑树的节点结构定义:

#define COLOR_RED  0x0
#define COLOR_BLACK 0x1

typedef struct RBNode{
int key;
unsigned char color;
struct RBNode *left;
struct RBNode *right;
struct RBNode *parent;
}rb_node_t, *rb_tree_t;

另外,在调整红黑树属性的过程中,插入分为3种情况,删除分为4种情况。仍然很难理解。除非你穿红衬衫黑裤子疯狂暗示面试官,否则被问到的概率还是很高的。没那么大。

三种结构比较

从上面的对比可以看出,数组并没有很好的满足要求分析跳跃列表的时间复杂度,链表在搜索过程中比较笨拙,平衡树有点复杂。我该怎么办?

跳台原型

以上三类结构存在一些问题,所以如果需要变换,可以看到数组和平衡树的一些特性决定了它们不容易变换(数组内存连续性、平衡树节点多指针和层次关系),相反,链表最有可能被转换和优化。

有序列表中的插入和删除相对简单。搜索时不能依赖下标,只能遍历。但是,您知道到达目的地需要走两步,但一次只能走一步。这是痛点。

该图演示了 O(n) 遍历元素 35 并跳过搜索元素 35 的过程:

似乎看到了曙光,那么如何实现跳跃呢?

那就对了!给链表添加索引分析跳跃列表的时间复杂度,让索引告诉我们接下来要跳转到哪里。

看到这里,又让我想起了经典的中间层理论。如果遇到问题,试试加个中间层,说不定就完美解决了。

跳转链表的实现原理

前面说过,可以通过在普通链表中添加索引来解决,但是具体怎么做,有什么难点呢?一步一步分析。

在项目中,跳表索引层数以及节点是否作为索引节点都是非常重要的属性。我稍后会详细讨论。现在我们来看一个简单的场景来说明索引带来的便利。

简单索引

选择每隔一个节点作为索引节点,索引是一层。这种形式虽然在项目中比较规范,但足以说明指标带来的加速。

可以在链表中添加一层指向偶数节点的指针,指向下一个偶数节点,如图:

搜索过程:

添加搜索值为55的节点时,先向上层搜索,从16跳到38,在38的下一跳会到达72,所以继续下一层类似的搜索,找到55。

多级索引

在基于偶数节点增加索引且只有两层的情况下,最高层的节点数为n/2,整体搜索复杂度降低到O(n/2),不要小看这 1/2 的系数,看这里,你会想要将索引层数增加到 k,那么复杂度就会将索引降低到 O(n/2^k)。

索引层的数量不会无休止地增加。它取决于层索引中的节点数。如果该层的索引中的节点数等于2,那么再增加一层是没有意义的。画个图看看:

这很容易理解。如果层中只有一个索引节点,比如4层索引的节点16,则只能向下遍历16,不能向后跳转到第4层的其他节点。因此,当该层的索引节点所在的点数等于2时,就达到了最高的索引级别。在分析跳过列表的复杂性时,此约束很重要。

索引级别和 inode 密度

跳表的复杂度与索引层数和索引节点的稀疏度有很大关系。

从上面我们也可以看出,索引层数等于索引节点数之比。如果跳过链表中的索引节点数量较少,则将接近退化为普通链表。这种情况下,当数据量很大的时候非常明显,看图(蓝色部分表示节点多):

从图中可以看出,虽然有索引层,但是索引节点的数量相对于总数据来说是比较少的。在这种情况下,search 35 与没有索引的情况相比优势并不明显。

因此,跳表的效率与索引层数和索引节点密度密切相关。当然,索引节点太多意味着没有索引。

太少的 inode 与太多的 inode 一样低效。

复杂性分析

从前面的分析可以看出,跳表的复杂度与索引层数m和索引节点间隙d直接相关。索引节点间隙理解为索引节点被若干节点隔开的出现,反映了对应层的索引节点。的稀疏度,当没有索引节点时,只能遍历,不能跳转。

如何确定最高指标级别m?

如果一个链表有n个节点,如果每两个节点取出来创建一个索引,那么一级索引的节点数为n/2,二级索引的节点数为n/4 ,以此类推 第 m 个索引中的节点数为 n/(2^m)。前面说过,最高层的节点数是2,所以有一个关系:

算上最底层的原始链表,整个跳转链表的高度为h=logn(基数为2),每层要遍历的节点数为d,那么整体的复杂度过程是:O(d*logn)。

d表示层间节点的稀疏程度,即每2个节点选择索引节点,或者每3个节点选择索引节点,每4个节点选择索引节点……

最密集的情况,d=2,借用知乎一个大佬的文章的图:

但是,索引节点的密度也意味着存储空间的增加。与普通链表相比,跳跃表是一种典型的以空间换时间的数据结构,实现了AVL O(logn)的复杂度。

跳过表的空间存储

以d=2的最密集情况为例,计算skip list中索引节点的总数:2+4+8+…n/8+n/4+n/2=n-2

由比例序列求和公式得到的d=2的跳转表的额外空间为O(n-2).

跳过表的插入和删除

项目中的skip table并没有严格要求索引层节点数遵循2:1的关系,因为这个要求会导致在插入和删除数据时进行调整,代价高昂。

跳过表的每个插入节点在插入时都被选为索引节点。如果是索引节点,层数会随机选择。整个过程是基于概率的,但是在数据量很大的情况下可以很好的使用。解决索引层数和节点数之间的权衡。

下面我们来看看插入和删除的基本操作流程吧!

插入跳转列表元素 17:

链表的插入和删除是结合查找过程完成的。贴一张William Pugh在论文中给出的skip list中插入元素17的过程图(暂时忽略节点17是否作为索引节点和索引层数,后面会详细解释):

跳过列表元素 1 删除:

与普通链表相比,跳过列表元素的删除增加了索引层的判断。如果节点是非索引节点,则正常处理。如果节点是索引节点,则需要处理索引层节点。

跳过列表的应用

一般来说,讨论搜索问题首先想到的就是平衡树和哈希表,但是跳表的数据结构也很犀利,其性能和实现复杂度与红色不相上下-黑树,甚至某些场景都是由于红黑树。1990年发明,目前广泛应用于各种场景,包括Redis、LevelDB等数据存储引擎,后面会详细介绍。

跳表在Redis中的应用

ZSet 结构包含字典和跳过表。跳过表按分数从小到大存储所有集合元素。字典保存从成员到分数的映射。这两个结构共享相同的 member 元素并通过指针进行评分,因此不会浪费额外的内存。

typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;

ZSet 中的字典和跳过表布局:

ZSet中skip table的实现细节

随机层的实现原理

跳过表是一种概率数据结构,元素的插入层数是随机分配的。Willam Pugh在论文中描述其计算过程如下:指定节点的最大层数MaxLevel,指定概率p,默认层数lvl为1

生成一个从 0 到 1 的随机数 r,如果 r

重复步骤 2,直到生成的 r > p,其中 lvl 是要插入的层数。

论文中生成随机层的伪代码:

Redis中跳转表的实现基本遵循这个思路,但是有细微的差别。看一下Redis的随机源代码src/z_set.c关于跳转表层数:

/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level}

redis.h 中定义了两个宏:

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */

您可以在以下位置看到时间:

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)

第一次看到这个公式时,我有点惊讶,因为它涉及到位运算。我要研究一下Antirez为什么要用位运算来写成这样?

最初的猜测是random()返回的是一个浮点数[0-1],于是我在网上找到了一个浮点数转二进制的工具,输入0.5查看结果:

可以看出0.5的32位十六进制转换结果为0x3f000000。如果与 0xFFFF 的 AND 运算结果为 0,则与预期不符。

在我的印象中,C语言的数学库好像没有直接随机函数,所以去Redis源码找,于是下载了3.2版本的代码,没找到random() 的实现,但我找到了。其他几个地方的应用:

看到这里的取模运算,才发现random()是[0-1]的浮点数,但是现在好像是uint32,所以Antirez的公式好理解。

ZSKIPLIST_P*0xFFFF

由于 ZSKIPLIST_P=0.25,相当于将 0xFFFF 右移 2 位为 0x3FFF。假设random()比较均匀,在清除0xFFFF的高16位后,低16位的值落在0x0000-0xFFFF之间,这个同时为真的概率只有1/4,而且更一般地说,为真的概率为 1/ZSKIPLIST_P。

随机层数的实现并不统一。重要的是随机数的生成。LevelDB中跳转表层数的生成代码如下:

template 
int SkipList::randomLevel() {

static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxLevel);
return height;
}

uint32_t Next( uint32_t& seed) {
seed = seed & 0x7fffffffu;

if (seed == 0 || seed == 2147483647L) {
seed = 1;
}
static const uint32_t M = 2147483647L;
static const uint64_t A = 16807;
uint64_t product = seed * A;
seed = static_cast((product >> 31) + (product & M));
if (seed > M) {
seed -= M;
}
return seed;
}

可以看出leveldb使用随机数和kBranching取模。如果值为 0,则添加一个图层。虽然不使用浮点数,但也实现了概率平衡。

跳过列表节点的平均层数

我们可以很容易地看到,节点层数越多,发生的概率越低。无论如何,层数总是满足幂律。数字越大,发生的概率越低。

如果某事发生的频率及其属性之一具有幂关系,则频率可以称为幂律。

幂律的表现是少数事件的发生频率占了发生频率的大部分,而其余事件的大部分仅占整体发生频率的一小部分。

应用于跳表随机层的幂律意味着大部分节点层是黄色部分,只有少数是绿色部分,概率很低。

定量分析如下:

节点层数正好等于K的概率为p^(k-1)(1-p)

所以,如果我们求平均节点层数,那么就变成了求概率分布的期望问题,魂画师大白又上线了:

表中P为概率,V为对应值,给出了所有可能的值和概率,所以可以计算出这个概率分布的期望值。

方括号里的公式其实就是一年级的比例顺序。常用的技术是位错减法和加法。由此可以看出,节点层数的期望值与1-p成反比。

对于 Redis,当 p=0.25 时,预期的节点层数为 1.33。

Redis源码中,有详细的插入删除调整跳表的过程。本文将不展开。代码不难理解。它是用纯 C 编写的,没有太多特殊效果。您可以放心阅读。

概括

本文主要介绍跳表的基本概念和简单原理,以及索引节点级别、时空复杂度等相关部分,不涉及概率平衡和工程实现,取Redis中底层数据结构zset作为一个典型的应用。让我们展开看看跳跃列表的实际应用。

需要注意的是,跳转链表的原理、应用和实现细节也是面试中的热门话题,值得花时间去学习和掌握。

© 版权声明
THE END
喜欢就支持一下吧
点赞0
分享
评论 抢沙发

请登录后发表评论