探索c#之跳跃表(SkipList)

基本介绍

SkipList是William Pugh在1990年提出的,它是一种可替代平衡树的数据结构。 SkipList在实现上相对比较简单,比如在限定时间条件下,能非常轻松的实现SkipList,但却实现不了B树、红黑树、AVL树等,想一想单B树的删除,就要考虑非常多的细节。虽说SkipList简单,但性能却非常高,在平均情况下,其插入、删除、查找数据时间复杂度都是O(log(N)),其最坏情况下都为O(N),这点要低于平衡树。 SkipList依赖随机生成数以一定概率来保持数据在树上的平衡分布,所以SkipList也属于概率算性的数据结构,和之前介绍的BoolFilter属于一个类型C#之布隆过滤器(Bloom filter)

算法思想

举个例子,楼主逛完街要回张江玉兰香苑,如果从人民广场做公交车回去,要路过非常多的站:

想想这么远的路程,多悲惨(在大数据情况下找对应项同样的问题),相较来说坐地铁就快很多,然后到广兰路换程。 这就是SkipList最核心的思想非常简单。 现在路线变成: 

因为可以一次跨越很多不需要的站,所以就快了很多。如果可以搭朋友顺风车的话,变成:

这个图就非常接近SkipList的结构及思想了。

演化步骤

大致了解怎么回事了、看具体怎么实现。 首先我们忘记树、图等高级概念及结构,回到我们刚学到链表的时候。 再看上面的回家路线图,我们把最下面一层当成一个链表,每个节点(站)指针指向下一个节点(站)。 单个有序链表:

按照传统的操作有序链表的做法,如果需要查找其中一条数据,需要顺序遍历。 按照地铁的思路,如果给一部分的节点增加个指向后面的节点指针,假设一半节点增加,最多遍历[n/2]+1次即可找到任意节点。这里把18、23、33、40、47节点都多增加个指针指向后面的节点:

以此类推,继续增加3、4个等更多的指针,使其指向更远的后方节点,这样可以更好的提高查询效率。 3个节点的情况:

如果理想情况下查找,就类似二分查找了。 SkipList通过随机数(丢硬币决定)在插入节点时,随机判定该节点应该有多少个执行后续节点的指针。 有几个执行后面节点指针,就是在第几层,比如上图18存在3个指针指向后面,它就在第三层,23有2个指针就在第二层。

实现细节

搜索

在同一层查找节点时和普通有序链表一样,顺序向后查找,查到返回,否则进入下一层继续向后查找。比如查找35,会从最顶层搜索比较18、相等返回,大于比较40继续下一层找,比较1、23、33、40后继续下一层,比较33、35正确返回、否则不存在。

更新

搜索到值后更新:

        SkipListNode<TKey, TValue> position;
        bool found = search(key, out position);
        if(found)
            position.value = value;

插入

插入时,如果值存在则更新,不存在插入。 如上图,假如要插入29,需要先查找到27插入到后面,如果扔硬币后得到3,那么依次增加指向后面节点的指针。

随机数

也称丢硬币做法。

       Random generator = new Random();
        int levels = 0;
        while (generator.NextDouble() < 0.5&&levels<=maxlevel)
            levels++;
        return levels;

删除同插入一样,如果找到,调整相对应的指针顺序,然后删除节点。

总结

由于skipList的高效及维护简单,所以很多大数据系统中在维护有序列表是都会使用SkipList。比如LevelDB在内存中暂存数据的结构MemTable是使用SkipList实现的,Redis在Sorted Set数据结构时也采用的是SkipList,还有Lucene中同样采用SkipList来对倒排列表进行快速查找。

关于就算法的实现, 可参考https://github.com/kencausey/SkipList

探索C#之系列导航

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

洛谷 P1876 开灯(思维,枚举,规律题)

P1876 开灯 题目背景 该题的题目是不是感到很眼熟呢? 事实上,如果你懂的方法,该题的代码简直不能再短。 但是如果你不懂得呢?那。。。(自己去想) 题目描述...

30960
来自专栏码洞

见缝插针 —— 深入 Redis HyperLogLog 内部数据结构分析

HyperLogLog算法是一种非常巧妙的近似统计海量去重元素数量的算法。它内部维护了 16384 个桶(bucket)来记录各自桶的元素数量。当一个元素到来时...

93920
来自专栏小红豆的数据分析

小蛇学python(18)pandas的数据聚合与分组计算

对数据集进行分组并对各组应用一个函数,这是数据分析工作的重要环节。在将数据集准备好之后,通常的任务就是计算分组统计或生成透视表。pandas提供了一个高效的gr...

29820
来自专栏小樱的经验随笔

详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

92860
来自专栏云霄雨霁

有向图----可达性问题

30800
来自专栏菩提树下的杨过

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1、路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的...

29090
来自专栏欢乐玩转技术

Leetcode 137. 只出现一次的数字 II - 题解

https://leetcode.com/problems/single-number-ii/

91240
来自专栏数据结构与算法

1226 倒水问题

1226 倒水问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 有两个无刻...

29360
来自专栏吴伟祥

UML 类图介绍 转

Unified Modeling Language (UML)又称统一建模语言或标准建模语言,是始于1997年一个OMG标准,它是一个支持模型化和软件系统开发的...

9010
来自专栏IT 指南者专栏

Python 从入门到入门基础练习十五题

微信公众号:compassblog 欢迎关注、转发,互相学习,共同进步! 有任何问题,请后台留言联系! ? 1、永远的 HelloWorld print("He...

1.1K70

扫码关注云+社区

领取腾讯云代金券