快捷導(dǎo)航

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

更新時間：2023年06月01日 14:05:26 作者：日拱一車

跳表（Skip List）是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，它可以支持快速的查找、插入、刪除操作，本文主要來和大家講講跳表的由來與實現(xiàn)，感興趣的小伙伴可以了解一下

什么是跳表

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

跳表的由來

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

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

1、找到位置。

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

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

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

1、找到當(dāng)前節(jié)點(diǎn)位置，

2、將當(dāng)前節(jié)點(diǎn)的前置節(jié)點(diǎn)指針指到當(dāng)前節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)。

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

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

糟糕的查詢

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

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

大佬的優(yōu)化

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

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

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

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

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

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

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

路徑對比表如下

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

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

時間復(fù)雜度

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

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

跳表的索引生成

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

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

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

跳表的JAVA實現(xiàn)

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

public class SkipNode<E> {
	private String key;
	private E value;
	/**
		數(shù)組存儲每層索引的下一個節(jié)點(diǎn)。比如下標(biāo)0表示鏈表本身，
		下標(biāo)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 當(dāng)前索引高度
    	head 跳表頭節(jié)點(diǎn)，從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é)點(diǎn)，如果要插入索引下面會用到
            */
            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;
        }
        /**
        	當(dāng)前節(jié)點(diǎn)作為新索引節(jié)點(diǎn)，更新每一層的索引指向
        */
        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--;
            }
        }
    }

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

您可能感興趣的文章: