江苏龙网

  1. 首页 > 人文 > >

快手视频|用java实现跳表SkipList


快手视频|用java实现跳表SkipList
文章图片
快手视频|用java实现跳表SkipList
文章图片
快手视频|用java实现跳表SkipList
文章图片
快手视频|用java实现跳表SkipList
前一篇文章学习了跳表的原理 ， 今天就来用Java来实现它 。
跳表原理回顾上一篇总结的最终跳表的结构如下图：
整体来看像是一个由节点组成的网 ， 每个节点有下节点和右节点 ， 最右的没有右节点 ， 最下面的没有下节点 ， 节点一层一层往下递增 。 接下来就看实现源码 。
跳表基本属性实现类的基本属性如下图：
SkipList类接受实现Comparable接口的参数 。 属性详解如下：
UP_RATE表示升级几率；
head属性就是跳表整个结构的最开始的节点 ， 比如最开始那张图中就表示最左上角的节点；
stack用于在跳表搜索过程中下层时的节点 ， 比如上图中会保存1 ， 8 ， 11 ， 这个数据在跳表的增加和删除的时候有大用处 。
构造方法初始化head ， 保存的值为null；
内部类Node表示跳表中各个节点 ， value表示节点中保存的值 ， down和right表示节点的下节点和右节点；
这次实现与总结图有所不同 ， 我们在最开始初始化了一个value为null的头结点 ， 并且整个跳表网最左侧的value都是null ， 表示每列的头结点 。
跳表的查询实现直接上实现源码 ， 源码如下图：
findPredecessor方法是跳表中很重要的方法 ， 所以首先来分析方法流程：
1、获取到头节点q以及头节点的右节点r；
2、如果value大于r的value则：q=rr=right（往右遍历 ， 返回第一步）；
3、如果value小于等于r的值则：d=q.downq=dr=d.right(往下遍历返回第一步)；
4、如果q.down等于null则返回q;
流程简析完成 ， 主要过程是往右遍历直到右节点为null或者右节点的值大于等于value ， 然后往下遍历 ， 然后又往右 ， 然后又往下 ， 直到下节点为null 。
findPredecessor的作用是找到一个节点（前置节点） ， 前置节点的值小于value或为null（头节点） ， 右节点大于等于value或者右节点为null（跳表中没有比value更大的值） 。
findPredecessor找到的节点的值小于value ， 而右节点要么等于null要么value大于等于 ， 所以search方法就很简单了 ， 只要验证右节点的值就能判断value是否存在 。
跳表的添加实现直接上添加方法源码 ， 源码如下图：
添加方法首先验证是否已经存在 ， 已经存在就直接返回了 ， findPredecessor返回的preNode表示前置节点 。 如果preNode的right的值不等于value ， 则new一个节点node保存value ， 把preNode的right给node在把node加到preNode节点中 ， 节点node就加到最底层的链表上了 。 接下来就是节点升级的过程了 。
for循环就是升级的过程 ， 产生的随机数与0.5比较判断是否升级 ， 不升级就跳出循环 ， 升级结束 ， 否则就升级 。
如果升级则需要在new一个节点node保存value ， 然后老的node作为新node的下级节点 ， 接下来就是怎么样把新节点加到上一层的链表中 ， 最开始留的一个栈stack就派上用场了 ， 在findPredecessor每次下沉的时候都保存下沉点的节点 。 所以stack保存着value在上面几层中的前置节点 ， 所以一层pop出来然后把新节点链接上就行 。


推荐阅读


上一篇：华为|作为一个普通人，赚钱真的难了

下一篇：阿里巴巴|阿里云「Teambition 网盘」还有微信小程序