前言

之前在研究LevelDB的時候聽說了這個數(shù)據(jù)結(jié)構(gòu)，后面發(fā)現(xiàn)Redis中也用這個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)有序集合zset，研究了一下發(fā)現(xiàn)特別簡單并且非常容易實現(xiàn)，所以記錄一下，畢竟18年的最后一次學(xué)習(xí)!:)。

之前看到有文章提到，像紅黑樹、B樹這些數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)起來并不是這么簡單，而SkipList結(jié)構(gòu)和實現(xiàn)都特別簡單，并且可以擁有和紅黑樹、B樹接近的性能(是的，我就是被這段話安利的)。

辣雞的筆記記錄，所以有理解錯誤的地方，還請各位直接指出:)。

結(jié)構(gòu)定義

考慮一個鏈表結(jié)構(gòu)，如下圖:

你會發(fā)現(xiàn)，無論你想找鏈表上哪個位置的元素，你都需要從鏈表的頭部開始往后一個一個的進(jìn)行遍歷。

而跳表的思路是，在鏈表的基礎(chǔ)上再建立一層或者多層索引也叫做level，來幫助你更快的找到想要的元素，加上了索引后的結(jié)構(gòu)變成如下圖:

那么這個時候我們再來考慮如果我們想找到元素9，那么按照這個結(jié)構(gòu)的流程就會變成如下步驟。

我們會從頂層的索引開始尋找，我們要找的元素是9，第一層的第一個索引節(jié)點值是1，因為9比1大，所以跳到下一個索引節(jié)點上，值為5。然后再進(jìn)行比較，9還是比8大，所以還是跳到下一個索引節(jié)點上。最后的一個索引節(jié)點值是11，比9大了，所以就在這個索引位置的下方往前找到元素9。用圖表示這個流程的話就是如下:

如果按照正常的鏈表遍歷流程找到9需要遍歷前8個元素，而用跳表的這個結(jié)構(gòu)只需要遍歷4次就找到元素9。

當(dāng)然跳表不止可以有一層索引，還可以擁有多層，擁有多層索引后的結(jié)構(gòu)如下圖:

那么按照結(jié)構(gòu)，我們要插入一個元素7，前面的流程和搜索基本一致，先找到7元素要插入的位置，流程如下圖:

這個時候，使用隨機(jī)數(shù)產(chǎn)生一個隨機(jī)值，用這個隨機(jī)數(shù)來決定7這個位置往上要更新多少層，如果大于現(xiàn)有層數(shù)則要添加新層，假如我們的隨機(jī)數(shù)產(chǎn)生的值是6，那么我們最后的結(jié)構(gòu)就會變成這樣:

C語言基本實現(xiàn)

其實說出來你們不信，Redis其實包含大量的數(shù)據(jù)結(jié)構(gòu)實現(xiàn)，并且實現(xiàn)的非常精簡，所以這里就套用Redis的跳表結(jié)構(gòu)體定義并稍加修改，C跳表結(jié)構(gòu)體定義如下:

#define SKIPLIST_MAX_LEVEL 64

typedef struct skipListNode {
    int key;
    int value;
    struct skipListLevel {
        struct skipListNode *forward;
    } level[];
} skipListNode;

typedef struct skipList {
    int level;
    struct skipListNode *header;
} skipList;

這個結(jié)構(gòu)體里面的level字段，就相當(dāng)于上圖的層的一豎列，所以大部分的跳表初始化代碼也可以套用大部分的Redis跳表實現(xiàn)，這里只考慮初始化和搜索及插入操作，刪除操作原理類似插入，所以不重復(fù)描述，定義一組操作方法：

skipListNode *slCreateNode(int level, int key, int value);
skipList *slCreate(void);
skipListNode *slInsert(skipList *sl, int key, int value);
int slRandomLevel(void);
skipListNode *slSearch(skipList *sl, int key);

創(chuàng)建一個包含制定數(shù)量層的跳表節(jié)點:

skipListNode *slCreateNode(int level, int key, int value)
{
    skipListNode *sn = malloc(sizeof(*sn) + level * sizeof(struct skipListLevel));
    sn->key = key;
    sn->value = value;
    return sn;
}

創(chuàng)建一個跳表結(jié)構(gòu):

skipList *slCreate(void)
{
    int i;
    skipList *sl;

    sl = malloc(sizeof(*sl));
    sl->level = 1;
    sl->header = slCreateNode(SKIPLIST_MAX_LEVEL, 0, 0);
    for (i = 0;  i < SKIPLIST_MAX_LEVEL; i++) {
        sl->header->level[i].forward = NULL;
    }

    return sl;
}

跳表中的第一層就是最完整的鏈表結(jié)構(gòu)，可以參考之前上面的圖，所以初始化就默認(rèn)初始化level字段為1。

產(chǎn)生一個隨機(jī)數(shù)用來確定插入后要更新或者新增的層數(shù)

int slRandomLevel(void)
{
    int level = 1;
    while ((rand() & 0xFFFF) < (0.5 * 0xFFFF))
        level += 1;
    return (level < SKIPLIST_MAX_LEVEL) ? level : SKIPLIST_MAX_LEVEL;
}

這里產(chǎn)生的隨機(jī)數(shù)是會小于最大可以創(chuàng)建的層數(shù)量(SKIPLIST_MAX_LEVEL)。

插入一個key->value進(jìn)入跳表:

skipListNode *slInsert(skipList *sl, int key, int value)
{
    skipListNode *update[SKIPLIST_MAX_LEVEL];
    skipListNode *sn;

    sn = sl->header;
    int i, level;
    for (i = sl->level - 1; i >= 0; i--) {
        while(sn->level[i].forward && sn->level[i].forward->key < key)
            sn = sn->level[i].forward;
        update[i] = sn;
    }

    level = slRandomLevel();
    if (level > sl->level) {
        for (i = sl->level; i < level; i++) {
            update[i] = sl->header;
        }
        sl->level = level;
    }

    sn = slCreateNode(level, key, value);
    for (i = 0; i < level; i++) {
        sn->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = sn;
    }

    return sn;
}

和之前說的一樣，和遍歷流程一樣先找到要插入的節(jié)點位置，然后順便記錄下遍歷路徑上的節(jié)點，這些都是需要進(jìn)行鏈表更新的，這些節(jié)點全部存放在update數(shù)組中。

然后使用slRandomLevel確定要更新或者新增的層數(shù)，如果隨機(jī)的層數(shù)大于現(xiàn)有鏈表的層數(shù)，則新增層，并且更新鏈表現(xiàn)在的層數(shù)。

最后創(chuàng)建節(jié)點，并進(jìn)行了常規(guī)的鏈表添加操作，刪除的基本過程差不多，就不重復(fù)描述了。

按照key尋找value:

skipListNode *slSearch(skipList *sl, int key)
{
    skipListNode *sn;
    int i;

    sn = sl->header;
    for (i = sl->level - 1; i >= 0; i--) {
        while (sn->level[i].forward && sn->level[i].forward->key < key)
            sn = sn->level[i].forward;
    }

    sn = sn->level[0].forward;
    if (sn && key == sn->key) {
        return sn;
    } else {
        return NULL;
    }
}

搜索過程就更加簡單，就是從跳表的頂層索引開始遍歷，直到找到下一個值比需要搜索的key大，就找到了位置。

那么用起來的效果就是這樣：

int main() {
    skipList *sl = slCreate();
    slInsert(sl, 2, 10);
    slInsert(sl, 3, 11);

    int key2 = slSearch(sl, 2)->value;
    int key3 = slSearch(sl, 3)->value;
    printf("key2:%d\n", key2);
    printf("key3:%d\n", key3);
    return 0;
}

輸出

key2:10
key3:11

總結(jié)

跳表的整體思路就是通過添加索引層來加快遍歷速度，本質(zhì)也是一個可以二分查找的有序鏈表，或者說也是一種樹結(jié)構(gòu)。并且通過我上面貼的代碼應(yīng)該也能感受到跳表是一個非常簡單并且非常容易實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，并且性能也非常接近其它樹結(jié)構(gòu)，也算是一種非常簡單實用的數(shù)據(jù)結(jié)構(gòu)了。

參考資料:
https://www.cnblogs.com/a8457013/p/8251967.html
https://www.youtube.com/watch?v=ypod5jeYzAU
http://www.cnblogs.com/liuhao/archive/2012/07/26/2610218.html
https://en.wikipedia.org/wiki/Skip_list
https://brilliant.org/wiki/skip-lists/