Go 實現跳躍表
簡介
跳躍表是一種可以用來替代平衡樹的數據結構，Redis 中的有序集合（zset）就是用 skiplist 來做排序的，在 leveldb 中也能看到 skiplist 的身影。本文介紹跳躍表的基本原理，然後用 Go 完成一個簡單的實現。
下面的圖片展示了一個典型的跳躍表：
跳躍表通過每個節點多出來的隨機個數的前進指針達到加快數據檢索的目的。與平衡樹嚴格是時間複雜度不同，跳躍表的這種加速是基於概率的，雖然最壞的情況要比平衡樹略差，但總體的平均複雜度也能達到 O(logn)。下面是跳躍表在各個操作上與不同實現的平衡樹的比較：
雖然檢索效率比平衡樹略差，但跳躍表具有以下優點：
-
插入、刪除要比平衡樹塊
-
實現簡單
-
更節省空間
-
更容易拓展
以自平衡樹紅黑樹爲例，除了需要倆個子節點指針外還需要記錄顏色，而跳躍表可以通過調整概率因子 p 使額外空間的使用小於紅黑樹。Redis 中的跳躍表實現就是做了拓展以支持雙向檢索等目的，類似的需求在紅黑樹中就不太好實現了。
下面使用 Go 完成一個簡單的實現。
接口設計
下面是我這個跳躍表要有的特性和接口：
-
鍵類型定義爲
float64，值支持任意類型 -
檢索（Search）：存在返回包含鍵值的元素和 true，不存在返回 nil 和 false
-
插入（Insert)
-
刪除（Delete）
-
獲取長度（Len）
-
迭代（Front，Next)
將這些寫成 ExampleTest：
package skiplist_test
import (
"fmt"
"github.com/protream/go-datastructures/skiplist"
)
func ExampleSkipList() {
sl := skiplist.New()
sl.Insert(float64(100), "foo")
e, ok := sl.Search(float64(100))
fmt.Println(ok)
fmt.Println(e.Value)
e, ok = sl.Search(float64(200))
fmt.Println(ok)
fmt.Println(e)
sl.Insert(float64(20.5), "bar")
sl.Insert(float64(50), "spam")
sl.Insert(float64(20), 42)
fmt.Println(sl.Len())
e = sl.Delete(float64(50))
fmt.Println(e.Value)
fmt.Println(sl.Len())
for e := sl.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
// Output:
// true
// foo
// false
// <nil>
// 4
// spam
// 3
// 42
// bar
// foo
}定義
首先定義倆個常量，maxLevel 表示元素最多可以有多少個向前的指針，它決定了跳躍表的容量。p 是一個概率因子，它決定了隨機生成 level 的大小分佈。
const (
maxLevel int = 16 // Should be enough for 2^16 elements
p float32 = 0.25
)p 的取值對檢索時間和節點向前指針個數影響如圖：
現在定義一下跳躍表的節點。Score 存放可排序鍵，Value 存放鍵對應的值，forward 存放向前的指針列表，forward 的長度是插入元素隨機生成的長度。
// Element is an Element of a skiplist.
type Element struct {
Score float64
Value interface{}
forward []*Element
}
func newElement(score float64, value interface{}, level int) *Element {
return &Element{
Score: score,
Value: value,
forward: make([]*Element, level),
}
}再來定義跳躍表。header 是一個啞節點，作用和單鏈表的啞節點一樣，方便操作，len 記錄當前元素個數，level 記錄當前所有元素最大 level。
// SkipList represents a skiplist.
// The zero value from SkipList is an empty skiplist ready to use.
type SkipList struct {
header *Element // header is a dummy element
len int // current skiplist length，header not included
level int // current skiplist level，header not included
}
// New returns a new empty SkipList.
func New() *SkipList {
return &SkipList{
header: &Element{forward: make([]*Element, maxLevel)},
}
}需要一個生成隨機 level 的函數：
func randomLevel() int {
level := 1
for rand.Float32() < p && level < maxLevel {
level++
}
return level
}迭代
要支持這樣的迭代訪問需要實現 Front 和 Next 方法。
for e := sl.Front(); e != nil; e = e.Next() {
...
}如過只看 forward 的 0 層，相當於是在迭代一個單鏈表，很好寫：
// Front returns first element in the skiplist which maybe nil.
func (sl *SkipList) Front() *Element {
return sl.header.forward[0]
}
// Next returns first element after e.
func (e *Element) Next() *Element {
if e != nil {
return e.forward[0]
}
return nil
}檢索
檢索是從跳躍表當前最大 level 由高到低進行的。以檢索 17 的過程爲例：
-
從當前最高層也就是第 4 層開始，找到這一層最後一個小於 17 的元素，這裏是 6
-
來到 6 所在元素，層數減 1，找到這一層最後一個小於 17 的元素，這裏是還是 6
-
層數減 1，重複上面的過程，找到第 0 層最後一個小於 17 的元素
到這裏顯而易見，如果第 0 層最後一個小於 17 的元素的下一個元素就是我們要找的元素，當然，如果這個元素爲 nil 或者 score 和要找的不相等，就說明要找的 score 不存在。
// Search the skiplist to findout element with the given score.
// Returns (*Element, true) if the given score present, otherwise returns (nil, false).
func (sl *SkipList) Search(score float64) (element *Element, ok bool) {
x := sl.header
for i := sl.level - 1; i >= 0; i-- {
for x.forward[i] != nil && x.forward[i].Score < score {
x = x.forward[i]
}
}
x = x.forward[0]
if x != nil && x.Score == score {
return x, true
}
return nil, false
}插入
下面是插入 17 到跳躍表：
插入首先要定位插入的點，這個過程和檢索基本一樣，不同的是，要記錄每個 level 最後一個小於 17 元素，因爲插入點必然在這些元素後，它們 forward 需要更新，這裏記錄的地方就是 update，後面更新 update 裏和待插入元素的指針就行了。這裏的實現是不允許重複 score 的，如果 score 已經存在則替換爲新的 value 值。
// Insert (score, value) pair to the skiplist and returns pointer of element.
func (sl *SkipList) Insert(score float64, value interface{}) *Element {
update := make([]*Element, maxLevel)
x := sl.header
for i := sl.level - 1; i >= 0; i-- {
for x.forward[i] != nil && x.forward[i].Score < score {
x = x.forward[i]
}
update[i] = x
}
x = x.forward[0]
// Score already presents, replace with new value then return
if x != nil && x.Score == score {
x.Value = value
return x
}
level := randomLevel()
if level > sl.level {
level = sl.level + 1
update[sl.level] = sl.header
sl.level = level
}
e := newElement(score, value, level)
for i := 0; i < level; i++ {
e.forward[i] = update[i].forward[i]
update[i].forward[i] = e
}
sl.len++
return e
}刪除
刪除和插入非常相似並且還要簡單一點。
// Delete remove and return element with given score, return nil if element not present
func (sl *SkipList) Delete(score float64) *Element {
update := make([]*Element, maxLevel)
x := sl.header
for i := sl.level - 1; i >= 0; i-- {
for x.forward[i] != nil && x.forward[i].Score < score {
x = x.forward[i]
}
update[i] = x
}
x = x.forward[0]
if x != nil && x.Score == score {
for i := 0; i < sl.level; i++ {
if update[i].forward[i] != x {
return nil
}
update[i].forward[i] = x.forward[i]
}
sl.len--
}
return x
}總結
本文簡單介紹了跳躍表並給出一個 Go 的實現。這個實現比較簡單，也沒有考慮併發安全，需要的話可以通過 sync.RWLock 來做。更詳細的介紹建議直接看 skiplist 的原論文：Skip Lists：A Probabilistic Alternative to Balanced Trees(https://protream.com/2019/skiplist-and-its-go-implementation/)。
轉自：
zhuanlan.zhihu.com/p/72553601
本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/BaDpagOecG7TtLoELhdtOw