欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

跳表的由來及Java實現(xiàn)詳解

 更新時間：2023年06月01日 14:05:26   作者：日拱一車  
跳表（Skip List）是一種基于鏈表的數(shù)據結構，它可以支持快速的查找、插入、刪除操作，本文主要來和大家講講跳表的由來與實現(xiàn)，感興趣的小伙伴可以了解一下

什么是跳表

跳表（Skip List）是一種基于鏈表的數(shù)據結構，它可以支持快速的查找、插入、刪除操作，并且具有較好的平均時間復雜度，可以替代平衡樹等復雜數(shù)據結構。

跳表的由來

一、從前有一個鏈表，他是這樣的。

他具有非常優(yōu)秀的插入和刪除能力，對于插入只要三步，

1、找到位置。

2、新建一個節(jié)點

3、將前面的節(jié)點指針指到新建的節(jié)點上，將新節(jié)點的指針指到后續(xù)的節(jié)點上。

對于刪除來說，只要兩步。

1、找到當前節(jié)點位置，

2、將當前節(jié)點的前置節(jié)點指針指到當前節(jié)點的后續(xù)節(jié)點。

他不會像數(shù)組一樣，產生碎片，需要整理。也不需要從從某個節(jié)點開始整體移動，空出地方來存儲新的數(shù)據。

既然有這么優(yōu)秀的特性，他卻少有用武之地，這是為什么呢。

糟糕的查詢

面對這么一個有序鏈表，我們要查詢其中的某個元素，就要從頭節(jié)點（H）開始便利，直到找到這個元素。對于一個有序的鏈表，O(n/2)的時間復雜度讓他失去了有序的意義。

而且對于插入和刪除的位置確定（其實也是查詢），也需要從頭遍歷O(n/2)的時間復雜度。

大佬的優(yōu)化

有一天某個大佬突然意識到，既然問題出在查詢上，那么怎么優(yōu)化查詢呢？常見的方法就是建立索引，比如這樣，我們每隔一個元素抽出來一個，這樣先查索引，然后再查下面鏈表，不是就能節(jié)省很多時間嘛。

比如我們要查找8這個元素，按照原來的查找方法，我們需要依次訪問 1->2->3->4->-5->6->7->8。按照新的數(shù)據結構，需要訪問 1->3->5->7->8（

判斷條件為，當前節(jié)點的下一個節(jié)點不為空且小于目標節(jié)點則往后走，否則往下走，知道找到目標元素或者最下層為空

比如要查找6，步驟如下：

  • 1的后節(jié)點3小于6，繼續(xù)往后走，當前節(jié)點設為3
  • 3的后節(jié)點5小于6，繼續(xù)往后走，當前節(jié)點設置5
  • 5的后節(jié)點7大于6，則往下走，當前節(jié)點為下層的5。
  • 5的后節(jié)點6等于6，查找結束*）

顯然優(yōu)化了查詢路徑，當鏈表足夠大時，可以看到時間復雜度從O(n/2)下降到O(n/4)。整整優(yōu)化了一半?？墒巧厦娴?->3->5->7這個鏈表還是太長，可以繼續(xù)抽取索引來優(yōu)化查詢，結果是這樣的。

我們繼續(xù)查找8這個元素，會發(fā)現(xiàn)路徑只需要 1->5->7->8這四個元素，又優(yōu)化了一步。

路徑對比表如下

鏈表類型查詢路徑節(jié)點數(shù)
單鏈表1->2->3->4->-5->6->7->88
一級索引鏈表1->3->5->7->85
二級索引鏈表1->-5->7->84

可以看到，通過建立索引可以優(yōu)化查詢，彌補鏈表的短板。這位大佬依據這種跳過某些元素區(qū)間的查詢方式，對這種數(shù)據結構起名為跳表。

時間復雜度

根據上面的定義，跳表是每層抽出一半的元素作為索引，創(chuàng)建多級索引來優(yōu)化查詢，因為上一層都是本層的一半，則有

至此一個擁有O(logN)查詢復雜度兼具靈活的插入刪除特性的數(shù)據結構跳表就出現(xiàn)了。

跳表的索引生成

上面我們說了，跳表索引最理想的生成方式是每層抽出一半作為索引，但是在涉及到插入，刪除時候要平凡的改動索引，會造成很大的時間浪費，可用性不高。所以退而求其次，采用隨機的方式的生成索引。雖然是隨機，但是數(shù)據量越大，索引結構就會越接近理想索引。生成邏輯如下：

對于一個新加入的節(jié)點，最底層是100%插入的，所以隨機數(shù)最小返回1，返回的數(shù)值代表從此層及以下都要插入索引。因為每層拿一半作為索引，所以隨機數(shù)取0.5。代碼如下：

public int getRandomLevel(){
        int level = 1;
        while(Math.random()<0.5&&level<MAX_LEVEL){
            level++;
        }
        return level;
    }

跳表的JAVA實現(xiàn)

一、定義一個鏈表節(jié)點

public class SkipNode<E> {
	private String key;
	private E value;
	/**
		數(shù)組存儲每層索引的下一個節(jié)點。比如下標0表示鏈表本身，
		下標1表示第一層索引，依次類推。
	*/
	private SkipNode<E>[] next; 
	public SkipNode( String key, E value, int length ){
		this.key = key;
		this.value = value;
		next = new SkipNode[length];
	}
}

二、定義跳表的通用參數(shù)

public class SkipList<E> {
    /**
    	maxLevel 索引最大高度
    	currentLevel 當前索引高度
    	head 跳表頭節(jié)點，從head查起
    */
	private int maxLevel;
	private int currentLevel;
	private SkipNode head;
	public SkipList(int maxLevel, int currentLevel){
		this.maxLevel = maxlevel;
		this.currentLevel = currentLevel
		head = new SkipNode("head",null,maxLevel);
	}
}

三、定義增刪改查方法

public void insert( int key, E data ){
        SkipNode c = this.head;
        SkipNode[] update = new SkipNode[maxLevel];
        for( int i=currentLevel-1; i>=0; i--){
            while(c.next[i]!=null&&key>c.next[i].key){
                c=c.next[i];
            }
            if(c.key==key){
                c.data = data;
                return;
            }
            /**
            	記錄每一層的入口節(jié)點，如果要插入索引下面會用到
            */
            update[i] = c;
        }
        int randomLevel = getRandomLevel();
        SkipNode newNode = new SkipNode(key,data,randomLevel);
        if(randomLevel>currentLevel){
            for( int i=currentLevel; i<randomLevel; i++ ){
                update[i]=this.head;
            }
            currentLevel = randomLevel;
        }
        /**
        	當前節(jié)點作為新索引節(jié)點，更新每一層的索引指向
        */
        for( int i=randomLevel-1; i>=0;i--){
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
    }
    public E search( int key ){
        SkipNode<E> c = this.head;
        for( int i = currentLevel-1; i>=0; i-- ){
            while(c.next[i]!=null&&key> c.next[i].key){
                c=c.next[i];
            }
            if(c.next[i]!=null&&c.next[i].key==key){
                return c.next[i].data;
            }
        }
        return null;
    }
    public void delete( int key ){
        SkipNode skipNode = this.head;
        SkipNode[] delete = new SkipNode[currentLevel];
        for( int i=currentLevel-1; i>=0; i-- ){
            while( skipNode.next[i]!=null&&skipNode.next[i].key<key){
                skipNode = skipNode.next[i];
            }
            delete[i]=skipNode;
        }
if(delete[0].next[0]!=null&&delete[0].next[0].key==key){
            SkipNode deleteNode = delete[0].next[0];
            for( int i=0; i<currentLevel; i++ ){
                if(delete[i].next[i]==deleteNode){
                    delete[i].next[i] = delete[i].next[i].next[i];
                }
            }
      while(currentLevel>1&&this.head.next[currentLevel-1]==null){
                currentLevel--;
            }
        }
    }

到此這篇關于跳表的由來及Java實現(xiàn)詳解的文章就介紹到這了,更多相關Java跳表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論