Java跳表方法实例分析

这篇"Java跳表方法实例分析"文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇"Java跳表方法实例分析"文章吧。

一、跳表的定义

跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

SkipList(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。SkipList让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过"空间来换取时间"的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

在Java的API中已经有了实现：分别是:

ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap) ；
ConcurrentSkipListSet(在功能上对应HashSet).
确切来说，SkipList更像Java中的TreeMap，TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。

SkipList的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

二、跳表搜索

例子：查找元素 117

(1) 比较 21， 比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85， 比 85 大，从后面找

(5) 比较 117， 等于 117， 找到了节点。

/**     * 找到元素 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;//往下搜索            }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 <=i; j++) {                //新增头节点和尾节点                Node h = new Node(Integer.MIN_VALUE,hight+j);                if(head.size()>0){                    h.down = head.getFirst();//往下指                }                Node t = new Node(Integer.MAX_VALUE,hight+j);//尾                if(tail.size()>0){                    t.down = tail.getFirst();                }                h.next=t;//头指向尾                tail.addFirst(t);                head.addFirst(h);            }            hight =k;//修改当前的跳表层数        }        return addFromK(val,k);//从第k层添加元素    }    /**     * 从跳表的第k层新增元素     * 被 add(int val) 方法调用     *     */    boolean addFromK(int val,int k){        Node preNewNode = new Node(val,k);        Node preLine = head.get(hight-k);//获取新增节点所在层的头节点        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;//往下搜索            }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;    }    /**     * 将数组中的元素添加到跳表中     * @param arr     */    void arrayToSkipList(int[] arr){        int len = arr.length;        for (int i = 0; i < len; i++) {            add(arr[i]);        }    }    /**     * 从上到下打印跳表的内容     */    void showSkipList(){        System.out.println("元素个数为："+size);        //从上往下逐层打印        for (int i = 0; i <=hight ; i++) {            Node linFirst = head.get(i);            System.out.print("第"+linFirst.level+"层:  "+"head ->    ");            linFirst = linFirst.next;//跳过第一列的元素            while (linFirst != null){                if(linFirst.next != null){                    System.out.print(""+linFirst.data +' '+"->       ");//+ " height:"+linFirst.level                }else {                    System.out.println("tail");                }                linFirst = linFirst.next;            }            System.out.println();        }    }}

以上就是关于"Java跳表方法实例分析"这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注行业资讯频道。