作者：蘑菇先生
网址：http://www.cnblogs.com/mushroom/p/4605690.html
点击“阅读原文”可查看本文网页版
基本介绍
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正确返回、否则不存在。
更新
搜索到值后更新：
