繼承躲株，是幸福的延續(xù)；重載镣衡，是幸福的重生霜定。
數(shù)組與鏈表
數(shù)組
在計(jì)算機(jī)科學(xué)中，數(shù)組數(shù)據(jù)結(jié)構(gòu)（英語：array data structure）廊鸥，簡稱數(shù)組（英語：Array）望浩，是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲(chǔ)惰说。利用元素的索引（index）可以計(jì)算出該元素對(duì)應(yīng)的存儲(chǔ)地址磨德。
優(yōu)點(diǎn)
- 隨機(jī)訪問速度較快（基于下標(biāo)訪問）。
- 實(shí)現(xiàn)簡單吆视，使用簡單典挑。
- 內(nèi)存地址連續(xù)，對(duì)cpu緩存很友好揩环，比如高性能隊(duì)列 disruptor 也是利用了cpu緩存+數(shù)組地址的連續(xù)性大大的優(yōu)化了性能搔弄。
缺點(diǎn)
- 內(nèi)存連續(xù)可以是優(yōu)點(diǎn)，也可以是缺點(diǎn)丰滑，如果在內(nèi)存緊張的情況下顾犹，數(shù)組將會(huì)被大大限制。
- 插入和刪除的時(shí)候會(huì)導(dǎo)致元素的移動(dòng)（數(shù)據(jù)拷貝）褒墨，較慢炫刷。
- 數(shù)組大小固定，大大的限制了元素的個(gè)數(shù)郁妈，對(duì)于很多動(dòng)態(tài)的數(shù)據(jù)不友好浑玛。
鏈表
鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表噩咪，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)顾彰，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)胃碾，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度涨享，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間仆百。
優(yōu)點(diǎn)
- 鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間厕隧，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
- 刪除插入不用移動(dòng)其他元素。
- 不受元素大小限制吁讨，可以隨意擴(kuò)展髓迎。
缺點(diǎn)
- 失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域建丧，空間開銷比較大排龄。
- 隨機(jī)訪問效率相對(duì)數(shù)組來說較低。
時(shí)間復(fù)雜度分析
隨機(jī)訪問
數(shù)組：O(1)
不支持隨機(jī)訪問-
插入茶鹃，刪除
數(shù)組：有序數(shù)組 ->O(n)涣雕，無序數(shù)組 ->（1）
鏈表：O(1)鏈表又可以分為單鏈表和雙向鏈表艰亮，不過這都不是這篇文章需要討論的問題闭翩，這里講一下數(shù)組和鏈表，只是做一下鋪墊迄埃，因?yàn)橄旅嬷v到的跳表就會(huì)用到鏈表的相關(guān)知識(shí)疗韵，所以對(duì)鏈表還不怎么熟悉的同學(xué)，可以先學(xué)習(xí)一下侄非，然后在開始今天的正文：跳表蕉汪。
什么是跳表？
上文講到了鏈表的概念逞怨，鏈表的查詢時(shí)間復(fù)雜度為：<font color='red' size=4 >O(n)</font>者疤，即使是有序的鏈表，也得從鏈表的第一個(gè)元素開始遍歷查找叠赦，時(shí)間復(fù)雜度偏高驹马，那如果讓你來優(yōu)化，你有什么解決方案嗎除秀？這個(gè)時(shí)候跳表就出現(xiàn)了糯累。
跳表，全程：跳躍鏈表册踩，在計(jì)算機(jī)科學(xué)中泳姐，跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個(gè)元素的有序序列的查找和插入操作的平均時(shí)間復(fù)雜度都是：
我們來畫一個(gè)普通的鏈表結(jié)構(gòu)
這是一個(gè)普通的單鏈表結(jié)構(gòu)暂吉，如果我們想查找出 58 這個(gè)節(jié)點(diǎn)胖秒，我們就得查詢 1 -> 4 -> 7 -> 15 -> 20 -> 35 -> 50 -> 58 ，一共查找了8次慕的，才將我們需要的結(jié)果查找出來阎肝，時(shí)間復(fù)雜度：O(n)，效率可想而知业稼，那我們一起試著來優(yōu)化一下盗痒。
mysql在數(shù)據(jù)量大的時(shí)候查詢效率也會(huì)急劇下降，他們是怎么來優(yōu)化效率問題呢？那就是<font color='red' size=4 >索引</font>俯邓，這里我們也可以使用一個(gè)類似 “索引” 的東西來對(duì)這個(gè)普通的單鏈表進(jìn)行優(yōu)化骡楼。
我們將原始鏈表中每隔兩個(gè)結(jié)點(diǎn)之后的節(jié)點(diǎn)復(fù)制一份出來，用于制作索引稽鞭，方便數(shù)據(jù)的查找鸟整。
我們還是繼續(xù)查找58，我們只需要經(jīng)過：1 -> 7 -> 20 --> 50 -> 58朦蕴，發(fā)現(xiàn)了沒有篮条，這里居然只搜索了5次就找到了我們想要的結(jié)點(diǎn)，效率是不是提升了一丟丟吩抓？我現(xiàn)在來解釋一下這張圖涉茧，由于我們建立了一層索引，所以查詢的時(shí)候優(yōu)先往第一層索引層搜索疹娶，搜索索引層時(shí)伴栓，發(fā)現(xiàn) 50 以及之前的節(jié)點(diǎn)都小于 58 ，遍歷到 50 的時(shí)候，他的下一個(gè)節(jié)點(diǎn) 66 大于需要查詢的節(jié)點(diǎn) ，所以這個(gè)時(shí)候就會(huì)找到50這個(gè)節(jié)點(diǎn)中的down（原始鏈表節(jié)點(diǎn)為 50 的指針）節(jié)點(diǎn)蝗拿，然后再往下遍歷一個(gè)就就找到了 58 。
加了“索引” 也才少查詢了三次饺窿，優(yōu)化的并不是很明顯啊，這個(gè)優(yōu)化是否有存在的必要呢移斩？我們這里之建立了一層“索引”肚医，我們多建立幾層”索引“之后呢？會(huì)是什么樣呢叹哭？
這個(gè)時(shí)候我們發(fā)現(xiàn)只需要4次就能找到我們需要查找的節(jié)點(diǎn) 58 忍宋，4 次相對(duì)于8次來說已經(jīng)快了一半了，我這里的數(shù)據(jù)不是太多风罩，當(dāng)數(shù)據(jù)足夠多的時(shí)候糠排，效果將會(huì)更為明顯。
這種一層一層的索引組成的數(shù)據(jù)結(jié)構(gòu)超升，我們稱他為：<font color='red' size=4 >跳表</font>入宦，現(xiàn)在相信你對(duì)什么是跳表應(yīng)該有了比較深的理解了吧，這個(gè)時(shí)候你可能又有一個(gè)疑問了室琢？我們?yōu)榱私⑺饕龑忧颍隙〞?huì)消耗大量的空間，這是屬于空間換時(shí)間的一種方式盈滴，但是在數(shù)據(jù)量大的時(shí)候涯肩，會(huì)不會(huì)存在空間不夠的情況呢轿钠？
那我們現(xiàn)在一起來分析一下跳表的時(shí)間/空間復(fù)雜度吧
跳表分析
假設(shè)原始鏈表結(jié)點(diǎn)個(gè)數(shù)為：n，我們知道病苗，我們每隔兩個(gè)節(jié)點(diǎn)抽離一個(gè)結(jié)點(diǎn)作為索引層的一個(gè)結(jié)點(diǎn)疗垛，那么第一層索引層的結(jié)點(diǎn)個(gè)數(shù)應(yīng)該是原始鏈表結(jié)點(diǎn)個(gè)數(shù)的1/2，也就是n/2硫朦，第二層索引的結(jié)點(diǎn)個(gè)數(shù)是第一層索引結(jié)點(diǎn)個(gè)數(shù)的1/2贷腕，是 1/4 原始鏈表結(jié)點(diǎn)個(gè)數(shù)，也就是 n/4咬展，第三層索引的結(jié)點(diǎn)個(gè)數(shù)是第二層結(jié)點(diǎn)個(gè)數(shù)的1/2泽裳，是第一層索引結(jié)點(diǎn)個(gè)數(shù)的4/1，是原始鏈表結(jié)點(diǎn)個(gè)數(shù)的1/8破婆，依次類推涮总，在k層索引的節(jié)點(diǎn)個(gè)數(shù)是k-1層索引的1/2，那么k層索引的節(jié)點(diǎn)個(gè)數(shù)：
一個(gè)鏈表荠割，假設(shè)我們都是每隔兩個(gè)結(jié)點(diǎn)分配一個(gè)索引結(jié)點(diǎn)妹卿，最高層索引只有兩個(gè)結(jié)點(diǎn)，索引層高度為：h蔑鹦，那么將會(huì)得到這么一個(gè)公式：
我們求解一下 h：
我們將這個(gè)公式拆分一下：
所以 h 的值為：
由于 h 是索引層的高度，我們算上原始鏈表箕宙，那么真?zhèn)€跳表的高度就是：
現(xiàn)在我們一起來算算跳表查詢的時(shí)間復(fù)雜度嚎朽，跳表有許多層索引，每層索引都會(huì)進(jìn)行相對(duì)應(yīng)次數(shù)的遍歷柬帕，假設(shè)每次索引遍歷的最大次數(shù)為：x哟忍，那么一個(gè)查詢需要遍歷的次數(shù)為：
所以用 O 表示法表示，跳表的時(shí)間復(fù)雜度為：
為什么對(duì)數(shù)中的底數(shù) 2 沒有了呢陷寝？ 其實(shí)在時(shí)間復(fù)雜度分析中锅很，分析的只是一種趨勢，并不是固定的值凤跑，相對(duì)數(shù)級(jí)別的爆安，底數(shù)可以忽略，具體相關(guān)的介紹仔引，這里就不展開介紹了扔仓，感興趣的可以百度一下，并不復(fù)雜咖耘，我們現(xiàn)在需要搞明白的是這個(gè) x 到底是多少呢翘簇？
在前面所畫的跳表結(jié)構(gòu)圖中，我們以每隔兩個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)儿倒，所以版保，當(dāng)我們需要查詢跳表中某一個(gè)結(jié)點(diǎn)時(shí)，需要在索引層從上而下開始遍歷，每層最多不會(huì)超過3個(gè)彻犁，為什么是 3 個(gè)而不是 4 個(gè)蹈垢、5 個(gè)、6 個(gè)呢袖裕？我們畫一個(gè)簡單的圖來說明一下曹抬。
我們需要查找 12 這個(gè)結(jié)點(diǎn)，當(dāng)走到 9 這個(gè)結(jié)點(diǎn)時(shí)發(fā)現(xiàn) 12 > 9 而 < 13 所以下降一層索引急鳄，到達(dá)第一層索引谤民，而在 9 - 13 之間只有三個(gè)結(jié)點(diǎn)，就算是下降到原始鏈表也是一樣的疾宏，兩個(gè)范圍結(jié)點(diǎn)之前最多只有三個(gè)結(jié)點(diǎn)张足，所以 每層需要遍歷的最多結(jié)點(diǎn)數(shù)就是這么得出來的，因?yàn)?x 是常數(shù) 3 坎藐，可以直接省略为牍，所以跳表最終的時(shí)間復(fù)雜度為：
雖然查詢的效率提高了非常多，但是這也存在一個(gè)非常重要的問題岩馍，那就是跳表會(huì)占用額外的內(nèi)存空間碉咆，因?yàn)椋枰芏鄬拥乃饕鳎@樣這個(gè)數(shù)據(jù)結(jié)構(gòu)還值不值得推薦使用呢疫铜？既然redis官方都在使用了，你還在怕什么呢双谆？我們再來分析一下跳表的空間復(fù)雜度壳咕，看看是不是對(duì)內(nèi)存有著極大的消耗呢？
假設(shè)原始鏈表長度為 n 顽馋，那么第一層索引長度為 n/2谓厘，第二層索引長度為：n/4，第三層索引長度：n/8寸谜，最后一層（最高層）索引長度：2竟稳，很明顯這是一個(gè)等比數(shù)列：
等比數(shù)列求和公式：
套入公式：
索引層占用總大小為：n - 2住练，加上原始鏈表 n = 2n -2 ，所以跳表的空間復(fù)雜度為：<font color='red' size=4 >O(n)</font>愁拭，常數(shù)可以省略讲逛，這是每個(gè)兩個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)的空間復(fù)雜度，那多隔幾個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)呢岭埠？比如每隔 3 個(gè)提取一個(gè)盏混，每隔 5 個(gè)提取一個(gè)蔚鸥，計(jì)算方式和上面一樣，結(jié)果空間復(fù)雜度也是：<font color='red' size=4 >O(n)</font>许赃，但是空間確實(shí)減少了很多止喷。
查詢我們講完了，那跳表的插入和刪除效果怎么樣呢混聊？會(huì)不會(huì)也表現(xiàn)得很優(yōu)秀弹谁？我們一起來看看。
由于我們的鏈表是有序的句喜，所以在插入的時(shí)候我們得先找到插入的位置预愤，跳表的查詢時(shí)間復(fù)雜度為O(logn )，找到了需要插入的位置之后就是插入操作咳胃，單鏈表的插入時(shí)間復(fù)雜度時(shí)O(1)植康，這里就不證明了，所以整個(gè)插入的過程等于查找插入的位置+插入=O(logn)展懈。
其實(shí)刪除操作的時(shí)間復(fù)雜也是O(logn)销睁，為什么呢？其實(shí)和插入也是一樣的存崖，但是會(huì)多一個(gè)查找前驅(qū)結(jié)點(diǎn)的操作冻记，因?yàn)閯h除，會(huì)導(dǎo)致前后驅(qū)結(jié)點(diǎn)的指針變動(dòng)金句，后驅(qū)結(jié)點(diǎn)在當(dāng)前刪除的結(jié)點(diǎn)中存在檩赢，但是前前驅(qū)節(jié)點(diǎn)沒有，查詢也是O(logn)违寞，所以刪除 O(logn)+O(logn)，所以刪除的時(shí)間復(fù)雜度最終還是：O(logn)偶房，但是刪除有一點(diǎn)需要注意趁曼，如果需要?jiǎng)h除的結(jié)點(diǎn)在索引層也存在，那么同時(shí)需要?jiǎng)h除索引層的結(jié)點(diǎn)棕洋，關(guān)于前驅(qū)結(jié)點(diǎn)的問題挡闰，可以使用雙向鏈表解決。
索引更新
跳表的查詢掰盘、刪除摄悯、添加在性能方面都比較優(yōu)秀，那它能一直保持這么優(yōu)秀嗎愧捕？既然跳表也是用來存放數(shù)據(jù)的奢驯，那么肯定會(huì)伴隨著頻繁的新增和刪除，假設(shè)在某一個(gè)相鄰區(qū)間的索引結(jié)點(diǎn)之間被插入了較多的數(shù)據(jù)次绘，那么就會(huì)導(dǎo)致數(shù)據(jù)分布不均勻瘪阁，在某一個(gè)區(qū)間的查詢時(shí)間效率降低撒遣，最壞情況可能會(huì)被退化成單鏈表，所有的數(shù)據(jù)都在這一個(gè)區(qū)間內(nèi)管跺，所以我們在數(shù)據(jù)插入的時(shí)候?qū)λ饕龑幼鰧?shí)時(shí)更新維護(hù)义黎，保證跳表的數(shù)據(jù)結(jié)構(gòu)不會(huì)過度退化，那我們怎么維護(hù)索引層的變化呢豁跑？
其實(shí)也不難廉涕，跳表通過隨機(jī)函數(shù)來保持?jǐn)?shù)據(jù)的平衡性，也就是讓數(shù)據(jù)保持相對(duì)均勻艇拍，當(dāng)我們往跳表中添加數(shù)據(jù)的時(shí)候狐蜕，通過隨機(jī)函數(shù)生成一個(gè)隨機(jī)數(shù)，這個(gè)隨機(jī)數(shù)就是索引的層數(shù)淑倾，然后在這一層把需要添加的結(jié)點(diǎn)添加到這一層索引層節(jié)點(diǎn)中馏鹤，假設(shè)我們需要插入的數(shù)據(jù)為 7 ，隨機(jī)函數(shù)生成的隨機(jī)數(shù)為： 2娇哆，那么插入的時(shí)候就會(huì)如下圖所示：
這里就對(duì)隨機(jī)函數(shù)的要求很高了湃累，它可以很好地保證跳表的平衡性，不會(huì)讓跳表的性能退化碍讨，這點(diǎn)和紅黑樹的左旋/右旋是一個(gè)道理治力。
代碼實(shí)現(xiàn)
上面的都是理論基礎(chǔ)，我們看完了理論勃黍，那一定要真刀真槍的干一下宵统，不然不就白看了嗎，那我們一起來看看跳表的代碼如何實(shí)現(xiàn)
``
package com.lx.cloud.test;
import java.util.Random;
/**
* @ClassName SkipList
* @Description 跳表
*/
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
/**
* 帶頭鏈表
*/
private Node head = new Node(MAX_LEVEL);
private Random r = new Random();
public Node find(int value) {
Node p = head;
// 從最大層開始查找覆获，找到前一節(jié)點(diǎn)马澈，通過--i，移動(dòng)到下層再開始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一節(jié)點(diǎn)
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
/**
* 優(yōu)化了作者zheng的插入方法
*
* @param value 值
*/
public void insert(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一層弄息，如果條件滿足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
// 從最大層開始查找痊班，找到前一節(jié)點(diǎn)，通過--i摹量，移動(dòng)到下層再開始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一節(jié)點(diǎn)
p = p.forwards[i];
}
// levelCount 會(huì) > level涤伐，所以加上判斷
if (level > i) {
update[i] = p;
}
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
/**
* 優(yōu)化了作者zheng的插入方法2
*
* @param value 值
*/
public void insert2(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一層，如果條件滿足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node p = head;
// 從最大層開始查找缨称，找到前一節(jié)點(diǎn)凝果，通過--i，移動(dòng)到下層再開始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一節(jié)點(diǎn)
p = p.forwards[i];
}
// levelCount 會(huì) > level睦尽，所以加上判斷
if (level > i) {
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
} else {
Node next = p.forwards[i];
p.forwards[i] = newNode;
newNode.forwards[i] = next;
}
}
}
}
/**
* 作者zheng的插入方法器净，未優(yōu)化前，優(yōu)化后參見上面insert()
*
* @param value
* @param level 0 表示隨機(jī)層數(shù)骂删，不為0掌动，表示指定層數(shù)四啰，指定層數(shù)
* 可以讓每次打印結(jié)果不變動(dòng)，這里是為了便于學(xué)習(xí)理解
*/
public void insert(int value, int level) {
// 隨機(jī)一個(gè)層數(shù)
if (level == 0) {
level = randomLevel();
}
// 創(chuàng)建新節(jié)點(diǎn)
Node newNode = new Node(level);
newNode.data = value;
// 表示從最大層到低層粗恢，都要有節(jié)點(diǎn)數(shù)據(jù)
newNode.maxLevel = level;
// 記錄要更新的層數(shù)柑晒，表示新節(jié)點(diǎn)要更新到哪幾層
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
/**
*
* 1，說明：層是從下到上的眷射，這里最下層編號(hào)是0匙赞，最上層編號(hào)是15
* 2，這里沒有從已有數(shù)據(jù)最大層（編號(hào)最大）開始找妖碉，（而是隨機(jī)層的最大層）導(dǎo)致有些問題涌庭。
* 如果數(shù)據(jù)量為1億，隨機(jī)level=1 欧宜，那么插入時(shí)間復(fù)雜度為O（n）
*/
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 這里update[i]表示當(dāng)前層節(jié)點(diǎn)的前一節(jié)點(diǎn)坐榆，因?yàn)橐业角耙还?jié)點(diǎn)，才好插入數(shù)據(jù)
update[i] = p;
}
// 將每一層節(jié)點(diǎn)和后面節(jié)點(diǎn)關(guān)聯(lián)
for (int i = 0; i < level; ++i) {
// 記錄當(dāng)前層節(jié)點(diǎn)后面節(jié)點(diǎn)指針
newNode.forwards[i] = update[i].forwards[i];
// 前一個(gè)節(jié)點(diǎn)的指針冗茸，指向當(dāng)前節(jié)點(diǎn)
update[i].forwards[i] = newNode;
}
// 更新層高
if (levelCount < level){
levelCount = level;
}
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
/**
* 隨機(jī) level 次席镀，如果是奇數(shù)層數(shù) +1，防止偽隨機(jī)
*
* @return
*/
private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
/**
* 打印每個(gè)節(jié)點(diǎn)數(shù)據(jù)和最大層數(shù)
*/
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
/**
* 打印所有數(shù)據(jù)
*/
public void printAll_beautiful() {
Node p = head;
Node[] c = p.forwards;
Node[] d = c;
int maxLevel = c.length;
for (int i = maxLevel - 1; i >= 0; i--) {
do {
System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
} while (d[i] != null && (d = d[i].forwards)[i] != null);
System.out.println();
d = c;
}
}
/**
* 跳表的節(jié)點(diǎn)夏漱，每個(gè)節(jié)點(diǎn)記錄了當(dāng)前節(jié)點(diǎn)數(shù)據(jù)和所在層數(shù)數(shù)據(jù)
*/
public class Node {
private int data = -1;
/**
* 表示當(dāng)前節(jié)點(diǎn)位置的下一個(gè)節(jié)點(diǎn)所有層的數(shù)據(jù)豪诲，從上層切換到下層，就是數(shù)組下標(biāo)-1挂绰，
* forwards[3]表示當(dāng)前節(jié)點(diǎn)在第三層的下一個(gè)節(jié)點(diǎn)屎篱。
*/
private Node forwards[];
/**
* 這個(gè)值其實(shí)可以不用，看優(yōu)化insert()
*/
private int maxLevel = 0;
public Node(int level) {
forwards = new Node[level];
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
public static void main(String[] args) {
SkipList list = new SkipList();
list.insert(1, 3);
list.insert(2, 3);
list.insert(3, 2);
list.insert(4, 4);
list.insert(5, 10);
list.insert(6, 4);
list.insert(8, 5);
list.insert(7, 4);
list.printAll_beautiful();
list.printAll();
SkipList list2 = new SkipList();
list2.insert2(1);
list2.insert2(2);
list2.insert2(6);
list2.insert2(7);
list2.insert2(8);
list2.insert2(3);
list2.insert2(4);
list2.insert2(5);
System.out.println();
list2.printAll_beautiful();
}
}
打印結(jié)果
`null:15-------
null:14-------
null:13-------
null:12-------
null:11-------
null:10-------
5:9-------
5:8-------
5:7-------
5:6-------
5:5-------
5:4-------8:4-------
4:3-------5:3-------6:3-------7:3-------8:3-------
1:2-------2:2-------4:2-------5:2-------6:2-------7:2-------8:2-------
1:1-------2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------
{ data: 1; levels: 3 } { data: 2; levels: 3 } { data: 3; levels: 2 } { data: 4; levels: 4 } { data: 5; levels: 10 } { data: 6; levels: 4 } { data: 7; levels: 4 } { data: 8; levels: 5 }
null:15-------
null:14-------
null:13-------
null:12-------
null:11-------
null:10-------
null:9-------
null:8-------
null:7-------
null:6-------
null:5-------
5:4-------
3:3-------5:3-------
3:2-------4:2-------5:2-------7:2-------8:2-------
2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------
`
代碼來源github葵蒂，并非本人編寫：https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList2.java
總結(jié)
- 什么是跳表交播？
跳表，全程：跳躍鏈表践付，在計(jì)算機(jī)科學(xué)中堪侯，跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個(gè)元素的有序序列的查找和插入操作的平均時(shí)間復(fù)雜度都是：
- 跳表的時(shí)間/空間復(fù)雜度
時(shí)間復(fù)雜度：<font color='red' size=4 >O(logn)</font>荔仁，空間復(fù)雜度：<font color='red' size=4 >O(n)</font>，空間復(fù)雜度會(huì)隨著索引間隔距離的增大而減少芽死，但是空間復(fù)雜度的趨勢還是O(n)不變乏梁，由于索引層存儲(chǔ)的信息相對(duì)于原始鏈表來說會(huì)少很多，所以即使是O(n)的空間復(fù)雜度关贵，也是可以接受的遇骑。
- 跳表的應(yīng)用
1.redis的有序集合。
2.google開源的key/value存儲(chǔ)引擎揖曾。
3.HBase MemStore 內(nèi)部存儲(chǔ)結(jié)構(gòu)
- 跳表的動(dòng)態(tài)更新
由于跳表是由多層索引組成的落萎，所以再頻繁插入的時(shí)候會(huì)導(dǎo)致某一端相鄰索引結(jié)點(diǎn)之前的數(shù)據(jù)過多亥啦，最壞情nixuefeileam況下，會(huì)導(dǎo)致所有的數(shù)據(jù)都集中在某一段相鄰索引結(jié)點(diǎn)之間练链，這將會(huì)導(dǎo)致跳表退化成普通鏈表翔脱，時(shí)間復(fù)雜度也會(huì)退化到O(n)，所以這個(gè)時(shí)候就需要?jiǎng)討B(tài)的去更新跳表中的索引結(jié)點(diǎn)媒鼓，目前通過隨機(jī)函數(shù)實(shí)現(xiàn)届吁。
- 為什么redis采用跳表實(shí)現(xiàn)有序集合？
1.跳表是鏈表+多級(jí)索引組成的數(shù)據(jù)結(jié)構(gòu)绿鸣，通過空間換時(shí)間的設(shè)計(jì)思路疚沐，實(shí)現(xiàn)了基于鏈表的“二分查找”，查找潮模、刪除亮蛔、插入時(shí)間復(fù)雜度皆為：O(logn)。
2.跳表實(shí)現(xiàn)方式相對(duì)于B樹擎厢、紅黑樹究流、AVL樹等簡單許多，這幾種樹的平衡維護(hù)相當(dāng)麻煩锉矢，而跳表的動(dòng)態(tài)索引更新相對(duì)來說就簡單很多了梯嗽。
3.跳表的區(qū)間查找要比紅黑樹等優(yōu)秀。
朋友沽损，你學(xué)廢了嗎灯节？
本文由博客群發(fā)一文多發(fā)等運(yùn)營工具平臺(tái) OpenWrite 發(fā)布
