精华内容
下载资源
问答
  • 跳表实现

    2021-03-11 13:14:34
    下面是跳表的C语言实现,参考的是redis跳表实现思路。具体实现思路会在GitHub上更新,感兴趣的小伙伴可以关注跳跃表 #include <stdio.h> #include <stdlib.h> #define MAX_LEVEL 20 #define SKIPLIST_P...
    下面是跳表的C语言实现,参考的是redis跳表实现思路。具体实现思路会在GitHub上更新,感兴趣的小伙伴可以关注跳跃表
    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAX_LEVEL 20
    #define SKIPLIST_P  0.25
    
    typedef struct SkipListLevel {
        struct SkipListNode *forward;
    } SkipListLevel;
    
    typedef struct SkipListNode {
        int value;
        struct SkipListNode *backward;
        SkipListLevel level[];
    } SkipListNode;
    
    typedef struct SkipList {
        SkipListNode *head, *tail;
        unsigned int totalLevel;
    } SkipList;
    
    SkipListNode *CreateSkipListNode(int level, int value) {
        SkipListNode *node = malloc(sizeof(SkipList) + level * sizeof(struct SkipListLevel));
        node->value = value;
        return node;
    }
    
    SkipList *CreateSkipList() {
        SkipList *list = malloc(sizeof(SkipList));
    
        list->totalLevel = 1;
        list->head = CreateSkipListNode(MAX_LEVEL, 0);
        for (int j = 0; j < MAX_LEVEL; j++) {
            list->head->level[j].forward = NULL;
        }
        list->tail = NULL;
        return list;
    }
    
    /**
     *
     *
     *
     */
    int RandomLevel(void) {
        int level = 1;
        while ((random()&0xFFFF) < (SKIPLIST_P * 0xFFFF)) {
            level += 1;
        }
        return (level < MAX_LEVEL) ? level : MAX_LEVEL;
    }
    
    //添加一个节点
    SkipListNode *Insert(SkipList *skipL, int value) {
        SkipListNode *update[MAX_LEVEL], *tmp, *node;
        int level, i;
    
        tmp = skipL->head;
        for (i = skipL->totalLevel - 1; i >= 0; i--) {
            while (tmp->level[i].forward && tmp->level[i].forward->value < value) {
                tmp = tmp->level[i].forward;
            }
            update[i] = tmp;
        }
    
        level = RandomLevel();
    
        if (level > skipL->totalLevel) {
            for (i = skipL->totalLevel; i < level; i++) {
                update[i] = skipL->head;
            }
            skipL->totalLevel = level;
        }
    
        node = CreateSkipListNode(level, value);
        for (i = 0; i < level; i++) {
            node->level[i].forward = update[i]->level[i].forward;
            update[i]->level[i].forward = node;
        }
    
        node->backward = (update[0] == skipL->head) ? NULL : update[0];
    
        if (node->level[0].forward) {
            node->level[0].forward->backward = node;
        } else {
            skipL->tail = node;
        }
        return node;
    }
    
    
    //查找
    int Find(SkipList *skipL, int value) {
        int i;
        SkipListNode *start, *stop;
    
        start = skipL->head;
        for (i = skipL->totalLevel - 1; i >= 0; i--) {
            while (start->level[i].forward && start->level[i].forward->value < value) {
                start = start->level[i].forward;
            }
            stop = start->level[i].forward;
        }
    
        if (start->value == value) {
            return 1;
        }
        while (start != stop) {
            if (start->level[0].forward->value == value) {
                return 1;
            }
            start = start->level[0].forward;
        }
    
        return -1;
    }
    
    int main() {
        SkipList *list;
        int insertData[7] = {76, 90, 2, 4, 67, 1, 4};
        int testData[5] = {4, 5, 6, 76, 1};
    
        list = CreateSkipList();
    
        for (int i = 0; i < 7; i++) {
            Insert(list, insertData[i]);
        }
    
        for (int i = 0; i < 5; i++) {
            printf("%d : %d\n", testData[i], Find(list, testData[i]));
        }
    
    }
    
    展开全文
  • java跳表实现

    2021-07-11 22:05:50
    java跳表实现 概念:一种有序链表,带有多级索引,查询性能为O(logN)。 运用:Redis,ConcurrentSkipListMap 这里主要参照了leetcode的实现,补充了泛型实现。 public class SkipList<T> { //当前层级 ...

    java跳表实现

    概念:一种有序链表,带有多级索引,查询性能为O(logN)。
    运用:Redis,ConcurrentSkipListMap

    这里主要参照了leetcode的实现,补充了泛型实现。

    public class SkipList<T> {
    
        //当前层级
        private int curentLevel = 1;
    	//最大索引层级
        private final static int MAX_LEVEL = 32;
    	//队列头节点
        private final Node<T> HEAD = new Node<>(null, MAX_LEVEL);
    	//晋升几率
        private final static double promote = 0.25d;
    
        private Comparator<T> comparator;
    
        public SkipList() {
    
        }
    
        public SkipList(Comparator<T> comparator) {
            this.comparator = comparator;
        }
    
        public void add(T value) {
            if (value == null) {
                throw new NullPointerException();
            }
            int level = getRandomLevel();
            Node<T> newNode = new Node<>(value, level);
    
            Node<T> point = HEAD;
            for (int current = curentLevel - 1; current >= 0; current--) {
                point = findClosest(point, current, value);
                if(current < level){
                    Node<T> oldNext = point.nextArr[current];
                    point.nextArr[current] = newNode;
                    newNode.nextArr[current] = oldNext;
                }
            }
    
            if (level > curentLevel){ //如果随机出来的层数比当前的层数还大,那么超过currentLevel的head 直接指向newNode
                for (int i = curentLevel; i < level; i++) {
                    HEAD.nextArr[i] = newNode;
                }
                curentLevel = level;
            }
        }
    
        public boolean search(T value) {
            if (value == null) {
                return false;
            }
    
            Node<T> point = HEAD;
            for (int current = curentLevel - 1; current >= 0; current--) {
                point = findClosest(point, current, value);
                if(point.nextArr[current] != null && point.nextArr[current].value.equals(value)){
                    return true;
                }
            }
            return false;
        }
    
        public boolean erase(T value) {
            if (value == null) {
                return false;
            }
    
            boolean flag = false;
            Node<T> point = HEAD;
            for (int current = curentLevel - 1; current >= 0; current--) {
                point = findClosest(point, current, value);
                if(point.nextArr[current] != null && point.nextArr[current].value.equals(value)){
                    point.nextArr[current] = point.nextArr[current].nextArr[current];
                    flag = true;
                }
            }
    
            return flag;
        }
    
        private Node<T> findClosest(Node<T> point, int level, T value) {
            Node<T> node = point;
            while (true) {
                Node<T> next = node.nextArr[level];
                if (next == null || cpr(next.value, value) >= 0) {
                    break;
                } else {
                    node = next;
                }
            }
            return node;
        }
    
        private int getRandomLevel() {
            int initLevel = 1;
            while (Math.random() <= promote && initLevel < MAX_LEVEL) {
                initLevel++;
            }
            return initLevel;
        }
    
        private int cpr(T a, T b) {
            if (comparator != null) {
                return comparator.compare(a, b);
            } else {
                Comparable<T> comparable = (Comparable<T>) a;
                return comparable.compareTo(b);
            }
        }
    
        class Node<T> {
            T value;
            Node<T>[] nextArr;
    
            Node(T value, int size) {
                this.value = value;
                this.nextArr = new Node[size];
            }
        }
    }
    
    
    展开全文
  • 使用跳表实现定时器

    2021-01-25 09:01:52
    使用跳表实现定时器 使用的是redis中使用的跳表结构,直接从中迁移出来并修改。 通过跳表实现的时间轮,查询第一个数据的时间复杂度就是O(1),插入时间复杂度就 大概率的趋向于O(logn(N))。 定时器本身就是从头部开始...

    使用跳表实现定时器

    • 使用的是redis中使用的跳表结构,直接从中迁移出来并修改。
    • 通过跳表实现的时间轮,查询第一个数据的时间复杂度就是O(1),插入时间复杂度就 大概率的趋向于O(logn(N))。
    • 定时器本身就是从头部开始取数据,跳表这一数据结构就特别匹配定时器的实现。

    文件skiplist.h

    #ifndef _MARK_SKIPLIST_
    #define _MARK_SKIPLIST_
    
    /* ZSETs use a specialized version of Skiplists */
    #define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^64 elements */
    #define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
    
    typedef struct zskiplistNode zskiplistNode;
    typedef void (*handler_pt) (zskiplistNode *node);
    struct zskiplistNode {
        // sds ele;
        // double score;
        unsigned long score; // 时间戳
        handler_pt handler;
        /* struct zskiplistNode *backward; 从后向前遍历时使用*/
        struct zskiplistLevel {
            struct zskiplistNode *forward;
            /* unsigned long span; 这个存储的level间节点的个数,在定时器中并不需要*/ 
        } level[];
    };
    
    typedef struct zskiplist {
        // 添加一个free的函数
        struct zskiplistNode *header/*, *tail 并不需要知道最后一个节点*/;
        int length;
        int level;
    } zskiplist;
    
    zskiplist *zslCreate(void);
    void zslFree(zskiplist *zsl);
    zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt func);
    zskiplistNode* zslMin(zskiplist *zsl);
    void zslDeleteHead(zskiplist *zsl);
    void zslDelete(zskiplist *zsl, zskiplistNode* zn); 
    
    void zslPrint(zskiplist *zsl);
    #endif
    

    文件skiplist.c

    #include <stdlib.h>
    #include <stdio.h>
    #include "skiplist.h"
    
    void defaultHandler(zskiplistNode *node) {
    }
    
    /* Create a skiplist node with the specified number of levels. */
    zskiplistNode *zslCreateNode(int level, unsigned long score, handler_pt func) {
        zskiplistNode *zn =
            malloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
        zn->score = score;
        zn->handler = func;
        return zn;
    }
    
    
    // 创建跳表
    zskiplist *zslCreate(void) {
        int j;
        zskiplist *zsl;
    
        zsl = malloc(sizeof(*zsl));
        zsl->level = 1;
        zsl->length = 0;
        zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,defaultHandler);
        for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
            zsl->header->level[j].forward = NULL;
        }
        return zsl;
    }
    
    /* Free a whole skiplist. */
    void zslFree(zskiplist *zsl) {
        zskiplistNode *node = zsl->header->level[0].forward, *next;
    
        free(zsl->header);
        while(node) {
            next = node->level[0].forward;
            free(node);
            node = next;
        }
        free(zsl);
    }
    
    // 获取随机的层数
    int zslRandomLevel(void) {
        int level = 1;
        while ((arc4random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
            level += 1;
        return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
    }
    
    // 向跳表插入节点
    zskiplistNode *zslInsert(zskiplist *zsl, unsigned long score, handler_pt fun){
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
        int i, level;
    
        x = zsl->header;
    	// update记录路径,方便建立节点时候的的前指针指向他
        for (i = zsl->level-1; i >= 0; i--) {
            while (x->level[i].forward &&
                    x->level[i].forward->score < score)
            {
                x = x->level[i].forward;
            }
            update[i] = x;
        }
        level = zslRandomLevel();
        printf("zskiplist add node level = %d\n", level);
    	// 高度超过了原先最大高度,补充头指向新建的路径
        if (level > zsl->level) {
            for (i = zsl->level; i < level; i++) {
                update[i] = zsl->header;
            }
            zsl->level = level;
        }
        x = zslCreateNode(level,score,func);
        for (i = 0; i < level; i++) {
    		// 新建节点接续他的前节点的后续指针
            x->level[i].forward = update[i]->level[i].forward;
    		// 前指针指向新建节点
            update[i]->level[i].forward = x;
        }
    
        zsl->length++;
        return x;
    }
    
    // 头结点不存数据,头结点的第一个后续节点为最小
    zskiplistNode* zslMin(zskiplist *zsl) {
        zskiplistNode *x;
        x = zsl->header;
        return x->level[0].forward;
    }
    
    // 删除跳表头部节点
    void zslDeleteHead(zskiplist *zsl) {
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL];
        zskiplistNode *x = zslMin(zsl);
        if (!x) return;
        int i;
        for (i = zsl->level-1; i >= 0; i--) {
    		// 拷贝x的每一层的后续节点
            if (zsl->header->level[i].forward == x) {
                zsl->header->level[i].forward = x->level[i].forward;
            }
        }
    	// 计算跳表的最高层
        while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        zsl->length--;
    }
    
    
    void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
        int i;
    	// 将行走路径上原先指向x的节点指向x的后续节点
        for (i = 0; i < zsl->level; i++) {
            if (update[i]->level[i].forward == x) {
                update[i]->level[i].forward = x->level[i].forward;
            } 
        }
        while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
            zsl->level--;
        zsl->length--;
    }
    
    // 删除任一跳表节点
    void zslDelete(zskiplist *zsl, zskiplistNode* zn) {
        zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
        int i;
    
        x = zsl->header;
    	// update存储行走路径
        for (i = zsl->level-1; i >= 0; i--) {
            while (x->level[i].forward &&
                    x->level[i].forward->score < zn->score)
            {
                x = x->level[i].forward;
            }
            update[i] = x;
        }
    	// 此时循环刚出来的是欲删除节点的前序节点
        x = x->level[0].forward;
        if (x && zn->score == x->score) {
            zslDeleteNode(zsl, x, update);
            free(x);
        }
    }
    
    void zslPrint(zskiplist *zsl) {
        zskiplistNode *x;
        x = zsl->header;
        x = x->level[0].forward;
        printf("start print skiplist level = %d\n", zsl->level);
        int i;
        for (i = 0; i < zsl->length; i++) {
            printf("skiplist ele %d: score = %lu\n", i+1, x->score);
            x = x->level[0].forward;
        }
    }
    
    

    定时器实现

    #include <stdio.h>
    #include <stdint.h>
    #include <unistd.h>
    #include <stdlib.h>
    #include <stddef.h>
    #include <time.h>
    #if defined(__APPLE__)
    #include <AvailabilityMacros.h>
    #include <sys/time.h>
    #include <mach/task.h>
    #include <mach/mach.h>
    #endif
    #include "skiplist.h"
    
    static uint32_t
    current_time() {
    	uint32_t t;
    #if !defined(__APPLE__) || defined(AVAILABLE_MAC_OS_X_VERSION_10_12_AND_LATER)
    	struct timespec ti;
    	clock_gettime(CLOCK_MONOTONIC, &ti);
    	t = (uint32_t)ti.tv_sec * 1000;
    	t += ti.tv_nsec / 1000000;
    #else
    	struct timeval tv;
    	gettimeofday(&tv, NULL);
    	t = (uint32_t)tv.tv_sec * 1000;
    	t += tv.tv_usec / 1000;
    #endif
    	return t;
    }
    
    zskiplist *init_timer() {
        return zslCreate();
    }
    
    zskiplistNode *add_timer(zskiplist *zsl, uint32_t msec, handler_pt func) {
        msec += current_time();
        printf("add_timer expire at msec = %u\n", msec);
        return zslInsert(zsl, msec, func);
    }
    
    void del_timer(zskiplist *zsl, zskiplistNode *zn) {
        zslDelete(zsl, zn);
    }
    
    void expire_timer(zskiplist *zsl) {
        zskiplistNode *x;
        uint32_t now = current_time();
        for (;;) {
            x = zslMin(zsl);
            if (!x) break;
            if (x->score > now) break;
            printf("touch timer expire time=%lu, now = %u\n", x->score, now);
            x->handler(x);
            zslDeleteHead(zsl);
        }
    }
    
    void print_hello(zskiplistNode *zn) {
        printf("hello world time = %lu\n", zn->score);
    }
    
    int main()
    {
        zskiplist *zsl = init_timer();
        add_timer(zsl, 3010, print_hello);
        add_timer(zsl, 3004, print_hello);
        zskiplistNode *zn = add_timer(zsl, 3005, print_hello);
        del_timer(zsl, zn);
        add_timer(zsl, 3008, print_hello);
        add_timer(zsl, 3003, print_hello);
        // zslPrint(zsl);
        for (;;) {
            expire_timer(zsl);
            usleep(10000); // 暂用睡眠函数替代阻塞
        }
        return 0;
    }
    
    展开全文
  • 跳表实现原理

    2019-04-15 00:40:42
    跳表实现原理 是一种动态的数据结构,它可以支持快速的插入、查找、查询操作.写起来并不复杂,甚至可以替代红黑树. 对于一个单链表来讲,即使链表中的储存数据是有序的.如果我们想要在其中查找某个数据,也只能...

    跳表实现原理

    是一种动态的数据结构,它可以支持快速的插入、查找、查询操作.写起来并不复杂,甚至可以替代红黑树.

    对于一个单链表来讲,即使链表中的储存数据是有序的.如果我们想要在其中查找某个数据,也只能从头到尾遍历链表.这样的效率会很低,时间复杂度也很高 O(n).

    如何提升链表的查询效率呢? 我们对链表建立一级索引层.每两个节点提取一个节点到上一级.图中的 down 表示 down 指针,指向下一级结点。


    这种链表加多级索引的结构,就是跳表

    小结:

    跳表采用空间换时间的设计思路,通过构建多级索引来提高查询的效率,实现了基于链表的二分查找.跳表是一种动态的数据结构,支持快速的插入.

    展开全文
  • 本项目是基于跳表实现的轻量级键值型存储引擎,使用C++实现。插入数据、删除数据、查询数据、数据展示、数据落盘、文件加载数据,以及数据库大小显示。 一、跳表定义 链表的数据结构为一个节点中除了存储数据,还...
  • [算法][面试]基于Python的跳表实现样例
  • 数据结构之跳表实现

    2021-04-26 10:24:15
    跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。-----来自百度百科 它的效率和红黑树以及 AVL 树不相上下,但实现起来比前面两个...
  • 有序集合是Redis对象系统中的一部分,其底层采用跳表和压缩列表两种形式存储,在上一篇介绍了跳表实现,就趁热打铁看一下有序集合的跳表实现本篇主要涉及的是有序集合添加数据的命令,后面会看到,在命令的底层实现...
  • 山东大学 跳表实现与分析(QT以及数学分析,以及cmd版都有)
  • levelDB跳表实现

    2016-03-02 23:22:00
    跳表的原理就是利用随机性建立索引,加速搜索,并且简化代码实现难度。具体的跳表原理不再赘述,主要是看了levelDB有一些实现细节的东西,凸显自己写的实现不足之处。 去除冗余的key template<typename Key, ...
  • 《数据结构、算法与应用 —— C++语言描述》学习笔记 — 字典 — 跳表实现一、跳表1、理想情况2、插入和删除3、级的分配二、跳表实现1、节点定义2、声明3、拷贝控制4、拷贝控制内部接口5、容量接口6、查找接口7、...
  • 前言做游戏的一般都有游戏排行榜的需求,要查一下某个uid的积分排名第几,这里我给大家推荐之前我们使用的一种排序算法,跳表skiplist。跳表是一个随机化的数据结构。它允许快速查询一个有序...
  • Java JDK中的跳表实现

    2020-01-01 23:39:58
    一、什么是Skip list(跳表) Skip list(跳表)是一种可以代替平衡树的数据结构,默认是按照Key值升序的。Skip list让已排序的数据分布在多层链表中,以0-1随机数决定一个数据的向上攀升与否,通过“空间来换取时间...
  • 本项目就是基于跳表实现的轻量级键值型存储引擎,使用C++实现。插入数据、删除数据、查询数据、数据展示、数据落盘、文件加载数据,以及数据库大小显示。 在随机写读情况下,该项目每秒可处理啊请求数(QPS): 24.39...
  • 跳表优化思路:每隔两个或两个以上节点时,提取一个节点到上一级,抽取出来的一级称为索引或索引层。down指针,可以指向下一级结点。 这种链表加多级索引的结构,就是跳表。 例如要查找节点16,可以现在...
  • 先科普一下跳表以及分析一下跳表优劣: 跳表:在普通链表中,给一些节点增加额外的指针,使得这些节点能够一次跨越更多的中间节点,提高了效率。 优点:相比普通链表,由于跳跃的特性,可以节省便利次数,时间...
  • 散列 - 跳表实现字典

    2014-09-12 20:09:51
    skiplist.h /******************************************************************** purpose: 跳表 author: xianyun1230 QQ: 836663997 e-mail: xianyun1230@163.com creat

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,330
精华内容 4,132
关键字:

跳表的实现