Shulou(Shulou.com)06/01 Report--

Most people don't understand the knowledge points of this article "Java Table Jumping Method Example Analysis", so Xiaobian summarizes the following contents for everyone. The contents are detailed, the steps are clear, and they have certain reference value. I hope everyone can gain something after reading this article. Let's take a look at this article "Java Table Jumping Method Example Analysis".

I. Definition of skip table

A jump table is a randomized data structure based on parallel linked lists, comparable in efficiency to binary lookup trees (requiring O(log n) average time for most operations), and friendly to concurrency algorithms.

SkipList is a data structure that can replace balanced trees. By default, it is in ascending order of Key value. SkipList allows sorted data to be distributed in a multi-level linked list, and determines whether a data climbs upward or not with a random number of 0-1. Through an algorithm of "space for time," a forward pointer is added to each node, and some nodes that are impossible to be involved can be ignored when inserting, deleting, and searching, thus improving efficiency.

There are already implementations in Java APIs:

ConcurrentSkipListMap(functionally corresponding to HashTable, HashMap, TreeMap) ;

ConcurrentSkipListSet(functionally corresponds to HashSet).

To be precise, SkipList is more like TreeMap in Java, which is implemented based on a red-black tree (a self-balancing binary search tree) with an average time complexity of O(log n).

HashMap is based on hash table implementation, time complexity can reach O(1) on average. ConcurrentSkipListMap is implemented based on the skip table, and the average time complexity can reach O(log n).

Properties of SkipList

(1)It consists of many layers, and the level is randomly generated by a certain probability.

(2)Each layer is an ordered list, default is ascending

(3)The list at the lowest level (Level 1) contains all elements.

(4)If an element appears in a list at Level i, it appears in all lists below Level i.

(5)Each node contains two pointers, one to the next element in the same list and one to the element one level below.

II. Skip list search

Example: Find element 117

(1)Compare 21. Bigger than 21. Go back.

(2)Compare 37, larger than 37, smaller than the maximum value of the linked list, starting from the bottom of 37

(3)Compare 71, larger than 71, smaller than the maximum value of the linked list, starting from the lower level of 71

(4)Compare 85. Bigger than 85. Look behind.

(5)Compare 117, equals 117, finds the node.

/** * Find the node immediately preceding val, i.e. the element immediately preceding the first occurrence of the same row at the highest level. */ private Node findPreNode(int val){ Node first = head.getFirst();//Start searching from the topmost head node while (first!= null){ if(first.data

< val && first.next.data >

val){ if(first.down == null){break;} first = first.down;//search down }else if(first.data

< val && first.next.data < val){ first = first.next;//往右搜索 }else if(first.data < val && first.next.data == val){ return first; } } return null; }三、插入元素 先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）然后在 Level 1 … Level K 各个层的链表都插入元素。 /** * 随机获取高度,（相当于抛硬币连续出现正面的次数） * @return */ private int getLeavel(){ int k = 0; while(rd.nextInt(2) == 1){ k ++; } return k; } 如果 K 大于链表的层数，则要添加新的层。 例子：插入 119， K = 4 四、删除元素 从上往下删除 /** * 向跳表中删除元素，从上往下删除，每次找到所在行的前一个节点 * @param val * @return 如果找不到 待删除元素 则返回 false */ boolean delete(int val){ Node lindPre = findPreNode(val);//找到待删除元素的最上层的前一个节点 if(lindPre == null){ return false; } while (true){ lindPre.next = lindPre.next.next; lindPre = lindPre.down;//往下遍历，直到最底下一层 if(lindPre==null){break;}//跳出循环 //找到待删除元素所在行的前一个节点 while (lindPre.next.data != val){ lindPre = lindPre.next; } } size--; return true; }五、完整代码package com.longstudy.algorithm;import java.util.LinkedList;import java.util.Random;/** * @anthor longzx * @create 2021 05 21 15:20 * @Description 跳表抽象数据结构 **/public class SkipList { //使用头插法插入新节点 LinkedList head;//每一行的头结点，相当于跳表的第一列， 默认设置为 Integer.MIN_VALUE LinkedList tail;//每一行大最后一个节点，相当与跳表的最后一列 Integer.MAX_VALUE Random rd ;//用于生成随机数数 int hight=-1;//当前跳表的层数，hight从0开始,初始值为-1， int size;//所有的节点数 public SkipList(){ this.head = new LinkedList(); this.tail = new LinkedList(); this.rd = new Random(); } public static void main(String[] args) { SkipList sl = new SkipList(); int[] arr = new int[500]; for (int i = 0; i < 500; i++) { arr[i] = (int)(Math.random()*600); } sl.arrayToSkipList(arr); sl.showSkipList(); System.out.println(sl.find(100)); System.out.println(sl.find(50)); System.out.println(sl.find(99)); System.out.println("清空跳表"); sl.clear(); sl.showSkipList(); } /** * 节点内部类 */ private class Node{ int data;//存放数据 Node next;//指向右边节点 Node down; //指向下面节点 int level;//当前所在的层 public Node(){} public Node(int data,int level){ this.data = data; this.level = level; } public Node(int data,int level,Node next,Node down){ this.data = data; this.level = level; this.next = next; this.down =down; } } /** * 向跳表中加添加元素 * 是否考虑重复元素？？？？？？？？？？ * @param val * @return */ boolean add(int val){ int k = getLeavel();//获得层数 //层数比当前大的时候，增加新的层 if(k>

hight){ int i = k-hight; for (int j = 1; j 0){ h.down = head.getFirst();//down } Node t = new Node(Integer.MAX_VALUE, height +j);//tail if(tail.size()>0){ t.down = tail.getFirst(); } h.next =t;//head to tail tail.addFirst(t); head.addFirst(h); } height =k;//Modify the current number of skip levels } return addFromK(val,k);//Add element from kth layer } /** * Add element from kth layer of jump list * called by the add(int val) method * */ boolean addFromK(int val,int k){ Node preNewNode = new Node(val,k); Node preLine = head.get(high-k);//Get the head node of the layer where the new node is located while (preLine != null){ while (preLine.next.data

< val){//往右搜索 preLine = preLine.next; } preNewNode.next = preLine.next; preLine.next = preNewNode; //如果不是第一层，则建立下一层的新节点 if (preNewNode.level>

0){ Node newNode = new Node(val,preNewNode.level-1); preNewNode.down = newNode;//往下指向新节点 preNewNode = newNode; } //往下层建立新节点 preLine = preLine.down; } size++;//跳表中的元素数量加一 return true; } /** * 随机获取高度,（相当于抛硬币连续出现正面的次数） * @return */ private int getLeavel(){ int k = 0; while(rd.nextInt(2) == 1){ k ++; } return k; } /** * 向跳表中删除元素，从上往下删除，每次找到所在行的前一个节点 * @param val * @return 如果找不到 待删除元素 则返回 false */ boolean delete(int val){ Node lindPre = findPreNode(val);//找到待删除元素的最上层的前一个节点 if(lindPre == null){ return false; } while (true){ lindPre.next = lindPre.next.next; lindPre = lindPre.down;//往下遍历，直到最底下一层 if(lindPre==null){break;}//跳出循环 //找到待删除元素所在行的前一个节点 while (lindPre.next.data != val){ lindPre = lindPre.next; } } size--; return true; } /** * 销毁跳表中的所有元素 */ void clear(){ this.hight=-1; this.size =0; this.head = null; this.tail = null; } /** * 查找跳表中是否存在该元素 * @param val * @return */ boolean find(int val){ return findPreNode(val) !=null; } /** * 找到元素 val 的前一个节点 即 最高层第一次出现的同一行的前一个元素 */ private Node findPreNode(int val){ Node first = head.getFirst();//从最上层的头节点开始搜索 while (first!=null){ if(first.data

< val && first.next.data >

val){ if(first.down == null){break;} first = first.down;//search down }else if(first.data < val && first.next.data < val){ first = first.next;//search to the right }else if(first.data < val && first.next.data == val){ return first; } } return null; } /** * Add elements from an array to a skip list * @param arr */ void arrayToSkipList(int[] arr){ int len = arr.length; for (int i = 0; i < len; i++) { add(arr[i]); } } /** * Print the contents of the jump table from top to bottom */ void showSkipList(){ System.out.println("Number of elements is: "+size); //print layer by layer from top to bottom for (int i = 0; i

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.