App下載

簡(jiǎn)述Java數(shù)據(jù)結(jié)構(gòu)之跳表及詳細(xì)操作內(nèi)容

猿友 2021-07-27 10:36:13 瀏覽數(shù) (2385)
反饋

一、跳表的定義

跳躍表是一種隨機(jī)化數(shù)據(jù)結(jié)構(gòu),基于并聯(lián)的鏈表,其效率可比擬于二叉查找樹(對(duì)于大多數(shù)操作需要O(log n)平均時(shí)間),并且對(duì)并發(fā)算法友好。

SkipList(跳表)是一種可以代替平衡樹的數(shù)據(jù)結(jié)構(gòu),默認(rèn)是按照Key值升序的。SkipList讓已排序的數(shù)據(jù)分布在多層鏈表中,以0-1隨機(jī)數(shù)決定一個(gè)數(shù)據(jù)的向上攀升與否,通過(guò)“空間來(lái)?yè)Q取時(shí)間”的一個(gè)算法,在每個(gè)節(jié)點(diǎn)中增加了向前的指針,在插入、刪除、查找時(shí)可以忽略一些不可能涉及到的結(jié)點(diǎn),從而提高了效率。

在Java的API中已經(jīng)有了實(shí)現(xiàn):分別是:

ConcurrentSkipListMap(在功能上對(duì)應(yīng)HashTable、HashMap、TreeMap) ;
ConcurrentSkipListSet(在功能上對(duì)應(yīng)HashSet).
確切來(lái)說(shuō),SkipList更像Java中的TreeMap,TreeMap基于紅黑樹(一種自平衡二叉查找樹)實(shí)現(xiàn)的,時(shí)間復(fù)雜度平均能達(dá)到O(log n)。
HashMap是基于散列表實(shí)現(xiàn)的,時(shí)間復(fù)雜度平均能達(dá)到O(1)。ConcurrentSkipListMap是基于跳表實(shí)現(xiàn)的,時(shí)間復(fù)雜度平均能達(dá)到O(log n)。

SkipList的性質(zhì)

(1) 由很多層結(jié)構(gòu)組成,level是通過(guò)一定的概率隨機(jī)產(chǎn)生的。
(2) 每一層都是一個(gè)有序的鏈表,默認(rèn)是升序
(3) 最底層(Level 1)的鏈表包含所有元素。
(4) 如果一個(gè)元素出現(xiàn)在Level i 的鏈表中,則它在Level i 之下的鏈表也都會(huì)出現(xiàn)。
(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針,一個(gè)指向同一鏈表中的下一個(gè)元素,一個(gè)指向下面一層的元素。

圖示:

2021052410265427

二、跳表搜索

2021052410265528

例子:查找元素 117

(1) 比較 21, 比 21 大,往后面找

(2) 比較 37, 比 37大,比鏈表最大值小,從 37 的下面一層開始找

(3) 比較 71, 比 71 大,比鏈表最大值小,從 71 的下面一層開始找

(4) 比較 85, 比 85 大,從后面找

(5) 比較 117, 等于 117, 找到了節(jié)點(diǎn)。

/**
     * 找到元素 val 的前一個(gè)節(jié)點(diǎn) 即 最高層第一次出現(xiàn)的同一行的前一個(gè)元素
     */
    private Node findPreNode(int val){
        Node first = head.getFirst();//從最上層的頭節(jié)點(diǎn)開始搜索
        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;
    }

三、插入元素

先確定該元素要占據(jù)的層數(shù) K(采用丟硬幣的方式,這完全是隨機(jī)的)然后在 Level 1 … Level K 各個(gè)層的鏈表都插入元素。

/**
     * 隨機(jī)獲取高度,(相當(dāng)于拋硬幣連續(xù)出現(xiàn)正面的次數(shù))
     * @return
     */
    private int getLeavel(){
        int k = 0;
        while(rd.nextInt(2) == 1){
            k ++;
        }
        return k;
    }

例子:插入 119, K = 2

2021052410265529

如果 K 大于鏈表的層數(shù),則要添加新的層。
例子:插入 119, K = 4

2021052410265530

四、刪除元素

從上往下刪除

2021052410265531

/**
     * 向跳表中刪除元素,從上往下刪除,每次找到所在行的前一個(gè)節(jié)點(diǎn)
     * @param val
     * @return 如果找不到 待刪除元素 則返回 false
     */
    boolean delete(int val){
        Node lindPre = findPreNode(val);//找到待刪除元素的最上層的前一個(gè)節(jié)點(diǎn)
        if(lindPre == null){
            return false;
        }
        while (true){
            lindPre.next = lindPre.next.next;
            lindPre = lindPre.down;//往下遍歷,直到最底下一層
            if(lindPre==null){break;}//跳出循環(huán)
            //找到待刪除元素所在行的前一個(gè)節(jié)點(diǎn)
            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 跳表抽象數(shù)據(jù)結(jié)構(gòu)
 **/
public class SkipList {

    //使用頭插法插入新節(jié)點(diǎn)
    LinkedList<Node> head;//每一行的頭結(jié)點(diǎn),相當(dāng)于跳表的第一列, 默認(rèn)設(shè)置為 Integer.MIN_VALUE
    LinkedList<Node> tail;//每一行大最后一個(gè)節(jié)點(diǎn),相當(dāng)與跳表的最后一列  Integer.MAX_VALUE
    Random rd ;//用于生成隨機(jī)數(shù)數(shù)
    int hight=-1;//當(dāng)前跳表的層數(shù),hight從0開始,初始值為-1,
    int size;//所有的節(jié)點(diǎn)數(shù)

    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();

    }
    /**
     * 節(jié)點(diǎn)內(nèi)部類
     */
    private class Node{
        int data;//存放數(shù)據(jù)
        Node next;//指向右邊節(jié)點(diǎn)
        Node down; //指向下面節(jié)點(diǎn)
        int level;//當(dāng)前所在的層
        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;
        }
    }

    /**
     * 向跳表中加添加元素
     * 是否考慮重復(fù)元素??????????
     * @param val
     * @return
     */
    boolean add(int val){
        int k = getLeavel();//獲得層數(shù)
        //層數(shù)比當(dāng)前大的時(shí)候,增加新的層
        if(k>hight){
            int i = k-hight;
            for (int j = 1; j <=i; j++) {
                //新增頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
                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;//修改當(dāng)前的跳表層數(shù)
        }
        return addFromK(val,k);//從第k層添加元素
    }

    /**
     * 從跳表的第k層新增元素
     * 被 add(int val) 方法調(diào)用
     *
     */
    boolean addFromK(int val,int k){
        Node preNewNode = new Node(val,k);
        Node preLine = head.get(hight-k);//獲取新增節(jié)點(diǎn)所在層的頭節(jié)點(diǎn)
        while (preLine != null){
            while (preLine.next.data < val){//往右搜索
                preLine = preLine.next;
            }
            preNewNode.next = preLine.next;
            preLine.next = preNewNode;
            //如果不是第一層,則建立下一層的新節(jié)點(diǎn)
            if (preNewNode.level>0){
                Node newNode = new  Node(val,preNewNode.level-1);
                preNewNode.down = newNode;//往下指向新節(jié)點(diǎn)
                preNewNode = newNode;
            }
            //往下層建立新節(jié)點(diǎn)
            preLine = preLine.down;
        }
        size++;//跳表中的元素?cái)?shù)量加一
        return true;
    }


    /**
     * 隨機(jī)獲取高度,(相當(dāng)于拋硬幣連續(xù)出現(xiàn)正面的次數(shù))
     * @return
     */
    private int getLeavel(){
        int k = 0;
        while(rd.nextInt(2) == 1){
            k ++;
        }
        return k;
    }

    /**
     * 向跳表中刪除元素,從上往下刪除,每次找到所在行的前一個(gè)節(jié)點(diǎn)
     * @param val
     * @return 如果找不到 待刪除元素 則返回 false
     */
    boolean delete(int val){
        Node lindPre = findPreNode(val);//找到待刪除元素的最上層的前一個(gè)節(jié)點(diǎn)
        if(lindPre == null){
            return false;
        }
        while (true){
            lindPre.next = lindPre.next.next;
            lindPre = lindPre.down;//往下遍歷,直到最底下一層
            if(lindPre==null){break;}//跳出循環(huán)
            //找到待刪除元素所在行的前一個(gè)節(jié)點(diǎn)
            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 的前一個(gè)節(jié)點(diǎn) 即 最高層第一次出現(xiàn)的同一行的前一個(gè)元素
     */
    private Node findPreNode(int val){
        Node first = head.getFirst();//從最上層的頭節(jié)點(diǎn)開始搜索
        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;
    }

    /**
     * 將數(shù)組中的元素添加到跳表中
     * @param arr
     */
    void arrayToSkipList(int[] arr){
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            add(arr[i]);
        }
    }

    /**
     * 從上到下打印跳表的內(nèi)容
     */
    void showSkipList(){
        System.out.println("元素個(gè)數(shù)為:"+size);
        //從上往下逐層打印
        for (int i = 0; i <=hight ; i++) {
            Node linFirst = head.get(i);
            System.out.print("第"+linFirst.level+"層:	"+"head ->	");
            linFirst = linFirst.next;//跳過(guò)第一列的元素
            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();
        }
    }

}

到此這篇關(guān)于 Java 數(shù)據(jù)結(jié)構(gòu)之跳表的介紹以及詳細(xì)操作內(nèi)容的文章就介紹到這了,想要了解更多相關(guān) Java 跳表內(nèi)容請(qǐng)搜索W3Cschool以前的文章或繼續(xù)瀏覽下面的相關(guān)文章,希望大家以后多多支持我們!


0 人點(diǎn)贊