本文共 4298 字，大约阅读时间需要 14 分钟。

前言

正如标题所诉，这算是一个比较常见的面试题了。小伙伴们在回答这个问题时，很多时候都会说单线程、基于内存的存储或者通过内部维护的字典可以使我们读取数据在O(1)的复杂度。

其实，还可以进行拓展。譬如提一下redis的单线程并非真正意义上的单线程，此时，如果你对IO多路复用了然于心，则接下来是show time！又或者你可以提一下redis为了达到快的目的用了哪些数据结构（这里不是指redis提供的操作类型，如字符串、哈希、列表这些，而是其内部构造使用到的一些数据结构，例如之前文章写过的SDS或者本篇文章计划说说的跳跃表）。 如果能回答出上述这些，比起先前千篇一律的回答，更能吸引住面试官。

何为跳跃表

本篇文章想说说redis中用到的跳跃表的数据结构，而在开始之前想阐述一波何为跳跃表。

跳跃表的本质还是链表+多级索引的结构，通过在一个有序链表上建立多级索引，使其查找时能够类似二分查找那样，减少比较的次数。

以依次插入50、7、25为例子，我们可以得到如下的一个流程图：

• 初始化一个层数为1的节点
• 插入50时，先通过一个函数生成一个随机数表示50占据的层数，即2。从顶层开始遍历，由于下一个节点为null，直接插入。
• 比较层数，因为新节点有两层，那么我们需要将头节点的第二层指向新节点。并把当前层数更新为2。
• 紧接着，插入7，同样通过一个函数生成一个随机数表示7占据的层数，这里为1。
• 从顶层开始遍历，由于头部节点顶层指向50，7和50比较，可以得出7要插入的位置在头部到50这个位置，此时我们取得头部节点。
• 由于从顶层位置开始找其，此时层数为第二层，而7这个节点只有一层，我们以取得的头部为出发点，从头部的第一层开始找起。
• 由于第一层的头部节点指向50，7和50比较，再次得出7要插入的位置在头部到50这个位置。
• 此时，比较7的层数和头部位置所在的层数（都是第一层），建立关联，将7和头部位置第一曾做关联，然后7的第一层指向50的第一层。
• 由于7只有一层，遍历结束。
• 同理，插入25，不过这里插入25后，由于25的节点有三层，比当前的最大层数2大，所以记得要更新当前最大层数。

根据以上流程，得到跳表添加的流程：

public void add(int num) {           // 随机生成层数        int level = random();        // 构造出一个新的节点        Node newNode = new Node(num, level);        // 保存一份副本, 用于遍历, 不会打乱原来的结构        Node addNode = head;        // 从最顶层开始遍历        for (int i = currentLevel-1; i >= 0 ; i--) {               // 找到一个节点, 该节点的下一个节点比当前节点大            Node target = find(num, i, addNode);            // i>level 表示此时的层数比新节点的层数高, 例如例子中, 插入5的流程,            // 需要继续往下寻找            if (i <= level) {                   if (addNode.next[i] == null) {                       addNode.next[i] = newNode;                } else {                       Node temp = target.next[i];                    target.next[i] = newNode;                    newNode.next[i] = temp;                }            }        }        if (level > currentLevel) {               for (int i = currentLevel; i < level; i++) {                   head.next[i] = newNode;            }            currentLevel = level;        }    }

关于random，随机生成层数的方法，redis算是给我们提供了经典之作，不用使我们刻意去计算出一个层数：

private int random() {           int initValue = 1;        while (Math.random() < FACTOR && initValue < currentLevel) {               initValue++;        }        return initValue;    }

通过一个随机函数小于一个因子（猜猜redis取得啥值）的条件和取得的层数小于当前层数的条件来获取随机层数。

为什么取得的层数小于当前层数？那时防止add方法里面，我们重新链接头部节点和下一个节点时，数组越界，即如下这段代码。

if (level > currentLevel) {               for (int i = currentLevel; i < level; i++) {                   head.next[i] = newNode;            }            currentLevel = level;        }

关于find方法就更加简单了，熟悉链表的同学对下面这段代码估计刻苦铭心：即找到一个节点, 该节点的下一个节点比当前节点大

private Node find(int num, int index, Node tempNode) {           while (tempNode.next[index] != null && tempNode.next[index].value < num) {               tempNode = tempNode.next[index];        }        return tempNode;    }

关于跳表在redis中的运用

参考《redis设计与实践》一书，跳表在redis中的运用有两个地方，一个是有序集合的实现之一，另一个则是用于集群节点。

• 下面是redis关于跳表在有序集合运用，redis 5.0版本，源码service.h和t_zet.c部分：
• 可以看我们上面代码中，用于生成随机层数的因子在这里则是ZSKIPLIST_P =0.25。

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 *//*定义一个节点*//* ZSETs use a specialized version of Skiplists */typedef struct zskiplistNode {       sds ele;    double score;    struct zskiplistNode *backward;    struct zskiplistLevel {           struct zskiplistNode *forward;        unsigned long span;    } level[];} zskiplistNode;typedef struct zskiplist {       struct zskiplistNode *header, *tail;    unsigned long length;    int level;} zskiplist;/* Create a new skiplist. */zskiplist *zslCreate(void) {       int j;    zskiplist *zsl;    zsl = zmalloc(sizeof(*zsl));    zsl->level = 1;    zsl->length = 0;    zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL);    for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {           zsl->header->level[j].forward = NULL;        zsl->header->level[j].span = 0;    }    zsl->header->backward = NULL;    zsl->tail = NULL;    return zsl;}/* 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在跳表中增加了一个向后的指针，不经可以从头部往后读取数据，亦可从后向前读取。