比红黑树更快的跳表到底是什么数据结构？如何实现？

　　前言
　　在头条创作了一个月左右的时间，收获了50粉丝，很是开心，我会把数据结构与算法的文章更新到底，第一次看我文章的同仁如果觉得不错的话就关注一下我哦，你的支持就是我创作的动力。
　　时间复杂度和空间复杂度详解（初学者请点击）：传送门
　　一、什么是跳表
　　我们在之前介绍了十分优秀的二分查找算法，但是它只能作用于有序数组上，查找起来比较方便，但是数组中插入和删除元素是比较麻烦的；那么有没有办法让二分查找也能作用于有序链表上，从而达到查找、插入和删除元素都十分的快速呢？
　　对于普通的有序列表来说，当然不能实现我们的目标，如下查找的时间复杂度为O（n）；
　　原始有序单链表
　　我们可以基于原始链表建立一个索引层，比如每两个节点提取一个节点到索引层：
　　带一级索引的跳表
　　如此，两种数据结构我们查找元素16的比较次数分别为10次和8次，确实能提高查询速度；我们更近一步，再次建立第二级索引：
　　带二级索引的跳表带二级索引的跳表
　　此时查找元素16比较的次数只需要比较7次即可；
　　如果在大数据量的有序链表中，我们建立很多层索引，使得最高层索引只有两个节点，那么就实现了类似二分查找的算法思想，此时这种数据结构就被成为跳表。二、跳表性能分析2。1时间复杂度
　　假设有序链表总节点个数为n，我们建立索引时每两个节点提取一个索引节点；那么第一级索引共有n2个节点；
　　第k级索引共有（n2k）个节点，假设k为最高级索引，为2个节点，那么2（n2k），n2（k1），klogn1，如果原始链表也算进去的话，klogn正好是整个数据结构的高度。
　　假设每一层需要遍历m个节点，那么时间复杂度就可以表示为O（mlogn），但是推断m是常量级别的，因此可以忽略，那么整个查找过程时间复杂度就是O（logn），竟然和二分查找是一样的高效！2。2空间复杂度
　　第一级索引需要n2个节点，第二级需要n22个节点，依次类推，第k级索引需要的节点个数为n2k，这正好是一个等比数列，等比数列求和的结果是n2，所以空间复杂度为O（n），这是一个以空间换时间的策略；
　　我们可以每3个节点或者每4个节点往上提取一个索引节点，如此可以适当减少需要的额外空间，但是空间复杂度仍然为O（n）；如果有序链表存储的是大对象，那么索引节点中无需存放整个大对象，只要存储对象的指针即可，所以此时空间复杂度就显得不那么重要了；2。3跳表的插入和删除
　　跳表因为是顺序链表，所以真正插入和删除的时间复杂度都是O（1），但是找到需要插入节点的位置或者找到待删除的节点时间复杂度为O（logn）；
　　跳表在删除的时候，除了需要删除原始有序链表中的节点，还需要同步删除k级索引中的全部该索引节点；
　　跳表在插入元素式，极端情况下会导致两个索引节点中存在大量的原始节点，时间效率极有可能会退化为单链表的O（n），所以需要动态地平衡和更新k级索引节点；三、跳表使用场景
　　Redis在存储有序集合的时候就用到了跳表散列表的数据结构，跳表和红黑树相比，插入、删除、查找的时间复杂度相同，但是跳表在按照区间查找时明显具有效率优势，而且跳表实现起来比红黑树要简单易懂，不容易出错。
　　红黑树等常用数据结构在程序语言中都是封装好的，我们想用的话直接拿来用即可，比如HashMap，但是跳表却没有对应的封装好的数据结构，想用的话开发者必须自己去实现。四、代码实现跳表Skiplist以及优化
　　代码来源于极客时间《数据结构和算法之美》
　　github地址：https：github。comwangzheng0822algo（数据结构和算法必知必会的50个代码实现）4。1作者王争给出的跳表实现方式跳表的一种实现方法。跳表中存储的是正整数，并且存储的是不重复的。publicclassSkipList｛privatestaticfinalfloatSKIPLISTP0。5f；privatestaticfinalintMAXLEVEL16；privateintlevelCount1；privateNodeheadnewNode（）；带头链表publicNodefind（intvalue）｛Nfor（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛pp。forwards〔i〕；｝｝if（p。forwards〔0〕！nullp。forwards〔0〕。datavalue）｛returnp。forwards〔0〕；｝else｛｝｝publicvoidinsert（intvalue）｛intlevelrandomLevel（）；NodenewNodenewNode（）；newNode。newNode。maxLNodeupdate〔〕newNode〔level〕；for（inti0；i）｛update〔i〕｝recordeverylevellargestvaluewhichsmallerthaninsertvalueinupdate〔〕Nfor（intilevel1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛pp。forwards〔i〕；｝update〔i〕p；useupdatesavenodeinsearchpath｝insearchpathnodenextnodebecomenewnodeforwords（next）for（inti0；i）｛newNode。forwards〔i〕update〔i〕。forwards〔i〕；update〔i〕。forwards〔i〕newN｝updatenodehightif（levelCountlevel）levelC｝publicvoiddelete（intvalue）｛Node〔〕updatenewNode〔levelCount〕；Nfor（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛pp。forwards〔i〕；｝update〔i〕p；｝if（p。forwards〔0〕！nullp。forwards〔0〕。datavalue）｛for（intilevelCount1；i0；i）｛if（update〔i〕。forwards〔i〕！nullupdate〔i〕。forwards〔i〕。datavalue）｛update〔i〕。forwards〔i〕update〔i〕。forwards〔i〕。forwards〔i〕；｝｝｝while（levelCount1head。forwards〔levelCount〕null）｛levelC｝｝理论来讲，一级索引中元素个数应该占原始数据的50，二级索引中元素个数占25，三级索引12。5，一直到最顶层。因为这里每一层的晋升概率是50。对于每一个新插入的节点，都需要调用randomLevel生成一个合理的层数。该randomLevel方法会随机生成1MAXLEVEL之间的数，且：50的概率返回125的概率返回212。5的概率返回3。。。privateintrandomLevel（）｛intlevel1；while（Math。random（）SKIPLISTPlevelMAXLEVEL）level1；｝publicvoidprintAll（）｛Nwhile（p。forwards〔0〕！null）｛System。out。print（p。forwards〔0〕）；pp。forwards〔0〕；｝System。out。println（）；｝publicclassNode｛privateintdata1；privateNodeforwards〔〕newNode〔MAXLEVEL〕；privateintmaxLevel0；OverridepublicStringtoString（）｛StringBuilderbuildernewStringBuilder（）；builder。append（｛data：）；builder。append（data）；builder。append（；levels：）；builder。append（maxLevel）；builder。append（｝）；returnbuilder。toString（）；｝｝｝4。2作者ldb基于王争的代码给出的优化importjava。util。R1，跳表的一种实现方法，用于练习。跳表中存储的是正整数，并且存储的是不重复的。2，本类是参考作者zheng，自己学习，优化了添加方法3，看完这个，我觉得再看ConcurrentSkipListMap源码，会有很大收获publicclassSkipList2｛privatestaticfinalintMAXLEVEL16；privateintlevelCount1；带头链表privateNodeheadnewNode（MAXLEVEL）；privateRandomrnewRandom（）；publicNodefind（intvalue）｛N从最大层开始查找，找到前一节点，通过i，移动到下层再开始查找for（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛找到前一节点pp。forwards〔i〕；｝｝if（p。forwards〔0〕！nullp。forwards〔0〕。datavalue）｛returnp。forwards〔0〕；｝else｛｝｝优化了作者zheng的插入方法paramvalue值publicvoidinsert（intvalue）｛intlevelhead。forwards〔0〕null？1：randomLevel（）；每次只增加一层，如果条件满足if（levellevelCount）｛levellevelC｝NodenewNodenewNode（level）；newNode。Nodeupdate〔〕newNode〔level〕；for（inti0；i）｛update〔i〕｝N从最大层开始查找，找到前一节点，通过i，移动到下层再开始查找for（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛找到前一节点pp。forwards〔i〕；｝levelCount会level，所以加上判断if（leveli）｛update〔i〕p；｝｝for（inti0；i）｛newNode。forwards〔i〕update〔i〕。forwards〔i〕；update〔i〕。forwards〔i〕newN｝｝优化了作者zheng的插入方法2paramvalue值publicvoidinsert2（intvalue）｛intlevelhead。forwards〔0〕null？1：randomLevel（）；每次只增加一层，如果条件满足if（levellevelCount）｛levellevelC｝NodenewNodenewNode（level）；newNode。N从最大层开始查找，找到前一节点，通过i，移动到下层再开始查找for（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛找到前一节点pp。forwards〔i〕；｝levelCount会level，所以加上判断if（leveli）｛if（p。forwards〔i〕null）｛p。forwards〔i〕newN｝else｛Nodenextp。forwards〔i〕；p。forwards〔i〕newNnewNode。forwards〔i〕｝｝｝｝作者zheng的插入方法，未优化前，优化后参见上面insert（）paramvalueparamlevel0表示随机层数，不为0，表示指定层数，指定层数可以让每次打印结果不变动，这里是为了便于学习理解publicvoidinsert（intvalue，intlevel）｛随机一个层数if（level0）｛levelrandomLevel（）；｝创建新节点NodenewNodenewNode（level）；newNode。表示从最大层到低层，都要有节点数据newNode。maxL记录要更新的层数，表示新节点要更新到哪几层Nodeupdate〔〕newNode〔level〕；for（inti0；i）｛update〔i〕｝1，说明：层是从下到上的，这里最下层编号是0，最上层编号是152，这里没有从已有数据最大层（编号最大）开始找，（而是随机层的最大层）导致有些问题。如果数据量为1亿，随机level1，那么插入时间复杂度为O（n）Nfor（intilevel1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛pp。forwards〔i〕；｝这里update〔i〕表示当前层节点的前一节点，因为要找到前一节点，才好插入数据update〔i〕p；｝将每一层节点和后面节点关联for（inti0；i）｛记录当前层节点后面节点指针newNode。forwards〔i〕update〔i〕。forwards〔i〕；前一个节点的指针，指向当前节点update〔i〕。forwards〔i〕newN｝更新层高if（levelCountlevel）levelC｝publicvoiddelete（intvalue）｛Node〔〕updatenewNode〔levelCount〕；Nfor（intilevelCount1；i0；i）｛while（p。forwards〔i〕！nullp。forwards〔i〕。datavalue）｛pp。forwards〔i〕；｝update〔i〕p；｝if（p。forwards〔0〕！nullp。forwards〔0〕。datavalue）｛for（intilevelCount1；i0；i）｛if（update〔i〕。forwards〔i〕！nullupdate〔i〕。forwards〔i〕。datavalue）｛update〔i〕。forwards〔i〕update〔i〕。forwards〔i〕。forwards〔i〕；｝｝｝｝随机level次，如果是奇数层数1，防止伪随机returnprivateintrandomLevel（）｛intlevel1；for（inti1；iMAXLEVEL；i）｛if（r。nextInt（）21）｛｝｝｝打印每个节点数据和最大层数publicvoidprintAll（）｛Nwhile（p。forwards〔0〕！null）｛System。out。print（p。forwards〔0〕）；pp。forwards〔0〕；｝System。out。println（）；｝打印所有数据publicvoidprintAllbeautiful（）｛NNode〔〕cp。Node〔〕intmaxLevelc。for（intimaxLevel1；i0；i）｛do｛System。out。print（（d〔i〕！null？d〔i〕。data：null）：i）；｝while（d〔i〕！null（dd〔i〕。forwards）〔i〕！null）；System。out。println（）；｝｝跳表的节点，每个节点记录了当前节点数据和所在层数数据publicclassNode｛privateintdata1；表示当前节点位置的下一个节点所有层的数据，从上层切换到下层，就是数组下标1，forwards〔3〕表示当前节点在第三层的下一个节点。privateNodeforwards〔〕；这个值其实可以不用，看优化insert（）privateintmaxLevel0；publicNode（intlevel）｛forwardsnewNode〔level〕；｝OverridepublicStringtoString（）｛StringBuilderbuildernewStringBuilder（）；builder。append（｛data：）；builder。append（data）；builder。append（；levels：）；builder。append（maxLevel）；builder。append（｝）；returnbuilder。toString（）；｝｝publicstaticvoidmain（String〔〕args）｛SkipList2listnewSkipList2（）；list。insert（1，3）；list。insert（2，3）；list。insert（3，2）；list。insert（4，4）；list。insert（5，10）；list。insert（6，4）；list。insert（8，5）；list。insert（7，4）；list。printAllbeautiful（）；list。printAll（）；结果如下：null：15null：14null：13null：12null：11null：105：95：85：75：65：55：48：44：35：36：37：38：31：22：24：25：26：27：28：21：12：13：14：15：16：17：18：11：02：03：04：05：06：07：08：0｛data：1；levels：3｝｛data：2；levels：3｝｛data：3；levels：2｝｛data：4；levels：4｝｛data：5；levels：10｝｛data：6；levels：4｝｛data：7；levels：4｝｛data：8；levels：5｝优化后insert（）SkipList2list2newSkipList2（）；list2。insert2（1）；list2。insert2（2）；list2。insert2（6）；list2。insert2（7）；list2。insert2（8）；list2。insert2（3）；list2。insert2（4）；list2。insert2（5）；System。out。println（）；list2。printAllbeautiful（）；｝｝