跳躍表的分析與實現

跳躍表的簡單介紹

跳躍列表一個有序鏈表，按層建造的。底層是一個普通的有序鏈表。每個更高層都充當下麵列表的"快速跑道"，查找一個元素時，可以先通過高層的“快車道”，在快車道上找不到時，從最接近目標元素的快車道逐步進入慢車道，直到最後找的目標元素。
分析的時候，常用的形狀如下：  

各層是完全分開的列表。但是在實際實現中，則使用的為如下結構：

這種方式將多條聯表的值合並到一起，同時使用指針來構造高層"快車道"。這種方式管理起來簡單，節省空間。

更詳細的介紹，請看跳表SkipList。

跳躍表的複雜度分析以及概率因子p

來看看跳躍表的複雜度分析:

• 空間複雜度： O(n) （期望）
• 跳躍表高度： O(logn) （期望）

相關操作的時間複雜度：

• 查找： O(logn) （期望）
• 插入： O(logn) （期望）
• 刪除： O(logn) （期望）

跳躍表的操作時間負責度是基於概率的，所有加上了期望。
在層 i 中的元素按某個固定的概率 p 出現在層 i+1 中。當p=1/2或者1/e的時候查找的性能最好。

更詳細的對比，請看到這篇文章：跳躍表，當中對不同概率的P對查詢性能的影響做了對比。

跳躍表的高度

實際使用時，如果高度太高，會造成空間浪費，我們要做一個空間和時間的平衡。那麼跳躍表的高度多少最合適？
假設跳躍表中的元素個數為N，當跳躍表的高度為log(N)時，跳躍表進化為一個二叉樹結構，其查詢次數與二分查找法一致。這無疑最理想的結果。

如果有一億條記錄，高度log(N)約等於30。redis中，最大高度也就是32，最多可以存幾億條記錄。通常，我們用不了這麼多記錄。所以高度可以降低一點。

跳躍表的實現

跳躍表在levledb和redis中均有實現。二者都是用C實現的。我這個實現是C++版本的

• skiplist
• skiplist0.2。

主要特點為：

• 支持模板
• 0.2版本增加了對迭代器和反向迭代器的支持
• 可自定義高度，默認為8，0.2版本版本改為了16
  因為高度為8的話適合幾百條的記錄，這時候，選用跳躍表並沒有太多優勢，不如之間使用排序數組。將默認值改為16的話，可以方便幾萬條記錄大小的地方使用。
• 概率p:暫時使用p=1/2
• 做過單元測試，放心使用啦

初始版本簡單直接，支持的函數為insert,find,remove。不支持範圍操作。0.2版本增了對了迭代器的支持。
另外，在實現的時候也遇到一些問題，要注意模板編程與平時編程有所不同，平時編程通常實現和定義分離，分別放在.cpp和.h中。但是模板編程編寫的通常是沒有具現的實現，為了方便，一般定義和實現都會放在.h文件中。

初始版本簡單直接，支持的函數為insert,find,remove。不再介紹。下麵是0.2版本實現的函數及其功能：
void insert(const_value_type &value)
在當前表中插入value值。值可以重複。
void remove(const_value_type &value)
刪除第一個值為value的元素。重複值需要多次刪除
void clear()
清空跳躍表
iterator find(const_value_type &value)
返回第一個值為value的元素的迭代器，否則返回end.
iterator begin(int level = 0)
返回指向當前表中第level層的第一個元素的迭代器。使用begin的時候，可以指定遍曆不同的層，默認為最底層。這個實際上並不是標準的迭代器，為了實現分層遍曆進行了特化。
iterator end() const
返回指向當前表中最後一個元素的迭代器。
iterator rbegin() const
返回指向當前表中最後一個元素的反向迭代器。
iterator rend() const
返回指向表中第一個元素的反向迭代器。
unsigned long size()
返回當前表中元素的數目
unsigned int level()
返回當前表的總層數
unsigned int maxlevel()
返回當前表的能使用的最大層數
bool empty()
判斷表是否為空

代碼地址見上麵的鏈接。

---

歡迎光臨我的網站----蝴蝶忽然的博客園----人既無名的專欄。
如果閱讀本文過程中有任何問題，請聯係作者，轉載請注明出處！