GO實(shí)現(xiàn)跳躍表的示例詳解
更新時(shí)間：2022年12月19日 11:22:04 作者：Onemorelight95
跳表全稱叫做跳躍表，簡稱跳表，是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，實(shí)質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。本文將利用GO語言編寫一個(gè)跳表，需要的可以參考一下
跳躍表介紹
跳躍表（skiplist）是一種有序的數(shù)據(jù)結(jié)構(gòu)，它通過建立多層"索引"，從而達(dá)到快速訪問節(jié)點(diǎn)的目的. 跳躍表支持平均O(logN)、最壞O(N)復(fù)雜度的節(jié)點(diǎn)查找，還可以通過順序性操作來批量處理節(jié)點(diǎn)。
下面是一個(gè)跳表結(jié)構(gòu)的示意圖，其實(shí)跳表就是一個(gè)二維鏈表，只有最底層的鏈表中存著數(shù)據(jù)，其他層都是在第一層基礎(chǔ)上建立的索引，越靠近上層，節(jié)點(diǎn)之間的跨度就越大，跳表的查詢范圍也越大。依靠著這些索引，跳表可以實(shí)現(xiàn)接近二分查找的查找效率。
跳躍表的實(shí)現(xiàn)
跳躍表的結(jié)構(gòu)
跳表的元素
// Element 是一個(gè)key-score對(duì)組
type Element struct {
Member string
// 跳躍表節(jié)點(diǎn)依照Score升序排序，若一樣，則按照Member的字典升序排序
Score float64
}
跳表的層結(jié)構(gòu)
// Level 層
type Level struct {
// 指向前面一個(gè)節(jié)點(diǎn)
forward *node
// 與前一個(gè)節(jié)點(diǎn)的跨度
span int64
}
跳表的節(jié)點(diǎn)
跳表的一個(gè)節(jié)點(diǎn)有三個(gè)字段：元素、指向前一個(gè)節(jié)點(diǎn)的指針和建立在該節(jié)點(diǎn)之上的層級(jí)。
// node 跳躍表的一個(gè)節(jié)點(diǎn)
type node struct {
Element
// 回退指針
backward *node
// 每個(gè)節(jié)點(diǎn)有 1~maxLevel 個(gè)層級(jí)
level []*Level
}
跳表的表頭結(jié)構(gòu)
// skiplist 跳表結(jié)構(gòu)
type skiplist struct {
// 指向表頭節(jié)點(diǎn)
header *node
// 指向表尾節(jié)點(diǎn)
tail *node
// 跳躍表的長度（除了第一個(gè)節(jié)點(diǎn)）
length int64
// 跳躍表的最大層級(jí)（除了第一個(gè)節(jié)點(diǎn)）
level int16
}
創(chuàng)建跳躍表
// makeNode 創(chuàng)建一個(gè)跳躍表節(jié)點(diǎn)
func makeNode(level int16, score float64, member string) *node {
n := &node{
Element: Element{
Score: score,
Member: member,
},
level: make([]*Level, level),
}
for i := range n.level {
n.level[i] = new(Level)
}
return n
}
// makeSkiplist 創(chuàng)建一個(gè)跳躍表結(jié)構(gòu)
func makeSkiplist() *skiplist {
return &skiplist{
level: 1,
header: makeNode(maxLevel, 0, ""),
}
}
跳躍表的插入和刪除
在插入跳躍表之前，我們要明確的是新插入的這個(gè)節(jié)點(diǎn)，我們應(yīng)該在它之上建立多少層索引呢？我們將通過一個(gè)隨機(jī)算法來計(jì)算得到一個(gè)隨機(jī)值，叫做冪次定律。
冪次定律的含義是：如果某件事的發(fā)生頻率和它的某個(gè)屬性成冪關(guān)系，那么這個(gè)頻率就可以稱之為符合冪次定律。映射到我們的需求就是一個(gè)新插入的節(jié)點(diǎn)，生成小數(shù)值層數(shù)的概率很大，而生成大數(shù)值層數(shù)的概率很小。
const (
maxLevel = 16
)
// randomLevel 隨機(jī)生成一個(gè)新跳躍表節(jié)點(diǎn)的層數(shù)（1~16）
// 滿足冪次定律
func randomLevel() int16 {
level := int16(1)
for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
level++
}
if level < maxLevel {
return level
}
return maxLevel
}
上述函數(shù)計(jì)算出來的層數(shù)將呈現(xiàn)以下概率：
p = 0.25（1/4）
層數(shù)恰好為1的概率（不執(zhí)行while）為1 - p（3/4）.
層數(shù)恰好為2的概率（執(zhí)行 1 次while）為p * (1 - p)（3/16）.
層數(shù)恰好為3的概率（執(zhí)行 2 次while）為p ^ 2 * (1 - p)（3/64）.
層數(shù)恰好為4的概率（執(zhí)行 3 次while）為p ^ 3 * (1 - p)（3/256）.
層數(shù)恰好為k（k <= 32）的概率（執(zhí)行 k - 1 次while）為p ^ (k - 1) * (1 - p).
可以發(fā)現(xiàn)生成越高層數(shù)的概率會(huì)越來越小，而且和上一次呈冪關(guān)系遞減.
插入操作
插入操作的步驟：
- 首先準(zhǔn)備兩個(gè)切片：update（用于保存在每一層，待插入節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)）、rank（用于累加每一層的跨度，方便后續(xù)待插入節(jié)點(diǎn)索引中span字段的計(jì)算）。
- 從上至下遍歷每一層索引，在每一層中尋找待插入節(jié)點(diǎn)的位置（如果分?jǐn)?shù)比當(dāng)前節(jié)點(diǎn)小，就往后遍歷，比當(dāng)前節(jié)點(diǎn)大就下沉），將待插入節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)存到update切片中，然后將待插入節(jié)點(diǎn)相對(duì)起始點(diǎn)的便宜量粗存到rank切片中。
- 找到待插入節(jié)點(diǎn)的位置之后，先使用
randomLevel函數(shù)獲取該節(jié)點(diǎn)應(yīng)該建立索引的層數(shù)。 - 接著構(gòu)造節(jié)點(diǎn)，然后插入到應(yīng)該插入的位置，首先需要更新每一層索引的狀態(tài)，新插入節(jié)點(diǎn)的forward指針就指向前一個(gè)節(jié)點(diǎn)的forward指針指向的位置（前一個(gè)節(jié)點(diǎn)保存在update切片中），新插入節(jié)點(diǎn)的索引span字段就是它與前一個(gè)節(jié)點(diǎn)同層索引的跨度之差（通過rank切片計(jì)算得到）。接著因?yàn)樾虏迦牍?jié)點(diǎn)增加了前面節(jié)點(diǎn)的跨度，所以需要更新前面一個(gè)節(jié)點(diǎn)每一層的跨度。
- 最后設(shè)置新插入節(jié)點(diǎn)的backward指針指向，直接指向前一個(gè)節(jié)點(diǎn)即可（通過update切片來實(shí)現(xiàn)）。
// insert 插入元素
func (skiplist *skiplist) insert(member string, score float64) *node {
// 保存在每一層，待插入節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
update := make([]*node, maxLevel)
// 用于累加跨度
rank := make([]int64, maxLevel)
// 找到待插入的位置
node := skiplist.header
for i := skiplist.level - 1; i >= 0; i-- {
if i == skiplist.level-1 {
rank[i] = 0
} else {
// 累加跨度
rank[i] = rank[i+1]
}
if node.level[i] != nil {
// 在第i層找待插入的位置
for node.level[i].forward != nil &&
(node.level[i].forward.Score < score ||
(node.level[i].forward.Score == score && node.level[i].forward.Member < member)) { // same score, different key
// 累加與前一個(gè)節(jié)點(diǎn)的跨度
rank[i] += node.level[i].span
// 前進(jìn)
node = node.level[i].forward
}
}
update[i] = node
}
// 獲得隨機(jī)層數(shù)
level := randomLevel()
// 如果新插入的節(jié)點(diǎn)抽到的層級(jí)最大
if level > skiplist.level {
// 初始化每一層的狀態(tài)
for i := skiplist.level; i < level; i++ {
rank[i] = 0
update[i] = skiplist.header
update[i].level[i].span = skiplist.length
}
skiplist.level = level
}
// 構(gòu)造新節(jié)點(diǎn)并插入到跳表
node = makeNode(level, score, member)
for i := int16(0); i < level; i++ {
node.level[i].forward = update[i].level[i].forward
update[i].level[i].forward = node
node.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
update[i].level[i].span = (rank[0] - rank[i]) + 1
}
// 新插入的節(jié)點(diǎn)增加了前面節(jié)點(diǎn)的跨度
for i := level; i < skiplist.level; i++ {
update[i].level[i].span++
}
// 設(shè)置回退節(jié)點(diǎn)
if update[0] == skiplist.header {
node.backward = nil
} else {
node.backward = update[0]
}
// 設(shè)置node前面一個(gè)節(jié)點(diǎn)的回退節(jié)點(diǎn)
if node.level[0].forward != nil {
node.level[0].forward.backward = node
}
skiplist.length++
return node
}刪除操作
刪除操作首先要找到待刪除節(jié)點(diǎn)的位置，找節(jié)點(diǎn)的步驟與插入節(jié)點(diǎn)的操作類似的，首先創(chuàng)建一個(gè)切片：update（用于保存在每一層，待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)）。然后在每一層中進(jìn)行查找，分?jǐn)?shù)比當(dāng)前節(jié)點(diǎn)小，就往后遍歷，比當(dāng)前節(jié)點(diǎn)大就下沉，同時(shí)用update切片記錄每一層中待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。找到該節(jié)點(diǎn)之后，就可以進(jìn)行刪除操作了。
先更新每一層索引的狀態(tài)：更新待刪除節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)的跨度以及forward指針的指向。
然后更新后面一個(gè)節(jié)點(diǎn)的回退指針，最后更新跳表中的最大層級(jí)即可。
// 尋找待刪除的節(jié)點(diǎn)
func (skiplist *skiplist) remove(member string, score float64) bool {
// 儲(chǔ)存待刪除節(jié)點(diǎn)每一層的上一個(gè)節(jié)點(diǎn)
update := make([]*node, maxLevel)
node := skiplist.header
// 尋找待刪除節(jié)點(diǎn)
for i := skiplist.level - 1; i >= 0; i-- {
for node.level[i].forward != nil &&
(node.level[i].forward.Score < score ||
(node.level[i].forward.Score == score &&
node.level[i].forward.Member < member)) {
node = node.level[i].forward
}
update[i] = node
}
// node在循環(huán)中，一直是待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
// 在最底層的索引處向后移動(dòng)一位，剛好就是待刪除節(jié)點(diǎn)
node = node.level[0].forward
// 找到該節(jié)點(diǎn)
if node != nil && score == node.Score && node.Member == member {
skiplist.removeNode(node, update)
return true
}
return false
}
// 刪除找到的節(jié)點(diǎn)
func (skiplist *skiplist) removeNode(node *node, update []*node) {
// 更新每一層的狀態(tài)
for i := int16(0); i < skiplist.level; i++ {
if update[i].level[i].forward == node {
update[i].level[i].span += node.level[i].span - 1
update[i].level[i].forward = node.level[i].forward
} else {
update[i].level[i].span--
}
}
// 更新后面一個(gè)節(jié)點(diǎn)的回退指針
if node.level[0].forward != nil {
node.level[0].forward.backward = node.backward
} else {
skiplist.tail = node.backward
}
// 更新跳表中的最大層級(jí)
for skiplist.level > 1 && skiplist.header.level[skiplist.level-1].forward == nil {
skiplist.level--
}
skiplist.length--
}跳躍表的排名操作
獲取元素的排名
獲取元素的排名操作比較簡單，首先定義一個(gè)rank整型變量，用于在遍歷的時(shí)候累加跨度。
接著逐層進(jìn)行查找，在某一層進(jìn)行查找時(shí)，每往前遍歷一個(gè)元素，就使用rank變量累加上它們索引之間的跨度，當(dāng)遍歷到第0層時(shí)，就找到了這個(gè)節(jié)點(diǎn)，rank變量就是當(dāng)前節(jié)點(diǎn)在整個(gè)跳躍表中的排名。
func (skiplist *skiplist) getRank(member string, score float64) int64 {
var rank int64 = 0
x := skiplist.header
for i := skiplist.level - 1; i >= 0; i-- {
for x.level[i].forward != nil &&
(x.level[i].forward.Score < score ||
(x.level[i].forward.Score == score &&
x.level[i].forward.Member <= member)) {
rank += x.level[i].span
x = x.level[i].forward
}
if x.Member == member {
return rank
}
}
return 0
}
通過排名獲取元素
首先定義一個(gè)變量i用于累加每一層索引的跨度，接著在每一層索引中進(jìn)行遍歷，如果i累加上當(dāng)前節(jié)點(diǎn)層與下一個(gè)節(jié)點(diǎn)層的跨度值小于rank，就繼續(xù)往后遍歷，否則就下沉。當(dāng)i等于rank時(shí)，就找到了該節(jié)點(diǎn)。
func (skiplist *skiplist) getByRank(rank int64) *node {
// 記錄從頭節(jié)點(diǎn)開始的跨度
var i int64 = 0
// 用于遍歷節(jié)點(diǎn)的指針
n := skiplist.header
// 從最高層級(jí)開始遍歷
for level := skiplist.level - 1; level >= 0; level-- {
for n.level[level].forward != nil && (i+n.level[level].span) <= rank {
i += n.level[level].span
n = n.level[level].forward
}
if i == rank {
return n
}
}
return nil
}跳躍表的區(qū)間操作
我們創(chuàng)建了一個(gè)ScoreBorder結(jié)構(gòu)體用于封裝跳表的分?jǐn)?shù)，提供了比較大小以及創(chuàng)建ScoreBorder等API。
const (
// 負(fù)無窮
negativeInf int8 = -1
// 正無窮
positiveInf int8 = 1
)
type ScoreBorder struct {
// 標(biāo)記當(dāng)前分?jǐn)?shù)是否為無窮
Inf int8
// 分?jǐn)?shù)值
Value float64
// 標(biāo)記兩個(gè)分?jǐn)?shù)相等時(shí)，是否返回true
Exclude bool
}
func (border *ScoreBorder) greater(value float64) bool {
if border.Inf == negativeInf {
return false
} else if border.Inf == positiveInf {
return true
}
if border.Exclude {
return border.Value > value
}
return border.Value >= value
}
func (border *ScoreBorder) less(value float64) bool {
if border.Inf == negativeInf {
return true
} else if border.Inf == positiveInf {
return false
}
if border.Exclude {
return border.Value < value
}
return border.Value <= value
}
var positiveInfBorder = &ScoreBorder{
Inf: positiveInf,
}
var negativeInfBorder = &ScoreBorder{
Inf: negativeInf,
}
// ParseScoreBorder 根據(jù)參數(shù)構(gòu)造并返回ScoreBorder
func ParseScoreBorder(s string) (*ScoreBorder, error) {
if s == "inf" || s == "+inf" {
return positiveInfBorder, nil
}
if s == "-inf" {
return negativeInfBorder, nil
}
if s[0] == '(' {
value, err := strconv.ParseFloat(s[1:], 64)
if err != nil {
return nil, errors.New("ERR min or max is not a float")
}
return &ScoreBorder{
Inf: 0,
Value: value,
Exclude: true,
}, nil
}
value, err := strconv.ParseFloat(s, 64)
if err != nil {
return nil, errors.New("ERR min or max is not a float")
}
return &ScoreBorder{
Inf: 0,
Value: value,
Exclude: false,
}, nil
}判斷[min, max]區(qū)間與是否在skiplist的分?jǐn)?shù)區(qū)間內(nèi)（是否有重合）
判斷有三個(gè)指標(biāo)：
- 判斷[min, max]區(qū)間本身是否有效。
- 判斷min是否大于跳表的最大分?jǐn)?shù)值（與表尾元素的分?jǐn)?shù)作比較）。
- 判斷max是否小于跳表的最小分?jǐn)?shù)值（與表頭元素的分?jǐn)?shù)作比較）。
func (skiplist *skiplist) hasInRange(min *ScoreBorder, max *ScoreBorder) bool {
// [min, max]無意義或?yàn)榭?
if min.Value > max.Value || (min.Value == max.Value && (min.Exclude || max.Exclude)) {
return false
}
// [min, max] > skiplist.tail.Score
n := skiplist.tail
if n == nil || !min.less(n.Score) {
return false
}
// [min, max] < skiplist.head.Score
n = skiplist.header.level[0].forward
if n == nil || !max.greater(n.Score) {
return false
}
return true
}
從跳表中找到處于[min, max]區(qū)間的最小值
實(shí)現(xiàn)思路比較簡單，我們找到跳表中分?jǐn)?shù)第一個(gè)大于min的節(jié)點(diǎn)即可。找到之后我們還需要將該節(jié)點(diǎn)的分?jǐn)?shù)與max作比較，如果大于max，則不存在。
func (skiplist *skiplist) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *node {
if !skiplist.hasInRange(min, max) {
return nil
}
n := skiplist.header
// 找到第一個(gè)大于等于min的節(jié)點(diǎn)
for level := skiplist.level - 1; level >= 0; level-- {
for n.level[level].forward != nil && !min.less(n.level[level].forward.Score) {
n = n.level[level].forward
}
}
n = n.level[0].forward
// n節(jié)點(diǎn)的分?jǐn)?shù)在[min, max]區(qū)間之外
if !max.greater(n.Score) {
return nil
}
return n
}刪除跳表中分?jǐn)?shù)值處在[min, max]區(qū)間內(nèi)的元素，并返回它們的切片
首先遍歷跳表，然后找到分?jǐn)?shù)值大于min的第一個(gè)節(jié)點(diǎn)，從這個(gè)節(jié)點(diǎn)開始刪除，刪除一個(gè)就繼續(xù)往后遍歷，刪除的過程中還得判斷，待刪除的節(jié)點(diǎn)分?jǐn)?shù)是否超出了[min, max]區(qū)間。
func (skiplist *skiplist) RemoveRangeByScore(min *ScoreBorder, max *ScoreBorder) (removed []*Element) {
// 儲(chǔ)存待刪除節(jié)點(diǎn)每一層的前驅(qū)節(jié)點(diǎn)
update := make([]*node, maxLevel)
removed = make([]*Element, 0)
// 找到待刪除節(jié)點(diǎn)每一層的前驅(qū)節(jié)點(diǎn)
node := skiplist.header
for i := skiplist.level - 1; i >= 0; i-- {
for node.level[i].forward != nil {
if min.less(node.level[i].forward.Score) {
break
}
node = node.level[i].forward
}
update[i] = node
}
node = node.level[0].forward
// 開始刪除節(jié)點(diǎn)
for node != nil {
// 保證不超出[min, max]區(qū)間
if !max.greater(node.Score) {
break
}
next := node.level[0].forward
removedElement := node.Element
removed = append(removed, &removedElement)
skiplist.removeNode(node, update)
node = next
}
return removed
}
刪除排名在[start, stop]區(qū)間內(nèi)的元素，并返回它們的切片
首先定義一個(gè)i變量，作為刪除節(jié)點(diǎn)的迭代器，接著找到排名為start的節(jié)點(diǎn)，然后從這個(gè)節(jié)點(diǎn)往后刪除即可。
func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64) (removed []*Element) {
// 排名迭代器
var i int64 = 0
update := make([]*node, maxLevel)
removed = make([]*Element, 0)
// 找到待刪除的第一個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，并儲(chǔ)存在update切片中
node := skiplist.header
for level := skiplist.level - 1; level >= 0; level-- {
for node.level[level].forward != nil && (i+node.level[level].span) < start {
i += node.level[level].span
node = node.level[level].forward
}
update[level] = node
}
i++
// 處在區(qū)間的第一個(gè)節(jié)點(diǎn)
node = node.level[0].forward
// 開始刪除節(jié)點(diǎn)
for node != nil && i < stop {
next := node.level[0].forward
removedElement := node.Element
removed = append(removed, &removedElement)
skiplist.removeNode(node, update)
node = next
i++
}
return removed
}完整實(shí)現(xiàn)
https://github.com/omlight95/GoRedis/blob/master/datastruct/sortedset/skiplist.go
到此這篇關(guān)于GO實(shí)現(xiàn)跳躍表的示例詳解的文章就介紹到這了,更多相關(guān)GO跳躍表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關(guān)文章
Go語言以其高效的編譯能力和簡潔的語法,能夠輕松打包生成Windows系統(tǒng)下的.exe可執(zhí)行文件,用戶只需安裝Go編譯器、編寫Go源代碼并使用gobuild命令指定輸出文件名即可完成編譯,感興趣的可以了解一下2024-10-10
本文主要介紹了go的切片擴(kuò)容機(jī)制詳解，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
我們知道,Go語言從設(shè)計(jì)伊始,就不支持經(jīng)典的面向?qū)ο笳Z法元素,但?Go?語言仍保留了名為“方法（method）”的語法元素,下面我們就來帶大家深入了解一下Go語言中的方法吧2023-11-11
變量、常量的聲明與使用是掌握一門編程語言的基礎(chǔ)，在這篇文章中，小編就來帶大家學(xué)習(xí)一下Go語言是怎么樣聲明和使用變量與常量吧2023-03-03
在Go語言中,chan（通道）是一種用于在不同的goroutine之間進(jìn)行通信的機(jī)制,通道可以是無緩沖的（同步的）或有緩沖的（異步的）,本文給大家詳細(xì)介紹了Golang中Channel的高級(jí)用法,需要的朋友可以參考下2024-05-05
Go?gRPC進(jìn)階教程服務(wù)超時(shí)設(shè)置
這篇文章主要為大家介紹了Go?gRPC進(jìn)階，gRPC請求的超時(shí)時(shí)間設(shè)置，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-06-06
今天小編就為大家分享一篇關(guān)于golang讀取文件的常用方法總結(jié)，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2019-04-04
本文主要介紹了GO語言中接口和接口型函數(shù)的使用，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03
這篇文章介紹了go語言中的函數(shù)與方法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
這篇文章主要為大家詳細(xì)介紹一下Golang深拷貝和淺拷貝，文中有詳細(xì)的代碼示例供大家參考，需要的可以參考一下2023-05-05