画画的 baby
2023-04-29 23:44 门头沟学院 后端工程师
关注
Q2:
我们都知道Redis里的跳表是一种平衡树的不错的替代数据结构，你可以讲一下跳表的结构，然后大概讲一下level中的前进指针的跨度是怎样生成的吧？
A:
跳表是使用类似于双向链表的结构，可以通过多个zskipListNode直接组成，也可以添加zSkipList表头后形成。首先就是同样的`header`、 `Tail`头尾指针（其中header指向的是一个表头），然后不一样的地方在于增加了`level`、`length`两个属性，一个是结点的个数，另外一个是最高的层数。然后结点的结构呢，也有几个属性（`score, object, level[], backward`）其中level数组中是不同级别，不同级别中分别对应不同的前进指针和跨度。
这里说的跨度就是前进指针的移动距离，它的生成规则也比较简单，假设最开始的时候，跳表是空的，这个时候新添加一个跳表节点，首先会随机生成一个1~32之间的数作为这个节点的层高度，然后从表头出发，用前进指针指向表尾，期间经过的节点进行连接，比如说有两个节点，都有L5，但是中间隔了两个点（高度均小于5），那么遍历后的结果就是第一个节点的第5层的前进指针的跨度是2.。跨度除了用来进行遍历，还可以用来**计算目标结点的排位**
查看原帖
点赞 评论
相关推荐
offer吸引力：我是不是撸
🦌昏了，28届都来了 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 什么是优秀的实习经历 #
8624次浏览 214人参与
# 实习简历求拷打 #
13322次浏览 162人参与
# 被上班搭子“传染”了哪些习惯 #
5708次浏览 99人参与
# 秋招被挂春招仍然能投的公司 #
6977次浏览 100人参与
# 工作后，你落下了哪些病根 #
13781次浏览 191人参与
# 外包能不能当跳板？ #
54125次浏览 256人参与
# mt对你说过最有启发的一句话 #
36818次浏览 442人参与
# 作业帮求职进展汇总 #
83315次浏览 547人参与
# 摸鱼被leader发现了怎么办 #
101924次浏览 647人参与
# 秋招特别不鸣谢 #
15951次浏览 181人参与
# 考研失败就一定是坏事吗？ #
201393次浏览 1376人参与
# 选实习，你更看重哪方面？ #
14388次浏览 220人参与
# 投格力的你，拿到offer了吗？ #
152829次浏览 817人参与
# 一起聊美团 #
307069次浏览 1760人参与
# 京东美团大战，你怎么看？ #
158153次浏览 861人参与
# 安克创新求职进展汇总 #
62382次浏览 541人参与
# 京东开奖 #
631575次浏览 3177人参与
# 第一次面试 #
1036580次浏览 13683人参与
# 今年秋招你收到了多少封邮件？ #
18093次浏览 220人参与
# 毕业论文进行时 #
20932次浏览 132人参与