一、什么是跳表
skiplist本質(zhì)上也是一種查找結構，用于解決算法中的查找問題，跟平衡搜索樹和哈希表的價值是
一樣的，可以作為key或者key/value的查找模型。那么相比而言它的優(yōu)勢是什么的呢？這么等我
們學習完它的細節(jié)實現(xiàn)，我們再來對比。
skiplist 是由 William Pugh 發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文 《Skip Lists: AProbabilistic Alternative to Balanced Trees》
skiplist，顧名思義，首先它是一個list。實際上，它是在有序鏈表的基礎上發(fā)展起來的。如果是一
個有序的鏈表，查找數(shù)據(jù)的時間復雜度是O(N)。
William Pugh開始的優(yōu)化思路：
- 假如我們每相鄰兩個節(jié)點升高一層，增加一個指針，讓指針指向下下個節(jié)點，如下圖b所示。這樣所有新增加的指針連成了一個新的鏈表，但它包含的節(jié)點個數(shù)只有原來的一半。由于新增加的指針，我們不再需要與鏈表中每個節(jié)點逐個進行比較了，需要比較的節(jié)點數(shù)大概只有原來的一半。
- 以此類推，我們可以在第二層新產(chǎn)生的鏈表上，繼續(xù)為每相鄰的兩個節(jié)點升高一層，增加一個指針，從而產(chǎn)生第三層鏈表。如下圖c，這樣搜索效率就進一步提高了。
- skiplist正是受這種多層鏈表的想法的啟發(fā)而設計出來的。實際上，按照上面生成鏈表的方式，上面每一層鏈表的節(jié)點個數(shù)，是下面一層的節(jié)點個數(shù)的一半，這樣查找過程就非常類似二分查找，使得查找的時間復雜度可以降低到O(log n)。但是這個結構在插入刪除數(shù)據(jù)的時候有很大的問題，插入或者刪除一個節(jié)點之后，就會打亂上下相鄰兩層鏈表上節(jié)點個數(shù)嚴格的2:1的對應關系。如果要維持這種對應關系，就必須把新插入的節(jié)點后面的所有節(jié)點（也包括新插入的節(jié)點）重新進行調(diào)整，這會讓時間復雜度重新蛻化成O(n)。
查找的過程：假如要查找的值是key，那么需要看下一個節(jié)點的值是否比key大，如果比key大， 就向下走。如果比key小，就向右走。如果沒有找到，就會走到第-1層。
skiplist的設計為了避免這種問題，做了一個大膽的處理，不再嚴格要求對應比例關系，而是插入一個節(jié)點的時候隨機出一個層數(shù)。這樣每次插入和刪除都不需要考慮其他節(jié)點的層數(shù)，這樣就好處理多了。細節(jié)過程入下圖：
二、跳表的效率如何保證？
上面我們說到，skiplist插入一個節(jié)點時隨機出一個層數(shù)，聽起來怎么這么隨意，如何保證搜索時的效率呢？
這里首先要細節(jié)分析的是這個隨機層數(shù)是怎么來的。一般跳表會設計一個最大層數(shù)maxLevel的限制，其次會設置一個多增加一層的概率p。那么計算這個隨機層數(shù)的偽代碼如下圖：在 Redis 的 skiplist 實現(xiàn)中，這兩個參數(shù)的取值為：
p = 1/4和maxLevel = 32。注：谷歌的開源項目 LevelDB（小型的 KV 型數(shù)據(jù)庫）也采用了 skiplist，有興趣的大佬可以了解一下！
根據(jù)前面randomLevel()的偽碼，我們很容易看出，產(chǎn)生越高的節(jié)點層數(shù)，概率越低。定量的分析
如下：
- 節(jié)點層數(shù)至少為1。而大于1的節(jié)點層數(shù)，滿足一個概率分布。
- 節(jié)點層數(shù)恰好等于1的概率為1-p。
- 節(jié)點層數(shù)大于等于2的概率為p，而節(jié)點層數(shù)恰好等于2的概率為p(1-p)。
- 節(jié)點層數(shù)大于等于3的概率為p2，而節(jié)點層數(shù)恰好等于3的概率為p2*(1-p)。
- 節(jié)點層數(shù)大于等于4的概率為p3，而節(jié)點層數(shù)恰好等于4的概率為p3*(1-p)
- …
因此，一個節(jié)點的平均層數(shù)（也包含的平均指針數(shù)目）計算如下：
現(xiàn)在很容易計算出：
- 當p=1/2時，每個節(jié)點所包含的平均指針數(shù)目為2；
- 當p=1/4時，每個節(jié)點所包含的平均指針數(shù)目為1.33。
跳表的平均時間復雜度為O(logN)，這個推導的過程比較復雜，這里我們稍微提一下。
三、skiplist的實現(xiàn)
結點的設計
struct SkiplistNode
{
int _val;
vector<SkiplistNode*> _nextV;
SkiplistNode(int val, int level)
:_val(val)
, _nextV(level, nullptr)
{}
};
因為每個結點的層數(shù)是隨機的，所以申請一個新節(jié)點需要知道其層數(shù)和存儲的值，通過vector的下標可以表示層數(shù)。
整體設計
class Skiplist {
typedef SkiplistNode Node;
public:
Skiplist() {
srand(time(0));
// 頭節(jié)點，層數(shù)是1
_head = new SkiplistNode(-1, 1);
}
private:
Node* _head; // 哨兵位頭節(jié)點
size_t _maxLevel = 32; // 最高的層數(shù)
double _p = 0.25; // 增加一層的概率
};
哨兵位頭節(jié)點的層數(shù)是該跳表中最高的，初始時讓哨兵位的層數(shù)為1.增加一層的概率是0.25，理論而言，概率越大，效率越高。
節(jié)點的隨機層數(shù)
計算這個隨機層數(shù)的偽代碼如下圖：
C語言產(chǎn)生隨機數(shù)
int RandomLevel()
{
size_t level = 1;
// rand() ->[0, RAND_MAX]之間
// rand() 《= RAND_MAX*_p 可以保證增加一層的概率是_p
// level <= maxLevel 保證隨機層數(shù)不超過最高層數(shù)maxLevel
while (rand() <= RAND_MAX*_p && level < _maxLevel)
{
++level;
}
return level;
}
C++產(chǎn)生隨機數(shù)
int RandomLevel()
{
static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
static std::uniform_real_distribution<double> distribution(0.0, 1.0);
size_t level = 1;
while (distribution(generator) <= _p && level < _maxLevel)
{
++level;
}
return level;
}
這里我們需要注意的是：因為C語言產(chǎn)生的隨機數(shù)范圍是0到32767之間的數(shù)，范圍比較小。不過可以通過加減一些數(shù)來擴大隨機數(shù)的范圍。
skiplist的查找
查找的過程:查找是要和下一個節(jié)點的值相比，并不是和當前節(jié)點的值相比一開始cur在哨兵位頭節(jié)點的最高層 head，開始進行比較。假如要查找的值為target，如果下一個節(jié)點為空或者下一個節(jié)點的值比target大，那么cur需要向下一層走;如果下一個節(jié)點的值比target下，那么cur向右走。重復上述過程，直至找到或者沒找到(沒找到的話，cur會去到第-1層，注:層數(shù)是從第0層開始的)
bool search(int target) {
Node* cur = _head;
int level = _head->_nextV.size() - 1;
while (level >= 0)
{
// 目標值比下一個節(jié)點值要大，向右走
// 下一個節(jié)點是空(尾)，目標值比下一個節(jié)點值要小，向下走
if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
{
// 向右走
cur = cur->_nextV[level];
}
else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
{
// 向下走
--level;
}
else
{
return true;
}
}
return false;
}
skiplist的插入
無論是插入值還是刪除值，都需要找到該值的前面的節(jié)點，這樣才能修改指針的指向關系。我們可以將這個保存前一個指針的操作封裝成一個函數(shù)，提供給插入和刪除接口使用。
vector<Node*> FindPrevNode(int num)
{
Node* cur = _head;
int level = _head->_nextV.size() - 1;
// 插入位置每一層前一個節(jié)點指針
vector<Node*> prevV(level + 1, _head);
while (level >= 0)
{
// 目標值比下一個節(jié)點值要大，向右走
// 下一個節(jié)點是空(尾)，目標值比下一個節(jié)點值要小，向下走
if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
{
// 向右走
cur = cur->_nextV[level];
}
else if (cur->_nextV[level] == nullptr
|| cur->_nextV[level]->_val >= num)
{
// 更新level層前一個
prevV[level] = cur;
// 向下走
--level;
}
}
return prevV;
}
void add(int num) {
vector<Node*> prevV = FindPrevNode(num);
int n = RandomLevel();
Node* newnode = new Node(num, n);
// 如果n超過當前最大的層數(shù)，那就升高一下_head的層數(shù)
if (n > _head->_nextV.size())
{
_head->_nextV.resize(n, nullptr);
prevV.resize(n, _head);
}
// 鏈接前后節(jié)點
for (size_t i = 0; i < n; ++i)
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}
刪除節(jié)點
bool erase(int num) {
vector<Node*> prevV = FindPrevNode(num);
// 第一層下一個不是val，val不在表中
if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
{
return false;
}
else
{
Node* del = prevV[0]->_nextV[0];
// del節(jié)點每一層的前后指針鏈接起來
for (size_t i = 0; i < del->_nextV.size(); i++)
{
prevV[i]->_nextV[i] = del->_nextV[i];
}
delete del;
// 如果刪除最高層節(jié)點，把頭節(jié)點的層數(shù)也降一下
int i = _head->_nextV.size() - 1;
while (i >= 0)
{
if (_head->_nextV[i] == nullptr)
--i;
else
break;
}
_head->_nextV.resize(i + 1);
return true;
}
注意：如果刪除的節(jié)點的層數(shù)是最高的，那么可以將哨兵位頭結點的層數(shù)降一降。如何判斷刪除的節(jié)點層數(shù)是不是最高的呢？從哨兵位頭結點的最高層其，如果該層的指針指向空，那么就說明刪除的節(jié)點層數(shù)最高。當前層指針指向空，那么就需要看下一層指針是否指向空。以此類推，直至指針不在指向空，那么就可以求出刪除最高節(jié)點后剩余節(jié)點的最高層數(shù)了。
打印跳表
void Print()
{
Node* cur = _head;
while (cur)
{
printf("%2d\n", cur->_val);
// 打印每個每個cur節(jié)點
for (auto e : cur->_nextV)
{
printf("%2s", "↓");
}
printf("\n");
cur = cur->_nextV[0];
}
}
打印跳表函數(shù)可以讓我們更好的觀察跳表的樣子。
完整代碼文章來源：http://www.zghlxwxcb.cn/news/detail-600168.html
#include <iostream>
#include <vector>
#include <time.h>
#include <random>
#include <chrono>
using namespace std;
struct SkiplistNode
{
int _val;
vector<SkiplistNode*> _nextV;
SkiplistNode(int val, int level)
:_val(val)
, _nextV(level, nullptr)
{}
};
class Skiplist {
typedef SkiplistNode Node;
public:
Skiplist() {
srand(time(0));
// 頭節(jié)點，層數(shù)是1
_head = new SkiplistNode(-1, 1);
}
bool search(int target) {
Node* cur = _head;
int level = _head->_nextV.size() - 1;
while (level >= 0)
{
// 目標值比下一個節(jié)點值要大，向右走
// 下一個節(jié)點是空(尾)，目標值比下一個節(jié)點值要小，向下走
if (cur->_nextV[level] && cur->_nextV[level]->_val < target)
{
// 向右走
cur = cur->_nextV[level];
}
else if (cur->_nextV[level] == nullptr || cur->_nextV[level]->_val > target)
{
// 向下走
--level;
}
else
{
return true;
}
}
return false;
}
vector<Node*> FindPrevNode(int num)
{
Node* cur = _head;
int level = _head->_nextV.size() - 1;
// 插入位置每一層前一個節(jié)點指針
vector<Node*> prevV(level + 1, _head);
while (level >= 0)
{
// 目標值比下一個節(jié)點值要大，向右走
// 下一個節(jié)點是空(尾)，目標值比下一個節(jié)點值要小，向下走
if (cur->_nextV[level] && cur->_nextV[level]->_val < num)
{
// 向右走
cur = cur->_nextV[level];
}
else if (cur->_nextV[level] == nullptr
|| cur->_nextV[level]->_val >= num)
{
// 更新level層前一個
prevV[level] = cur;
// 向下走
--level;
}
}
return prevV;
}
void add(int num) {
vector<Node*> prevV = FindPrevNode(num);
int n = RandomLevel();
Node* newnode = new Node(num, n);
// 如果n超過當前最大的層數(shù)，那就升高一下_head的層數(shù)
if (n > _head->_nextV.size())
{
_head->_nextV.resize(n, nullptr);
prevV.resize(n, _head);
}
// 鏈接前后節(jié)點
for (size_t i = 0; i < n; ++i)
{
newnode->_nextV[i] = prevV[i]->_nextV[i];
prevV[i]->_nextV[i] = newnode;
}
}
bool erase(int num) {
vector<Node*> prevV = FindPrevNode(num);
// 第一層下一個不是val，val不在表中
if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
{
return false;
}
else
{
Node* del = prevV[0]->_nextV[0];
// del節(jié)點每一層的前后指針鏈接起來
for (size_t i = 0; i < del->_nextV.size(); i++)
{
prevV[i]->_nextV[i] = del->_nextV[i];
}
delete del;
// 如果刪除最高層節(jié)點，把頭節(jié)點的層數(shù)也降一下
int i = _head->_nextV.size() - 1;
while (i >= 0)
{
if (_head->_nextV[i] == nullptr)
--i;
else
break;
}
_head->_nextV.resize(i + 1);
return true;
}
}
//int RandomLevel()
//{
// size_t level = 1;
// // rand() ->[0, RAND_MAX]之間
// while (rand() <= RAND_MAX*_p && level < _maxLevel)
// {
// ++level;
// }
// return level;
//}
int RandomLevel()
{
static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());
static std::uniform_real_distribution<double> distribution(0.0, 1.0);
size_t level = 1;
while (distribution(generator) <= _p && level < _maxLevel)
{
++level;
}
return level;
}
void Print()
{
/*int level = _head->_nextV.size();
for (int i = level - 1; i >= 0; --i)
{
Node* cur = _head;
while (cur)
{
printf("%d->", cur->_val);
cur = cur->_nextV[i];
}
printf("\n");
}*/
Node* cur = _head;
while (cur)
{
printf("%2d\n", cur->_val);
// 打印每個每個cur節(jié)點
for (auto e : cur->_nextV)
{
printf("%2s", "↓");
}
printf("\n");
cur = cur->_nextV[0];
}
}
private:
Node* _head;
size_t _maxLevel = 32;
double _p = 0.5;
};
四、skiplist跟平衡搜索樹和哈希表的對比
- skiplist 相比平衡搜索樹(AVL 樹和紅黑樹)對比，都可以做到遍歷數(shù)據(jù)有序，時間復雜度也差不多。skiplist 的優(yōu)勢是：a、skiplist 實現(xiàn)簡單，容易控制。平衡樹增刪查改遍歷都更復雜。b、skiplist 的額外空間消耗更低。平衡樹節(jié)點存儲每個值有三叉鏈，平衡因子或者顏色等消耗。skiplist 中 p = 1 / 2 時，每個節(jié)點所包含的平均指針數(shù)目為 2；skiplist 中 p = 1 / 4 時，每個節(jié)點所包含的平均指針數(shù)目為 1.33；
- skiplist 相比哈希表而言，就沒有那么大的優(yōu)勢了。相比而言，a、哈希表平均時間復雜度是 O(1)，比 skiplist快。b、哈希表空間消耗略多一點。skiplist 優(yōu)勢如下：a、遍歷數(shù)據(jù)有序。b、skiplist 空間消耗略小一點，哈希表存在鏈接指針和表空間消耗。c、哈希表擴容有性能損耗。d、哈希表在極端場景下哈希沖突高，效率下降厲害，需要紅黑樹補足接力。
文章來源地址http://www.zghlxwxcb.cn/news/detail-600168.html
到了這里，關于【高階數(shù)據(jù)結構】跳表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
