FWQ
深入理解跳表及其在Redis中的应用
深入理解跳表及其在Redis中的应用 收藏 本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的,希望这篇《深入理解跳表及其在Redis中的应用》对你有很大帮助!欢迎收藏,分享给更多的需要的朋友学习~ 前言 跳表可以达到和红黑树一样的时间复杂度 O(logN),且实现简单,Redis 中的有序集合对象的底层数据结构就使用了跳表。其作者威廉·普评价:跳跃链表是在很多应用中有可能替代平衡树的一种数据结构。本篇文章将对跳表的实现及在Redis中的应用进行学习。 一. 跳表的基础概念 跳表,即跳跃链表(Skip List),是基于并联的链表数据结构,操作效率可以达到O(logN),对并发友好,跳表的示意图如下所示。 跳表的特点,可以概括如下。 •跳表是多层(level)链表结构; •跳表中的每一层都是一个有序链表,并且按照元素升序(默认)排列; •跳表中的元素会在哪一层出现是随机决定的,但是只要元素出现在了第 k 层,那么 k 层以下的链表也会出现这个元素; •跳表的底层的链表包含所有元素; •跳表头节点和尾节点不存储元素,且头节点和尾节点的层数就是跳表的最大层数; •跳表中的节点包含两个指针,一个指针指向同层链表的后一节点,一个指针指向下层链表的同元素节点。 以上图中的跳表为例,如果要查找元素 71,那么查找流程如下图所示。 从顶层链表的头节点开始查找,查找到元素71的节点时,一共遍历了4个节点,但是如果按照传统链表的方式(即从跳表的底层链表的头节点开始向后查找),那么就需要遍历7个节点,所以跳表以空间换时间,缩短了操作跳表所需要花费的时间。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。这种数据结构是由William Pugh(音译为威廉·普)发明的,最早出现于他在1990年发表的论文《Skip Lists: A…