探索c#之跳跃表(SkipList) 2015-06-28 16:25 by 蘑菇先生, ... 阅读, ... 评论, 收藏, 编辑 阅读目录：
基本介绍算法思想演化步骤实现细节总结基本介绍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#之系列导航
