Skip List的工作原理
Skip List（跳躍表）是一種支持快速查找的數(shù)據(jù)結(jié)構(gòu)，插入、查找和刪除操作都僅僅只需要O(log n)對(duì)數(shù)級(jí)別的時(shí)間復(fù)雜度，它的效率甚至可以與紅黑樹(shù)等二叉平衡樹(shù)相提并論，而且實(shí)現(xiàn)的難度要比紅黑樹(shù)簡(jiǎn)單多了。
Skip List主要思想是將鏈表與二分查找相結(jié)合，它維護(hù)了一個(gè)多層級(jí)的鏈表結(jié)構(gòu)（用空間換取時(shí)間），可以把Skip List看作一個(gè)含有多個(gè)行的鏈表集合，每一行就是一條鏈表，這樣的一行鏈表被稱(chēng)為一層，每一層都是下一層的"快速通道"，即如果x層和y層都含有元素a，那么x層的a會(huì)與y層的a相互連接（垂直）。最底層的鏈表是含有所有節(jié)點(diǎn)的普通序列，而越接近頂層的鏈表，含有的節(jié)點(diǎn)則越少。
[圖片上傳失敗...(image-1a72d5-1514724423133)]
對(duì)一個(gè)目標(biāo)元素的搜索會(huì)從頂層鏈表的頭部元素開(kāi)始，然后遍歷該鏈表，直到找到元素大于或等于目標(biāo)元素的節(jié)點(diǎn)，如果當(dāng)前元素正好等于目標(biāo)，那么就直接返回它。如果當(dāng)前元素小于目標(biāo)元素，那么就垂直下降到下一層繼續(xù)搜索，如果當(dāng)前元素大于目標(biāo)或到達(dá)鏈表尾部，則移動(dòng)到前一個(gè)節(jié)點(diǎn)的位置，然后垂直下降到下一層。正因?yàn)镾kip List的搜索過(guò)程會(huì)不斷地從一層跳躍到下一層的，所以被稱(chēng)為跳躍表。
Skip List還有一個(gè)明顯的特征，即它是一個(gè)不準(zhǔn)確的概率性結(jié)構(gòu)，這是因?yàn)镾kip List在決定是否將節(jié)點(diǎn)冗余復(fù)制到上一層的時(shí)候（而在到達(dá)或超過(guò)頂層時(shí)，需要構(gòu)建新的頂層）依賴(lài)于一個(gè)概率函數(shù)，舉個(gè)栗子，我們使用一個(gè)最簡(jiǎn)單的概率函數(shù)：丟硬幣，即概率P為0.5，那么依賴(lài)于該概率函數(shù)實(shí)現(xiàn)的Skip List會(huì)不斷地"丟硬幣"，如果硬幣為正面就將節(jié)點(diǎn)復(fù)制到上一層，直到硬幣為反。
理解Skip List的原理并不困難，下面我們將使用Java來(lái)動(dòng)手實(shí)現(xiàn)一個(gè)支持基本需求（查找，插入和刪除）的Skip List。
本文作者為SylvanasSun(sylvanas.sun@gmail.com)，首發(fā)于SylvanasSun’s Blog。
原文鏈接：https://sylvanassun.github.io/2017/12/31/2017-12-31-skip_list/
（轉(zhuǎn)載請(qǐng)務(wù)必保留本段聲明，并且保留超鏈接。）
節(jié)點(diǎn)與基本實(shí)現(xiàn)
對(duì)于一個(gè)普通的鏈表節(jié)點(diǎn)一般只含有一個(gè)指向后續(xù)節(jié)點(diǎn)的指針（雙向鏈表的節(jié)點(diǎn)含有兩個(gè)指針，一個(gè)指向前節(jié)點(diǎn)，一個(gè)指向后節(jié)點(diǎn)），由于Skip List是一個(gè)多層級(jí)的鏈表結(jié)構(gòu)，我們的設(shè)計(jì)要讓節(jié)點(diǎn)擁有四個(gè)指針，分別對(duì)應(yīng)該節(jié)點(diǎn)的前后左右，為了方便地將頭鏈表永遠(yuǎn)置于頂層，還需要設(shè)置一個(gè)int屬性表示該鏈表所處的層級(jí)。
protected static class Node<K extends Comparable<K>, V> {
private K key;
private V value;
private int level; // 該節(jié)點(diǎn)所處的層級(jí)
private Node<K, V> up, down, next, previous;
public Node(K key, V value, int level) {
this.key = key;
this.value = value;
this.level = level;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Node[")
.append("key:");
if (this.key == null)
sb.append("None");
else
sb.append(this.key.toString());
sb.append(" value:");
if (this.value == null)
sb.append("None");
else
sb.append(this.value.toString());
sb.append("]");
return sb.toString();
}
// 余下都是get,set方法, 這里省略
.....
}
接下來(lái)是SkipList的基本實(shí)現(xiàn)，為了能夠讓Key進(jìn)行比較，我們規(guī)定Key的類(lèi)型必須實(shí)現(xiàn)了Comparable接口，同時(shí)為了支持ForEach循環(huán)，該類(lèi)還實(shí)現(xiàn)了Iterable接口。
public class SkipList<K extends Comparable<K>, V> implements Iterable<K> {
// 一個(gè)隨機(jī)數(shù)生成器
protected static final Random randomGenerator = new Random();
// 默認(rèn)的概率
protected static final double DEFAULT_PROBABILITY = 0.5;
// 頭節(jié)點(diǎn)
private Node<K, V> head;
private double probability;
// SkipList中的元素?cái)?shù)量（不計(jì)算多個(gè)層級(jí)中的冗余元素）
private int size;
public SkipList() {
this(DEFAULT_PROBABILITY);
}
public SkipList(double probability) {
this.head = new Node<K, V>(null, null, 0);
this.probability = probability;
this.size = 0;
}
.....
}
我們還需要定義幾個(gè)輔助方法，如下所示（都很簡(jiǎn)單）：
// 對(duì)key進(jìn)行檢查
// 因?yàn)槊織l鏈表的頭節(jié)點(diǎn)就是一個(gè)key為null的節(jié)點(diǎn)，所以不允許其他節(jié)點(diǎn)的key也為null
protected void checkKeyValidity(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
// a是否小于等于b
protected boolean lessThanOrEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
// 概率函數(shù)
protected boolean isBuildLevel() {
return randomGenerator.nextDouble() < probability;
}
// 將y水平插入到x的后面
protected void horizontalInsert(Node<K, V> x, Node<K, V> y) {
y.setPrevious(x);
y.setNext(x.getNext());
if (x.getNext() != null)
x.getNext().setPrevious(y);
x.setNext(y);
}
// x與y進(jìn)行垂直連接
protected void verticalLink(Node<K, V> x, Node<K, V> y) {
x.setDown(y);
y.setUp(x);
}
查找
查找一個(gè)節(jié)點(diǎn)的過(guò)程如下：
從頂層鏈表的頭部開(kāi)始進(jìn)行遍歷，比較每一個(gè)節(jié)點(diǎn)的元素與目標(biāo)元素的大小。
如果當(dāng)前元素小于目標(biāo)元素，則繼續(xù)遍歷。
如果當(dāng)前元素等于目標(biāo)元素，返回該節(jié)點(diǎn)。
如果當(dāng)前元素大于目標(biāo)元素，移動(dòng)到前一個(gè)節(jié)點(diǎn)（必須小于等于目標(biāo)元素），然后跳躍到下一層繼續(xù)遍歷。
如果遍歷至鏈表尾部，跳躍到下一層繼續(xù)遍歷。
protected Node<K, V> findNode(K key) {
Node<K, V> node = head;
Node<K, V> next = null;
Node<K, V> down = null;
K nodeKey = null;
while (true) {
// 不斷遍歷直到遇見(jiàn)大于目標(biāo)元素的節(jié)點(diǎn)
next = node.getNext();
while (next != null && lessThanOrEqual(next.getKey(), key)) {
node = next;
next = node.getNext();
}
// 當(dāng)前元素等于目標(biāo)元素，中斷循環(huán)
nodeKey = node.getKey();
if (nodeKey != null && nodeKey.compareTo(key) == 0)
break;
// 否則，跳躍到下一層級(jí)
down = node.getDown();
if (down != null) {
node = down;
} else {
break;
}
}
return node;
}
public V get(K key) {
checkKeyValidity(key);
Node<K, V> node = findNode(key);
// 如果找到的節(jié)點(diǎn)并不等于目標(biāo)元素，則目標(biāo)元素不存在于SkipList中
if (node.getKey().compareTo(key) == 0)
return node.getValue();
else
return null;
}
插入
插入操作的過(guò)程要稍微復(fù)雜些，主要在于復(fù)制節(jié)點(diǎn)到上一層與構(gòu)建新層的操作上。
public void add(K key, V value) {
checkKeyValidity(key);
// 直接找到key，然后修改對(duì)應(yīng)的value即可
Node<K, V> node = findNode(key);
if (node.getKey() != null && node.getKey().compareTo(key) == 0) {
node.setValue(value);
return;
}
// 將newNode水平插入到node之后
Node<K, V> newNode = new Node<K, V>(key, value, node.getLevel());
horizontalInsert(node, newNode);
int currentLevel = node.getLevel();
int headLevel = head.getLevel();
while (isBuildLevel()) {
// 如果當(dāng)前層級(jí)已經(jīng)到達(dá)或超越頂層
// 那么需要構(gòu)建一個(gè)新的頂層
if (currentLevel >= headLevel) {
Node<K, V> newHead = new Node<K, V>(null, null, headLevel + 1);
verticalLink(newHead, head);
head = newHead;
headLevel = head.getLevel();
}
// 找到node對(duì)應(yīng)的上一層節(jié)點(diǎn)
while (node.getUp() == null) {
node = node.getPrevious();
}
node = node.getUp();
// 將newNode復(fù)制到上一層
Node<K, V> tmp = new Node<K, V>(key, value, node.getLevel());
horizontalInsert(node, tmp);
verticalLink(tmp, newNode);
newNode = tmp;
currentLevel++;
}
size++;
}
刪除
對(duì)于刪除一個(gè)節(jié)點(diǎn)，需要先找到節(jié)點(diǎn)所在的位置（位于最底層鏈表中的位置），之后再自底向上地刪除該節(jié)點(diǎn)在每一行中的冗余復(fù)制。
public void remove(K key) {
checkKeyValidity(key);
Node<K, V> node = findNode(key);
if (node == null || node.getKey().compareTo(key) != 0)
throw new NoSuchElementException("The key is not exist!");
// 移動(dòng)到最底層
while (node.getDown() != null)
node = node.getDown();
// 自底向上地進(jìn)行刪除
Node<K, V> prev = null;
Node<K, V> next = null;
for (; node != null; node = node.getUp()) {
prev = node.getPrevious();
next = node.getNext();
if (prev != null)
prev.setNext(next);
if (next != null)
next.setPrevious(prev);
}
// 對(duì)頂層鏈表進(jìn)行調(diào)整，去除無(wú)效的頂層鏈表
while (head.getNext() == null && head.getDown() != null) {
head = head.getDown();
head.setUp(null);
}
size--;
}
迭代器
由于我們的SkipList實(shí)現(xiàn)了Iterable接口，所以還需要實(shí)現(xiàn)一個(gè)迭代器。對(duì)于迭代一個(gè)Skip List，只需要找到最底層的鏈表并且移動(dòng)到它的首節(jié)點(diǎn)，然后進(jìn)行遍歷即可。
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<K, V> node = head;
// 移動(dòng)到最底層
while (node.getDown() != null)
node = node.getDown();
while (node.getPrevious() != null)
node = node.getPrevious();
// 第一個(gè)節(jié)點(diǎn)是頭部節(jié)點(diǎn)，沒(méi)有任何意義，所以需要移動(dòng)到后一個(gè)節(jié)點(diǎn)
if (node.getNext() != null)
node = node.getNext();
// 遍歷
while (node != null) {
sb.append(node.toString()).append("\n");
node = node.getNext();
}
return sb.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private Node<K, V> node;
public SkipListIterator(Node<K, V> node) {
while (node.getDown() != null)
node = node.getDown();
while (node.getPrevious() != null)
node = node.getPrevious();
if (node.getNext() != null)
node = node.getNext();
this.node = node;
}
@Override
public boolean hasNext() {
return this.node != null;
}
@Override
public K next() {
K result = node.getKey();
node = node.getNext();
return result;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
本文中實(shí)現(xiàn)的SkipList完整代碼地址
