一、跳表的定义
跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要o(log n)平均时间)，并且对并发算法友好。
skiplist(跳表）是一种可以代替平衡树的数据结构，默认是按照key值升序的。skiplist让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。
在java的api中已经有了实现：分别是:
concurrentskiplistmap(在功能上对应hashtable、hashmap、treemap) ；
concurrentskiplistset(在功能上对应hashset).
确切来说，skiplist更像java中的treemap，treemap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到o(log n)。
hashmap是基于散列表实现的，时间复杂度平均能达到o(1)。concurrentskiplistmap是基于跳表实现的，时间复杂度平均能达到o(log n)。
skiplist的性质
(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序
(3) 最底层(level 1)的链表包含所有元素。
(4) 如果一个元素出现在level i 的链表中，则它在level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
图示：
二、跳表搜索
例子：查找元素 117
(1) 比较 21， 比 21 大，往后面找
(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
(4) 比较 85， 比 85 大，从后面找
(5) 比较 117， 等于 117， 找到了节点。
三、插入元素
先确定该元素要占据的层数 k（采用丢硬币的方式，这完全是随机的）然后在 level 1 … level k 各个层的链表都插入元素。
例子：插入 119， k = 2
如果 k 大于链表的层数，则要添加新的层。
例子：插入 119， k = 4
四、删除元素
从上往下删除
五、完整代码
到此这篇关于java数据结构之实现跳表的文章就介绍到这了,更多相关java跳表内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！
