Java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)跳表
一、跳表的定義
跳躍表是一種隨機(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ù)的向上攀升與否，通過“空間來換取時(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).
確切來說，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是通過一定的概率隨機(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è)指向下面一層的元素。
圖示：
二、跳表搜索
例子：查找元素 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
如果 K 大于鏈表的層數(shù)，則要添加新的層。
例子：插入 119， K = 4
四、刪除元素
從上往下刪除
/**
* 向跳表中刪除元素，從上往下刪除，每次找到所在行的前一個(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+"層:\t"+"head ->\t");
linFirst = linFirst.next;//跳過第一列的元素
while (linFirst != null){
if(linFirst.next != null){
System.out.print(""+linFirst.data +'\t'+"->\t");//+ " height:"+linFirst.level
}else {
System.out.println("tail");
}
linFirst = linFirst.next;
}
System.out.println();
}
}
}
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)跳表的文章就介紹到這了,更多相關(guān)Java跳表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
MyBatis實(shí)現(xiàn)數(shù)據(jù)庫(kù)類型和Java類型的轉(zhuǎn)換
MyBatis 在處理數(shù)據(jù)庫(kù)查詢結(jié)果或傳遞參數(shù)時(shí),需要將數(shù)據(jù)庫(kù)類型與 Java 類型之間進(jìn)行轉(zhuǎn)換,本文就給大家介紹MyBatis如何實(shí)現(xiàn)數(shù)據(jù)庫(kù)類型和 Java 類型的轉(zhuǎn)換的,需要的朋友可以參考下2024-09-09
如何使用Maven管理項(xiàng)目?Maven管理項(xiàng)目實(shí)例
下面小編就為大家?guī)硪黄绾问褂肕aven管理項(xiàng)目?Maven管理項(xiàng)目實(shí)例。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了Mybatis重置Criteria的正確姿勢(shì)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
Spring中網(wǎng)絡(luò)請(qǐng)求客戶端WebClient的使用詳解
作為替代,Spring 官方已在 Spring 5 中引入了 WebClient 作為非阻塞式 Reactive HTTP 客戶端,本文將通過樣例演示如何使用 WebClient,希望對(duì)大家有所幫助2024-04-04
JAVA JNI原理詳細(xì)介紹及簡(jiǎn)單實(shí)例代碼
這篇文章主要介紹了JAVA JNI原理的相關(guān)資料,這里提供簡(jiǎn)單實(shí)例代碼，需要的朋友可以參考下2016-12-12
這篇文章主要介紹了@ComponentScan注解的使用詳解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08
Spring Cloud Alibaba配置多環(huán)境管理詳解與實(shí)戰(zhàn)代碼
本文通過實(shí)際案例詳細(xì)介紹了springboot配置多環(huán)境管理的使用,以及基于nacos的配置多環(huán)境管理的實(shí)踐,在實(shí)際開發(fā)中,配置多環(huán)境管理是一個(gè)很難避開的問題,同時(shí)也是微服務(wù)治理中一個(gè)很重要的內(nèi)容,感興趣的朋友跟隨小編一起看看吧2024-06-06
Java設(shè)計(jì)模塊系列之書店管理系統(tǒng)單機(jī)版(一)
這篇文章主要為大家詳細(xì)介紹了Java單機(jī)版的書店管理系統(tǒng)設(shè)計(jì)模塊和思想第一章，感興趣的小伙伴們可以參考一下2016-08-08
mybatisplus實(shí)現(xiàn)自動(dòng)創(chuàng)建/更新時(shí)間的項(xiàng)目實(shí)踐
Mybatis-Plus提供了自動(dòng)填充功能,可以通過實(shí)現(xiàn)MetaObjectHandler接口來實(shí)現(xiàn)自動(dòng)更新時(shí)間的功能,本文就來介紹一下mybatisplus實(shí)現(xiàn)自動(dòng)創(chuàng)建/更新時(shí)間的項(xiàng)目實(shí)踐,感興趣的可以了解下2024-01-01
mybatis教程之查詢緩存（一級(jí)緩存二級(jí)緩存和整合ehcache）
這篇文章主要介紹了mybatis教程之查詢緩存（一級(jí)緩存二級(jí)緩存和整合ehcache）,具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-05-05