前言
在頭條創(chuàng)作了一個(gè)月左右的時(shí)間，收獲了50+粉絲，很是開(kāi)心，我會(huì)把數(shù)據(jù)結(jié)構(gòu)與算法的文章更新到底，第一次看我文章的同仁如果覺(jué)得不錯(cuò)的話(huà)就關(guān)注一下我哦，你的支持就是我創(chuàng)作的動(dòng)力。
一、什么是跳表
我們?cè)谥敖榻B了十分優(yōu)秀的二分查找算法，但是它只能作用于有序數(shù)組上，查找起來(lái)比較方便，但是數(shù)組中插入和刪除元素是比較麻煩的；那么有沒(méi)有辦法讓二分查找也能作用于有序鏈表上，從而達(dá)到查找、插入和刪除元素都十分的快速呢？
對(duì)于普通的有序列表來(lái)說(shuō)，當(dāng)然不能實(shí)現(xiàn)我們的目標(biāo)，如下查找的時(shí)間復(fù)雜度為O(n)；
原始有序單鏈表
我們可以基于原始鏈表建立一個(gè) 索引層，比如每?jī)蓚€(gè)節(jié)點(diǎn)提取一個(gè)節(jié)點(diǎn)到索引層：
帶一級(jí)索引的跳表
如此，兩種數(shù)據(jù)結(jié)構(gòu)我們查找元素16的比較次數(shù)分別為10次和8次，確實(shí)能提高查詢(xún)速度；我們更近一步，再次建立第二級(jí)索引：
帶二級(jí)索引的跳表 帶二級(jí)索引的跳表
此時(shí)查找元素16比較的次數(shù)只需要比較7次即可；
如果在大數(shù)據(jù)量的有序鏈表中，我們建立很多層索引，使得最高層索引只有兩個(gè)節(jié)點(diǎn)，那么就實(shí)現(xiàn)了類(lèi)似二分查找的算法思想，此時(shí)這種數(shù)據(jù)結(jié)構(gòu)就被成為跳表。
二、跳表性能分析
2.1 時(shí)間復(fù)雜度
假設(shè)有序鏈表總節(jié)點(diǎn)個(gè)數(shù)為n，我們建立索引時(shí)每?jī)蓚€(gè)節(jié)點(diǎn)提取一個(gè)索引節(jié)點(diǎn)；那么第一級(jí)索引共有n/2個(gè)節(jié)點(diǎn)；
第k級(jí)索引共有（n/2^k）個(gè)節(jié)點(diǎn)，假設(shè)k為最高級(jí)索引，為2個(gè)節(jié)點(diǎn)，那么2=(n/2^k)，n=2(k+1)，k=logn-1，如果原始鏈表也算進(jìn)去的話(huà)，k=logn正好是整個(gè)數(shù)據(jù)結(jié)構(gòu)的高度。
假設(shè)每一層需要遍歷m個(gè)節(jié)點(diǎn)，那么時(shí)間復(fù)雜度就可以表示為O(mlogn)，但是推斷m是常量級(jí)別的，因此可以忽略，那么整個(gè)查找過(guò)程時(shí)間復(fù)雜度就是O(logn)，竟然和二分查找是一樣的高效！
2.2 空間復(fù)雜度
第一級(jí)索引需要n/2個(gè)節(jié)點(diǎn)，第二級(jí)需要n/2^2個(gè)節(jié)點(diǎn)，依次類(lèi)推，第k級(jí)索引需要的節(jié)點(diǎn)個(gè)數(shù)為n/2^k，這正好是一個(gè)等比數(shù)列，等比數(shù)列求和的結(jié)果是n-2，所以空間復(fù)雜度為O(n)，這是一個(gè)以空間換時(shí)間的策略；
我們可以每3個(gè)節(jié)點(diǎn)或者每4個(gè)節(jié)點(diǎn)往上提取一個(gè)索引節(jié)點(diǎn)，如此可以適當(dāng)減少需要的額外空間，但是空間復(fù)雜度仍然為O(n)；如果有序鏈表存儲(chǔ)的是大對(duì)象，那么索引節(jié)點(diǎn)中無(wú)需存放整個(gè)大對(duì)象，只要存儲(chǔ)對(duì)象的指針即可，所以此時(shí)空間復(fù)雜度就顯得不那么重要了；
2.3 跳表的插入和刪除
跳表因?yàn)槭琼樞蜴湵恚哉嬲迦牒蛣h除的時(shí)間復(fù)雜度都是O(1)，但是找到需要插入節(jié)點(diǎn)的位置或者找到待刪除的節(jié)點(diǎn)時(shí)間復(fù)雜度為O(logn)；
跳表在刪除的時(shí)候，除了需要?jiǎng)h除原始有序鏈表中的節(jié)點(diǎn)，還需要同步刪除k級(jí)索引中的全部該索引節(jié)點(diǎn)；
跳表在插入元素式，極端情況下會(huì)導(dǎo)致兩個(gè)索引節(jié)點(diǎn)中存在大量的原始節(jié)點(diǎn)，時(shí)間效率極有可能會(huì)退化為單鏈表的O(n)，所以需要?jiǎng)討B(tài)地平衡和更新k級(jí)索引節(jié)點(diǎn)；
三、跳表使用場(chǎng)景
redis在存儲(chǔ)有序集合的時(shí)候就用到了跳表+散列表的數(shù)據(jù)結(jié)構(gòu)，跳表和紅黑樹(shù)相比，插入、刪除、查找的時(shí)間復(fù)雜度相同，但是跳表在按照區(qū)間查找時(shí)明顯具有效率優(yōu)勢(shì)，而且跳表實(shí)現(xiàn)起來(lái)比紅黑樹(shù)要簡(jiǎn)單易懂，不容易出錯(cuò)。
紅黑樹(shù)等常用數(shù)據(jù)結(jié)構(gòu)在程序語(yǔ)言中都是封裝好的，我們想用的話(huà)直接拿來(lái)用即可，比如HashMap，但是跳表卻沒(méi)有對(duì)應(yīng)的封裝好的數(shù)據(jù)結(jié)構(gòu)，想用的話(huà)開(kāi)發(fā)者必須自己去實(shí)現(xiàn)。
四、代碼實(shí)現(xiàn)跳表Skiplist以及優(yōu)化
代碼來(lái)源于極客時(shí)間《數(shù)據(jù)結(jié)構(gòu)和算法之美》
github地址：
https://github.com/wangzheng0822/algo（數(shù)據(jù)結(jié)構(gòu)和算法必知必會(huì)的50個(gè)代碼實(shí)現(xiàn)）
4.1 作者王爭(zhēng)給出的跳表實(shí)現(xiàn)方式
/**
* 跳表的一種實(shí)現(xiàn)方法。
* 跳表中存儲(chǔ)的是正整數(shù)，并且存儲(chǔ)的是不重復(fù)的。
*
*/
public class SkipList {
private static final float SKIPLIST_P = 0.5f;
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node(); // 帶頭鏈表
public Node find(int value) {
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];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
public void insert(int value) {
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
// record every level largest value which smaller than insert value in update[]
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] = p;// use update save node in search path
}
// in search path node next node become new node forwords(next)
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
// update node hight
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];
}
}
}
while (levelCount>1&&head.forwards[levelCount]==null){
levelCount--;
}
}
// 理論來(lái)講，一級(jí)索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級(jí)索引中元素個(gè)數(shù)占 25%，三級(jí)索引12.5% ，一直到最頂層。
// 因?yàn)檫@里每一層的晉升概率是 50%。對(duì)于每一個(gè)新插入的節(jié)點(diǎn)，都需要調(diào)用 randomLevel 生成一個(gè)合理的層數(shù)。
// 該 randomLevel 方法會(huì)隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)，且 ：
// 50%的概率返回 1
// 25%的概率返回 2
// 12.5%的概率返回 3 ...
private int randomLevel() {
int level = 1;
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
public class Node {
private int data = -1;
private Node forwards[] = new Node[MAX_LEVEL];
private int maxLevel = 0;
@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();
}
}
}
4.2 作者ldb基于王爭(zhēng)的代碼給出的優(yōu)化
import JAVA.util.Random;
/**
* 1，跳表的一種實(shí)現(xiàn)方法，用于練習(xí)。跳表中存儲(chǔ)的是正整數(shù)，并且存儲(chǔ)的是不重復(fù)的。
* 2，本類(lèi)是參考作者zheng ，自己學(xué)習(xí)，優(yōu)化了添加方法
* 3，看完這個(gè)，我覺(jué)得再看ConcurrentSkipListMap 源碼，會(huì)有很大收獲
*/
public class SkipList2 {
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;
// 從最大層開(kāi)始查找，找到前一節(jié)點(diǎn)，通過(guò)--i，移動(dòng)到下層再開(kāi)始查找
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();
// 每次只增加一層，如果條件滿(mǎn)足
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;
// 從最大層開(kāi)始查找，找到前一節(jié)點(diǎn)，通過(guò)--i，移動(dòng)到下層再開(kāi)始查找
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();
// 每次只增加一層，如果條件滿(mǎn)足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node p = head;
// 從最大層開(kāi)始查找，找到前一節(jié)點(diǎn)，通過(guò)--i，移動(dòng)到下層再開(kāi)始查找
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)化后參見(jiàn)上面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，說(shuō)明：層是從下到上的，這里最下層編號(hào)是0，最上層編號(hào)是15
* 2，這里沒(méi)有從已有數(shù)據(jù)最大層（編號(hào)最大）開(kāi)始找，（而是隨機(jī)層的最大層）導(dǎo)致有些問(wèn)題。
* 如果數(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) {
SkipList2 list = new SkipList2();
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();
/**
* 結(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 }
*/
// 優(yōu)化后insert()
SkipList2 list2 = new SkipList2();
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();
}
}
