跳躍表（Skip Links）實作（Golang版）

1. 介紹

跳躍表（Skip Lists）是一種隨機化的資料，由 William Pugh 在論文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳躍表以有序的方式在層次化的鏈表中保存元素，效率和平衡樹媲美 —— 查找、洗掉、添加等操作都可以在對數期望時間下完成，并且比起平衡樹來說，跳躍表的實作要簡單直觀得多，

本文注重跳躍表的實作，關于跳躍表的原理介紹，網上有很多優質的介紹檔案，這里就不再介紹跳躍表的實作原理了，

2. 跳躍表在Redis中的應用

Redis的有序集合（sorted set）是基于跳躍表實作的，相比 William Pugh 論文中描述的跳躍表，Redis做了一些修改，其中包括：

允許重復的 score 值：多個不同的 member 的 score 值可以相同，
進行對比操作時，不僅要檢查 score 值，還要檢查 member ：當 score 值可以重復時，單靠 score 值無法判斷一個元素的身份，所以需要連 member 域都一并檢查才行，
每個節點都帶有一個高度為 1 層的后退指標，用于從表尾方向向表頭方向迭代：當執行ZREVRANGE或ZREVRANGEBYSCORE這類以逆序處理有序集的命令時，就會用到這個屬性，

以下展示了Redis有序集合（sorted set）的一個可能結構：

注意：圖中前向指標上面括號中的數字，表示對應的span的值，即當前指標跨越了多少個節點，這個計數不包括指標的起點節點，但包括指標的終點節點，
圖取于此：http://zhangtielei.com/posts/blog-redis-skiplist.html

3. 跳躍表實作（Golang版）

3.1 實作介紹

參考Redis有序集合（sorted set）設計原理與實作原始碼，
只實作三個基礎介面：Search（查詢）、Add（添加）、Erase（洗掉）
支持設定最大層級數（Determining MaxLevel）和上升索引概率（Probabilistic Philosophy），
提供一個Println介面，用于除錯測驗，

3.2 實作原始碼

package skiplinks

import (
	"fmt"
	"math/rand"
	"strings"
	"time"
)

const (
	defaultSkipLinkedP = 0.5
	defaultMaxLevel    = 64
)

type SkipLinks struct {
	// key和score的映射表
	scoreMap map[string]float64
	// 當前層級數
	curLevel uint16
	// 最大層級數
	maxLevel uint16
	// 最小值
	minScore float64
	// 上升索引概率
	skipLinkedP float64
	// 頭節點
	head *Node
	// 隨機引數
	rand *rand.Rand
}

func NewSkipLinked(maxLevel uint16, minScore float64, p ...float64) *SkipLinks {
	skipLinkedP := defaultSkipLinkedP
	if len(p) > 0 && float64(0) <= p[0] && p[0] < float64(1) {
		skipLinkedP = p[0]
	}
	if maxLevel <= 0 || maxLevel > maxLevel {
		maxLevel = defaultMaxLevel
	}
	return &SkipLinks{
		scoreMap:    make(map[string]float64),
		curLevel:    1,
		maxLevel:    maxLevel,
		minScore:    minScore,
		skipLinkedP: skipLinkedP,
		head:        NewNode("", minScore, nil, maxLevel),
		rand:        rand.New(rand.NewSource(time.Now().UnixNano())),
	}
}

func (l *SkipLinks) getLevel() uint16 {
	level := uint16(1)
	for l.rand.Float64() < l.skipLinkedP && level < l.maxLevel {
		level++
	}
	return level
}

func (l *SkipLinks) compare(score1, score2 float64, key1, key2 string) int {
	if score1 > score2 {
		return 1
	} else if score1 < score2 {
		return -1
	} else {
		return strings.Compare(key1, key2)
	}
}

func (l *SkipLinks) Search(key string) (bool, interface{}) {
	score, exist := l.scoreMap[key]
	if !exist {
		return false, nil
	}
	exist, node := l.search(key, score, l.head, l.curLevel)
	if !exist {
		return false, nil
	}
	return true, node.Val
}

func (l *SkipLinks) search(key string, score float64, node *Node, level uint16) (bool, *Node) {
	next := node.Next[level-1]
	for next != nil && l.compare(next.Score, score, next.Key, key) <= 0 {
		node = node.Next[level-1]
		next = node.Next[level-1]
	}
	if l.compare(node.Score, score, node.Key, key) == 0 {
		return true, node
	}
	if level == 1 {
		return false, node
	}
	return l.search(key, score, node, level-1)
}

func (l *SkipLinks) Add(key string, score float64, val interface{}) error {
	if score < l.minScore {
		return NewScoreOutOfRangeError(key, score, l.minScore)
	}
	if key == "" {
		return NewInvalidKeyError(key, "empty key")
	}
	_, exist := l.scoreMap[key]
	if exist {
		l.Erase(key)
	}
	high, newNode := l.add(key, score, val, l.head, l.curLevel)
	if high > l.curLevel {
		// Add之后，層數可能加一
		l.head.Next[l.curLevel] = newNode
		l.curLevel++
	}
	l.scoreMap[key] = score
	return nil
}

func (l *SkipLinks) add(key string, score float64, val interface{}, node *Node, level uint16) (uint16, *Node) {
	next := node.Next[level-1]
	for next != nil && l.compare(next.Score, score, next.Key, key) <= 0 {
		node = node.Next[level-1]
		next = node.Next[level-1]
	}
	if level == 1 {
		newNode := NewNode(key, score, val, l.maxLevel)
		newNode.Next[level-1] = next
		node.Next[level-1] = newNode
		return l.getLevel(), newNode
	}
	high, newNode := l.add(key, score, val, node, level-1)
	if high >= level {
		newNode.Next[level-1] = next
		node.Next[level-1] = newNode
	}
	return high, newNode
}

func (l *SkipLinks) Erase(key string) (bool, interface{}) {
	score, exist := l.scoreMap[key]
	if !exist {
		return false, nil
	}
	delete(l.scoreMap, key)
	exist, node := l.erase(key, score, l.head, l.curLevel)
	if !exist {
		return false, nil
	}
	for i := int(l.curLevel - 1); i > 0; i-- {
		if l.head.Next[i] == nil {
			// Erase之后，層數可能減少
			l.curLevel--
		} else {
			break
		}
	}
	return true, node.Val
}

func (l *SkipLinks) erase(key string, score float64, node *Node, level uint16) (bool, *Node) {
	next := node.Next[level-1]
	for next != nil && l.compare(next.Score, score, next.Key, key) < 0 {
		node = next
		next = next.Next[level-1]
	}
	if level == 1 {
		if next != nil && l.compare(next.Score, score, next.Key, key) == 0 {
			node.Next[level-1] = next.Next[level-1]
			next.Next[level-1] = nil
			return true, next
		} else {
			return false, nil
		}
	}
	exist, rmNode := l.erase(key, score, node, level-1)
	if exist && next != nil && l.compare(next.Score, score, next.Key, key) == 0 {
		node.Next[level-1] = next.Next[level-1]
		next.Next[level-1] = nil
	}
	return exist, rmNode
}

func (l *SkipLinks) Println() {
	for i := int(l.curLevel - 1); i >= 0; i-- {
		var (
			content string = fmt.Sprintf("level%d", i)
			node    *Node  = l.head.Next[i]
		)
		for node != nil {
			content += fmt.Sprintf(" %s(%v)", node.Key, node.Score)
			node = node.Next[i]
		}
		fmt.Println(content)
	}
}

type Node struct {
	Key   string
	Score float64
	Val   interface{}
	Next  []*Node
}

func NewNode(key string, score float64, val interface{}, maxLevel uint16) *Node {
	return &Node{
		Key:   key,
		Score: score,
		Val:   val,
		Next:  make([]*Node, maxLevel, maxLevel),
	}
}

type ScoreOutOfRangeError struct {
	key   string
	score float64
	min   float64
}

func NewScoreOutOfRangeError(key string, score float64, min float64) *ScoreOutOfRangeError {
	return &ScoreOutOfRangeError{
		key:   key,
		score: score,
		min:   min,
	}
}

func (e *ScoreOutOfRangeError) Error() string {
	return fmt.Sprintf("score out of range, min(include)=%v, score=%v, key=%s", e.min, e.score, e.key)
}

type InvalidKeyError struct {
	key    string
	reason string
}

func NewInvalidKeyError(key, reason string) *InvalidKeyError {
	return &InvalidKeyError{
		key:    key,
		reason: reason,
	}
}

func (e *InvalidKeyError) Error() string {
	return fmt.Sprintf("invalid key: %s, reason: %s", e.key, e.reason)
}

附錄

參考檔案

論文：《Skip lists: a probabilistic alternative to balanced trees》
Redis有序集合原始碼：Redis ZSET原始碼
Redis內部資料結構詳解：Redis內部資料結構詳解(6)——skiplist

轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/240580.html

標籤：區塊鏈

上一篇：關于Tron波場的FullNode節點操作,地址互轉,代理資源,離線簽名,錯誤資訊決議等等

下一篇：區塊鏈通識問題（一）