算法: skiplist 跳跃表代码实现和原理

简介: SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构。由于它的代码以及原理实现的简单性,更为人们所接受。所有操作均从上向下逐层查找,越上层一次next操作跨度越大。其实现是典型的空间换时间。

SkipList在leveldb以及lucence中都广为使用,是比较高效的数据结构。由于它的代码以及原理实现的简单性,更为人们所接受。

所有操作均从上向下逐层查找,越上层一次next操作跨度越大。其实现是典型的空间换时间。

Skip lists  are data structures  that use probabilistic  balancing rather  than  strictly  enforced balancing. 
As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly
faster than equivalent algorithms for balanced trees.

 

后面的图片来自:http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html

后面的代码当然是我自己写的呀。

(1)SkipList图示

(2)SkipList插入

(3)SkipList删除

(3)SkipList查找

  查找操作也是上面的套路


 

实现中主要有几点需要注意:

(1) 如何支持各种数据类型的数据。 通用的做法就是 char数组保存value + char数组对应value的长度

(2) 看图中,每个节点有多个指向不同层级的指针。代码中可以使用指针数组 + 节点的level来保存。

(3) 查找、插入、删除操作,都要找到(或者经过)需要操作点的前驱节点。这个操作可以封装起来,极大减少代码量。

(4) skiplist整体是一个链表, 设置一个头节点方便后续的各种操作。

数据结构如下:

 1 truct SkipNode{
 2     int  key;       //key
 3     char *value;    //value,可以支持任意类型
 4     int  length;    //value_length, 记录数据长度
 5     int  level;     //保存当前节点的level
 6     SkipNode** next;    //记录各层后续的地址
 7 };

skiplist.h

class SkipList{
public:
    SkipList(int level = 10);
    ~SkipList();

    //根据key获取数据
    int get(const int key, char* value, int &length);

    //链表插入新节点
    int insert(
            const int key, 
            const char* value, 
            const int length);

    //删除key对应节点
    int del(const int key);

private:
    //初始化链表头, 路过链表
    int init();

    //空间释放
    int deinit();

    //新建一个节点
    SkipNode* createNode(
            const int key, 
            const char* value, 
            const int &length,
            const int level);

    //所用随机函数获取一个level值, 用于后续新建节点使用
    int getNewNodeLevel();
   
    //init update node
    int init_updatenode();

    //get node pre(get update)
    int get_update(const int key);

    //记录skiplist支持的最大level, 以及当前高度
    int max_level;
    int curr_level;

    SkipNode* List; //skiplist 第一个节点
    SkipNode** Update;  //记录每层搜索节点的前驱节点
};

 

cpp代码比较长,这里就不贴了。

相关文章
|
2月前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
50 3
|
29天前
|
算法 容器
令牌桶算法原理及实现,图文详解
本文介绍令牌桶算法,一种常用的限流策略,通过恒定速率放入令牌,控制高并发场景下的流量,确保系统稳定运行。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
令牌桶算法原理及实现,图文详解
|
12天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
9天前
|
存储 人工智能 缓存
【AI系统】布局转换原理与算法
数据布局转换技术通过优化内存中数据的排布,提升程序执行效率,特别是对于缓存性能的影响显著。本文介绍了数据在内存中的排布方式,包括内存对齐、大小端存储等概念,并详细探讨了张量数据在内存中的排布,如行优先与列优先排布,以及在深度学习中常见的NCHW与NHWC两种数据布局方式。这些布局方式的选择直接影响到程序的性能,尤其是在GPU和CPU上的表现。此外,还讨论了连续与非连续张量的概念及其对性能的影响。
29 3
|
13天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
1月前
|
负载均衡 算法 应用服务中间件
5大负载均衡算法及原理,图解易懂!
本文详细介绍负载均衡的5大核心算法:轮询、加权轮询、随机、最少连接和源地址散列,帮助你深入理解分布式架构中的关键技术。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
5大负载均衡算法及原理,图解易懂!
|
22天前
|
缓存 算法 网络协议
OSPF的路由计算算法:原理与应用
OSPF的路由计算算法:原理与应用
35 4
|
21天前
|
存储 缓存 算法
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
22天前
|
存储 算法 网络协议
OSPF的SPF算法介绍:原理、实现与应用
OSPF的SPF算法介绍:原理、实现与应用
52 3
|
27天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。