你的位置:首页 > ASP.net教程

[ASP.net教程]探索c#之跳跃表(SkipList)


阅读目录:

  1. 基本介绍
  2. 算法思想
  3. 演化步骤
  4. 实现细节
  5. 总结

基本介绍

SkipList是William Pugh在1990年提出的,它是一种可替代平衡树的数据结构。 SkipList在实现上相对比较简单,比如在限定时间条件下,能非常轻松的实现SkipList,但却实现不了B树、红黑树、AVL树等,想一想单B树的删除,就要考虑非常多的细节。虽说SkipList简单,但性能却非常高,在平均情况下,其插入、删除、查找数据时间复杂度都是O(log(N)),其最坏情况下都为O(N),这点要低于平衡树。
由于skipList的高效及维护简单,所以很多大数据系统中在维护有序列表是都会使用SkipList,比如LevelDB在内存中暂存数据的结构MemTable就是使用SkipList实现的,Redis在Sorted Set数据结构时也采用的是SkipList,还有Lucene中同样采用SkipList来对倒排列表进行快速查找。
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;

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

总结

C#版的一个实现 https://github.com/kencausey/SkipList

 

探索C#之系列导航