内容简介：Life is the art of drawing without an eraser.Obstacles are those frightful things you see when you take your eyes off your goal. 生活是一门没有橡皮擦的绘画艺术。当你看到众多困难的时候，通常是你忘记目标的时候。本文主要分享了一种各方面都十分优秀的动态数据结构---跳表。实现不是目的，重要的是了解它的实现原理和思想，开拓自己的视野。所有源码均已上传至github：
Life is the art of drawing without an eraser.Obstacles are those frightful things you see when you take your eyes off your goal. 生活是一门没有橡皮擦的绘画艺术。当你看到众多困难的时候，通常是你忘记目标的时候。
本文主要分享了一种各方面都十分优秀的动态数据结构---跳表。实现不是目的，重要的是了解它的实现原理和思想，开拓自己的视野。所有源码均已上传至github：
定义
跳表是快速查询一个有序连续元素的数据链表。它虽然是链表，但是它集数组和链表与之所长，跳表的平均查找和插入时间复杂度都是O(log n)，优于普通队列的O(n)，非常高效。当然有利就有弊，相对而言，它因为建立了多级索引，因此非常耗内存（O(n)）。它的查找借鉴了二分查找。利用空间换时间，根据随机数建立多级索引。
总结来讲 跳表 = 链表 + 多级索引
举例
比如有一个链表存了1-100个正整数，我想快速找到67，首先建立一级索引，取中间值50，这样他的一级索引为{1,50,100}，这样可以确定67在50-100之间，但是这样还是不好查找，所以再建立二级索引{1,25,50,75,100}，，，就这样以此类推，不断地建立索引，缩小查找范围，可以快速定位。
redis的有序集合也用到了跳表。
呢为什么 Redis 用跳表而不是红黑树呢？
答：首先Redis的有序集合有插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。并且跳表的代码更容易实现，可读性高，它不像红黑树那么复杂，它更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
实现
跳表结构
这里，默认-1 数据不存在，maxLevel为0级，forwards为多级索引,并且重写了它的toString方法，为了便于测试，查看日志
该用法随机了level次，主要是用来防止伪随机的，当随机出奇数的时候，level+1
插入
跳表关键在于插入，理解了插入方法的实现，删除和查找即一通百通。
第一个循环比较好理解，构建索引
第二个for循环，根据level倒序遍历，查找头链表的多级索引中满足索引中的值小于插入的值的节点，更新多级索引
第三个for循环更新头链表的多级索引。
over
删除
删除的第一个for循环和新增的呢个循环作用是一样的
第二个循环类似链表的常规删除 node.next = node.next.next
查找
该方法是倒序遍历多级索引，不断缩小范围，查找到相对应的索引等级，然后找
forwards[0].data == data 即可
测试结果
根据打印结果，它的结构大致是这样的
根据查找的打印结果可以看出，level最高级为8级，查到第5级就能查出结果，非常高效。
end
您的点赞和关注是对我最大的支持，谢谢！
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
函数式算法设计珠玑
Richard Bird / 苏统华、孙芳媛、郝文超、徐琴 / 机械工业出版社 / 2017-4-1 / 69.00
本书采用完全崭新的方式介绍算法设计。全书由30个珠玑构成，每个珠玑单独列为一章，用于解决一个特定编程问题。这些问题的出处五花八门，有的来自游戏或拼图，有的是有趣的组合任务，还有的是散落于数据压缩及字串匹配等领域的更为熟悉的算法。每个珠玑以使用函数式编程语言Haskell对问题进行描述作为开始，每个解答均是诉诸于函数式编程法则从问题表述中计算得到。本书适用于那些喜欢学习算法设计思想的函数式编程人员、......一起来看看 《函数式算法设计珠玑》 这本书的介绍吧!
