跳跃表

跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

ConcurrentSkipListSet、ConcurrentSkipListMap没有使用锁，所有操作都是可以并行的，包括写。

跳跃表是基于链表实现的，在链表的基础上加了多层索引结构。

举个简单的例子：

2    3    6    7    9    12    17    19    21    25

图中最下面一层就是最基本的单向有序链表，虽然有序，但是与数组不同，我们不能直接能通过索引定位，不能进行二分查找。

    为了快速查找，跳跃表就有了多层索引结构，如3和7。高层的索引节点少，低层的索引节点多。统计概率上，第一层索引节点是实际元素的1/2，第二层索引节点是第一层的1/2，逐层减半，但并不是绝对的、有随机性，只是大致如此。

    每个索引节点有两个指针，一个向右，指向同层下一个节点；一个向下，指向下层节点。

    有了这个结构，就可以大至进行二分查找了。查找元素总是从最高层开始，将待查值与下一个索引节点进行比较，如果大于索引节点，就向右移动继续比较，如果小于索引节点，则向下移动到下一层进行比较，如下图描述了查找值6和21的过程。

如值6的查找过程：

与7相比，小于7；

向下移动与3相比较，大于3；

向右与6相比，找到6；

如值21的查找过程：

与7比较，大于7；

向右移动与19相比，大于19；

向右移动与25相比，小于25；

向下层与右相比较，找到21；

查找性能与二叉树类似O(log(n)) ，这个结构的保持也与二叉树类似，在更新过程中保持。

保存到基本链表，找到待插入的位置。

更新索引层。

插入元素、往链表写入一个元素2，元素2会往几层索引上写是一个概率。

    如我们定义跳表的最高层为MAX=2，那么任意一个元素写入一层索引的概率1/2，写入二层索引的概率为1/4。

删除元素、直接删除元素，然后调整一下删除元素后的指针即可。跟普通的链表删除操作完全一样。

    对于Java ConcurrentSkipListMap，不是直接进行真正的删除操作，为了避免并发冲突，有一个复杂的标记过程，在内部遍历操作过程中进行真正的删除。

Java ConcurrentSkipListMap的实现非常复杂，有兴趣的同学可以参考其源码，具体我们就不再深入探讨。

如果不需要并发，可以以一种更高效的结果，把数据与所有层的索引都放在一个节点中。

Redis中也有对跳表的实现，有兴趣的同学也可以研究一下。

https://sourcegraph.com/github.com/antirez/redis@fe43406/-/blob/src/server.h#L795:9

码农闲话