java跳表使用场景,跳跃表原理和实现

　　跳转表的全称叫做跳转表，是一种随机化的数据结构。本质上，它是一个可以进行二进制搜索的有序链表。跳转表在原有的有序列表上增加多级索引，通过索引实现快速搜索。跳表不仅可以提高搜索性能，还可以提高插入和删除性能。redis中的有序集是通过跳表实现的，面试中经常被问到。

　　这里，我们的原始数据的数量为n=10，以k=2的间隔建立索引，这样第一层索引为10/2=5，第二层索引为10/2 ^ 2=3，第三层索引为10/2 ^ 3=2，第四层索引为10/2 ^ 4=1。根据上图，我们来分析一下。跳转表的结构是一棵树(原始数据层除外)。树的左指针指向下一个链表的对应节点，右指针指向当前链表的下一个节点。这棵树的高度是log(n)。对于每一层，最大比较次数为k，所以时间复杂度为O(k*log(n))，k为常数项。所以跳转表的查询时间复杂度是因为需要额外的空间来存储索引，典型的是用空间换时间，空间复杂度为O(n)。

　　接下来，我们将自己实现一个跳转表：

　　节点结构的定义：根据跳转表结构，一个节点首先需要一个值存储当前的nodevalue，一个next指针指向同一层的下一个节点，一个nodeValue指针指向下一层对应的节点。但是，这里为了方便插入和删除，引入了prev指针，指向同一层中的前一个节点。

　　类节点{//当前节点值私有整数值；//当前节点所属的链表中的下一个节点是私有节点next；//当前节点所属的链表上的最后一个节点是private Node prev//当前节点指向的另一个索引链表/原始值链表节点私有节点nodeValueNode(整数值){ this.value=value}}}初始化一个跳表：跳表的建立需要以数据排序为基础，然后在下一层的基础上自下而上每间隔k生成当前层的节点。新生成的节点需要与当前层的前一个节点连接，并指向生成它的下一层的节点。

　　/* * *原始数据链表*/私有节点头；/* * *最终跳转表结构：保存索引链表和原链表*/private ListNode index list；/* * *表面跳转次数*/private int level；/* * * Initialize */public void init(){//前导节点的链表，方便操作head=new Node(-1)；head.next=headindexList=new ArrayList()；级别=0；}/* * *初始化跳转表* @param k interval * @param nums原始数据(已排序)*/public void init (int k，int[]nums){//初始化数据链表节点temp=headfor(int num : nums){ Node cur=new Node(num)；cur.prev=temptemp.next=curtemp=temp.next}//新节点保存(最底层)indexlist . add(head)；//循环生成索引结构，结束条件，当层只有一个元素temp=head.nextWhile (true) {//当前链表中的什么元素int I=0；//生成另一个长度int size=0的链表；Node indexNode=新节点(-1)；index node . next=index node；Node indexNodeTemp=indexNodewhile (null！=temp) {//interval k生成节点if(I % k==0){ node curnode=new node(temp . value)；curNode.nodeValue=tempcurNode.prev=indexNodeTempindexNodeTemp.next=curNodeindexNodeTemp=indexNodeTemp . next；尺寸；}我；temp=temp.next}

　　 indexList.add(indexNode); temp = indexNode.next; //当生成的索引链表仅1时不需要再继续生成 if (size == 1) { break; } } level = indexList.size();}从跳表中查找元素：从最顶层索引链表开始查找，找到第一个大于当前节点的元素，则需要查找的元素在当前节点与之前节点之间，则从当前节点的上一个节点prev往下nodevalue继续进行查找，直到当前节点值与查找值相等，则直接返回当前节点，返回的节点可能是索引节点，也可能是原始数据节点，如果需要找到原始数据节点，则通过nodeValue继续往下找。

/** * 是否存在num * @param num * @return */public boolean hasNum(int num) { Node result = this.findNum(num); return null != result;}/** * 查找num（返回的可能是索引，也可能是原始数据，根据nodeValue可以判断，也可以找到原始数据） * @param num */public Node findNum(int num) { //跳表结构indexList是数据-》第一层索引-》第二层索引-》。。。。 //1.直接匹配到 //2.找到第一个大于当前元素的数，找前一个 Node node = indexList.get(indexList.size() - 1).next; Node last = null; while (null != node) { if (node.value == num) { //已经找到元素 return node; } if (node.value > num) { if (null == last) { //比最小值还小 return null; } //找到了第一个大于num的索引node //到下一层去继续找 node = last.nodeValue; last = null; continue; } last = node; node = null != node.next ? node.next : node.nodeValue; } return null;}

删除节点：首先通过上面的查找方法找到目标节点，如果目标节点是索引值，则需要从当前索引层，层层往下删除包括原始数据链表，如果是原始数据值，则直接删除，暂不调整。

/** * 构建索引时：自底向上逐层构建，如果索引需要删除（当两个索引之间没有任何数据时候，删除） * @param num * @return */public boolean remove(int num) { Node node = this.findNum(num); if (null == node) { //不需要移除 return false; } if (null == node.nodeValue) { //数据链表，可以直接移除 //是否最后一个节点 if (null == node.next) { node.prev.next = null; return true; } node.next.prev = node.prev; node.prev.next = node.next; return true; } //当前在索引上，自上而下删除索引及数据 while (null != node) { Node cur = node.nodeValue; if (null == node.next) { node.prev.next = null; } else { node.next.prev = node.prev; node.prev.next = node.next; } node = cur; } return true;}

新增节点：新增节点时候，如果不对索引进行调整，极端情况下，每次新增的节点都在之前第一层两个节点之间，当这之间的链表越变越长，时间复杂度直接退化为O(n)，所以需要同时新增索引，维持跳表的高效性。但是我们如何新增，有一个方法就是，在新增节点时，随机选择k，即第k级索引，从1～k新增索引。

/** * 首先需要查找插入位置，如果比最小的还小，直接在前面插入 * 否则需要从最顶级一直查找到数据链表，找到插入位置，插入，在查找的过程中，就可以开始插入索引节点， * 从上往下进行插入 * @param num */public void add(int num) { int k = this.generatorLevelK(); //寻找插入点的过程和查找过程基本一致 //顶级索引链表 Node node = indexList.get(indexList.size() - 1).next; int index = 1; while (null != node) { //找到第一个node.value >= num的元素，在前面插入 if (node.value >= num) { //已经找到,前插 if (index >= k) { Node newNode = new Node(num); Node temp = node.prev; newNode.next = temp.next; temp.next.prev = newNode; newNode.prev = temp; temp.next = newNode; } //找的时候往后面找的，但是当前已经先于num了，下一次再往后面找，就出现问题 if (null == node.prev.prev) { //第一个节点就符合条件 node = node.nodeValue; continue; } node = node.prev.nodeValue; ++ index; continue; } //没有找到，但是当前已经是链表最后一个元素了 if (null == node.next) { if (index >= k) { Node newNode = new Node(num); newNode.prev = node; node.next = newNode; } if (null == node.prev.prev) { //第一个节点就符合条件 node = node.nodeValue; continue; } node = node.prev.nodeValue; ++ index; continue; } node = node.next; }}private int generatorLevelK() { Random random = new Random(); return random.nextInt(level);}

至此，我们实现了一个跳表的定义，初始化，查找，节点新增与删除。

　　到此这篇关于Java实现跳跃表的示例详解的文章就介绍到这了,更多相关Java跳跃表内容请搜索盛行IT以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。