skiplist 跳跃表分析

跳表(skip List)是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)。跳表是由William Pugh发明的，跳表的实质是一种特殊的链表，只不过它在链表的基础上增加了跳跃功能，正是这个跳跃的功能，使得在查找元素时，能够提供O(log n)的时间复杂度。 红黑树等这样的平衡数据结构查找的时间复杂度也是O(log n)，并且相对于红黑树这样的平衡二叉树skiplist的优点是更好的支持并发操作，因为红黑树在插入和删除可能需要做一些rebanlance操作，这样的操作会涉及到整个树的其他部分，而skiplist的操作就显得局部性一些，需要锁住的节点更少，对并发也就更友好一些。并且只要熟悉链表的基本操作,再加之对跳表原理的理解，实现一个跳表数据结构就是一个很自然的事情了，但是要实现像红黑树这样的数据结构并非易事。

跳表在当前热门的开源项目中也有很多应用，比如LevelDB的核心数据结构memtable是用跳表实现的，Redis的sorted set数据结构也是由跳表实现的。

跳表的基本特征：

1. 一个跳表应该有几个层（level）组成；
2. 跳表的第一层包含所有的元素；
3. 每一层都是一个有序的链表；
4. 如果元素x出现在第i层，则所有比i小的层都包含x；

5. 每个节点包含key/value和一个指向同一层链表的下个节点的指针数组。

   
   跳表的图示

跳表的代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define LEVEL_MAX 32

typedef struct skiplist_node_s
{
    int key;
    int value;
    struct skiplist_node_s *next[1];
} skiplist_node_t;

typedef struct skiplist_list_s
{
    int level;
    skiplist_node_t *head;
} skiplist_list_t;


skiplist_list_t *skiplist_create(void);
bool skiplist_insert(skiplist_list_t *list, int key, int value);
bool skiplist_remove(skiplist_list_t *list, int key);
int *skiplist_find(skiplist_list_t *list, int key);
void skiplist_free(skiplist_list_t *list);

int main(int argc, char **argv)
{
    skiplist_list_t *list = skiplist_create();

    for (int i = 0; i < 1000; i++) {
        skiplist_insert(list, i, i);
    }

    for (int i = 1000 - 1; i >= 0; i--) {
        if (!skiplist_find(list, i)) {
            printf("oh no, not found...\n");
        }
    }

    for (int i = 0; i < 1000; i++) {
        skiplist_remove(list, i);
    }

    for (int i = 1000 - 1; i >= 0; i--) {
        if (skiplist_find(list, i)) {
            printf("oh no, found it...\n");
        }
    }

    skiplist_free(list);
    printf("hello skiplist\n");

    return 0;
}

int skiplist_random_level(void)
{
    int level = 1;

    while (rand() % 2) {
        level++;
    }

    return level < LEVEL_MAX ? level : LEVEL_MAX;
}

skiplist_node_t *skiplist_create_node(int level, int key, int value)
{
    skiplist_node_t *node = (skiplist_node_t *) malloc(sizeof(skiplist_node_t) +
                                                       (level - 1) * sizeof(skiplist_node_t *));
    if (!node) {
        return NULL;
    }

    memset(node, 0, sizeof(skiplist_node_t) + (level - 1) * sizeof(skiplist_node_t *));
    node->key = key;
    node->value = value;

    return node;
}

skiplist_list_t *skiplist_create(void)
{
    skiplist_list_t *list = NULL;
    skiplist_node_t *head = NULL;

    list = (skiplist_list_t *) malloc(sizeof(skiplist_list_t));
    if (!list) {
        return NULL;
    }

    head = skiplist_create_node(LEVEL_MAX, 0, 0);
    if (!head) {
        free(list);
        return NULL;
    }

    /* init srand seed */
    srand(time(0));
    memset(head, 0, sizeof(skiplist_node_t) + (LEVEL_MAX - 1) * sizeof(skiplist_node_t *));
    list->level = 0;
    list->head = head;

    return list;
}

bool skiplist_insert(skiplist_list_t *list, int key, int value)
{
    skiplist_node_t *update[LEVEL_MAX];
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    /* record update array */
    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        update[i] = p;
    }
    /* if key exists, just return */
    if (q && (q->key == key)) {
        q->value = value;
        return true;
    }

    int level = skiplist_random_level();
    if (level > list->level) {
        for (i = list->level; i < level; i++) {
            update[i] = list->head;
        }
        list->level = level;
    }

    /* create node and insert it */
    p = skiplist_create_node(level, key, value);
    if (!p) {
        return false;
    }
    for (i = level - 1; i >= 0; i--) {
        p->next[i] = update[i]->next[i];
        update[i]->next[i] = p;
    }
    
    return true;
}

bool skiplist_remove(skiplist_list_t *list, int key)
{
    skiplist_node_t *update[LEVEL_MAX];
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    /* record update array */
    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        update[i] = p;
    }
    /* if key not exists, just return */
    if (!q || (q && q->key != key)) {
        return false;
    }

    /* remove node according to level */
    for (i = list->level - 1; i >= 0; i--) {
        if (update[i]->next[i] == q) {
            update[i]->next[i] = q->next[i];
            if (list->head->next[i] == NULL) {
                /* the removed node is highest level node */
                list->level--;
            }
        }
    }

    free(q);
    return true;
}

int *skiplist_find(skiplist_list_t *list, int key)
{
    skiplist_node_t *q = NULL, *p = list->head;
    int i = list->level;

    for (; i >= 0; i--) {
        while ((q = p->next[i]) && (q->key < key)) {
            p = q;
        }
        if (q && q->key == key) {
            return &(q->key);
        }
    }

    return NULL;
}

void skiplist_free(skiplist_list_t *list)
{
    if (!list) {
        return;
    }

    skiplist_node_t *curr = list->head;
    skiplist_node_t *next = NULL;
    while (curr) {
        next = curr->next[0];
        free(curr);
        curr = next;
    }

    free(list);
}

参考资料：

1. skiplist 跳跃表详解及其编程实现
2. 《数据结构与算法分析 C语言版》跳跃表章节