内容简介: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
您的点赞和关注是对我最大的支持,谢谢!
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Ruby on Rails社区网站开发
布拉德伯纳 / 柳靖 / 2008-10 / 55.00元
《Ruby on Rails社区网站开发》全面探讨创建完整社区网站的开发过程。首先介绍开发一个内容简单的管理系统,之后逐渐添加新特性,以创建更完整的、使用Ruby on Rails 的Web 2.0 社区网站。还给出了开发和测试中的一些建议和提示,同时指导如何使网站更生动以及维护得更好。《Ruby on Rails社区网站开发》也探讨了如何与Flickr 、Google Maps 等其他平台集成,......一起来看看 《Ruby on Rails社区网站开发》 这本书的介绍吧!