GO實現跳躍表的示例詳解
更新時間：2022年12月19日 11:22:04 作者：Onemorelight95
跳表全稱叫做跳躍表，簡稱跳表，是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。本文將利用GO語言編寫一個跳表，需要的可以參考一下
跳躍表介紹
跳躍表（skiplist）是一種有序的數據結構，它通過建立多層"索引"，從而達到快速訪問節(jié)點的目的. 跳躍表支持平均O(logN)、最壞O(N)復雜度的節(jié)點查找，還可以通過順序性操作來批量處理節(jié)點。
下面是一個跳表結構的示意圖，其實跳表就是一個二維鏈表，只有最底層的鏈表中存著數據，其他層都是在第一層基礎上建立的索引，越靠近上層，節(jié)點之間的跨度就越大，跳表的查詢范圍也越大。依靠著這些索引，跳表可以實現接近二分查找的查找效率。
跳躍表的實現
跳躍表的結構
跳表的元素
// Element 是一個key-score對組
type Element struct {
Member string
// 跳躍表節(jié)點依照Score升序排序，若一樣，則按照Member的字典升序排序
Score float64
}
跳表的層結構
// Level 層
type Level struct {
// 指向前面一個節(jié)點
forward *node
// 與前一個節(jié)點的跨度
span int64
}
跳表的節(jié)點
跳表的一個節(jié)點有三個字段：元素、指向前一個節(jié)點的指針和建立在該節(jié)點之上的層級。
// node 跳躍表的一個節(jié)點
type node struct {
Element
// 回退指針
backward *node
// 每個節(jié)點有 1~maxLevel 個層級
level []*Level
}
跳表的表頭結構
// skiplist 跳表結構
type skiplist struct {
// 指向表頭節(jié)點
header *node
// 指向表尾節(jié)點
tail *node
// 跳躍表的長度（除了第一個節(jié)點）
length int64
// 跳躍表的最大層級（除了第一個節(jié)點）
level int16
}
創(chuàng)建跳躍表
// makeNode 創(chuàng)建一個跳躍表節(jié)點
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)建一個跳躍表結構
func makeSkiplist() *skiplist {
return &skiplist{
level: 1,
header: makeNode(maxLevel, 0, ""),
}
}
跳躍表的插入和刪除
在插入跳躍表之前，我們要明確的是新插入的這個節(jié)點，我們應該在它之上建立多少層索引呢？我們將通過一個隨機算法來計算得到一個隨機值，叫做冪次定律。
冪次定律的含義是：如果某件事的發(fā)生頻率和它的某個屬性成冪關系，那么這個頻率就可以稱之為符合冪次定律。映射到我們的需求就是一個新插入的節(jié)點，生成小數值層數的概率很大，而生成大數值層數的概率很小。
const (
maxLevel = 16
)
// randomLevel 隨機生成一個新跳躍表節(jié)點的層數（1~16）
// 滿足冪次定律
func randomLevel() int16 {
level := int16(1)
for float32(rand.Int31()&0xFFFF) < (0.25 * 0xFFFF) {
level++
}
if level < maxLevel {
return level
}
return maxLevel
}
上述函數計算出來的層數將呈現以下概率：
p = 0.25（1/4）
層數恰好為1的概率（不執(zhí)行while）為1 - p（3/4）.
層數恰好為2的概率（執(zhí)行 1 次while）為p * (1 - p)（3/16）.
層數恰好為3的概率（執(zhí)行 2 次while）為p ^ 2 * (1 - p)（3/64）.
層數恰好為4的概率（執(zhí)行 3 次while）為p ^ 3 * (1 - p)（3/256）.
層數恰好為k（k <= 32）的概率（執(zhí)行 k - 1 次while）為p ^ (k - 1) * (1 - p).
可以發(fā)現生成越高層數的概率會越來越小，而且和上一次呈冪關系遞減.
插入操作
插入操作的步驟：
- 首先準備兩個切片：update（用于保存在每一層，待插入節(jié)點的前一個節(jié)點）、rank（用于累加每一層的跨度，方便后續(xù)待插入節(jié)點索引中span字段的計算）。
- 從上至下遍歷每一層索引，在每一層中尋找待插入節(jié)點的位置（如果分數比當前節(jié)點小，就往后遍歷，比當前節(jié)點大就下沉），將待插入節(jié)點的前一個節(jié)點存到update切片中，然后將待插入節(jié)點相對起始點的便宜量粗存到rank切片中。
- 找到待插入節(jié)點的位置之后，先使用
randomLevel函數獲取該節(jié)點應該建立索引的層數。 - 接著構造節(jié)點，然后插入到應該插入的位置，首先需要更新每一層索引的狀態(tài)，新插入節(jié)點的forward指針就指向前一個節(jié)點的forward指針指向的位置（前一個節(jié)點保存在update切片中），新插入節(jié)點的索引span字段就是它與前一個節(jié)點同層索引的跨度之差（通過rank切片計算得到）。接著因為新插入節(jié)點增加了前面節(jié)點的跨度，所以需要更新前面一個節(jié)點每一層的跨度。
- 最后設置新插入節(jié)點的backward指針指向，直接指向前一個節(jié)點即可（通過update切片來實現）。
// insert 插入元素
func (skiplist *skiplist) insert(member string, score float64) *node {
// 保存在每一層，待插入節(jié)點的前一個節(jié)點
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
// 累加與前一個節(jié)點的跨度
rank[i] += node.level[i].span
// 前進
node = node.level[i].forward
}
}
update[i] = node
}
// 獲得隨機層數
level := randomLevel()
// 如果新插入的節(jié)點抽到的層級最大
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
}
// 構造新節(jié)點并插入到跳表
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é)點增加了前面節(jié)點的跨度
for i := level; i < skiplist.level; i++ {
update[i].level[i].span++
}
// 設置回退節(jié)點
if update[0] == skiplist.header {
node.backward = nil
} else {
node.backward = update[0]
}
// 設置node前面一個節(jié)點的回退節(jié)點
if node.level[0].forward != nil {
node.level[0].forward.backward = node
}
skiplist.length++
return node
}刪除操作
刪除操作首先要找到待刪除節(jié)點的位置，找節(jié)點的步驟與插入節(jié)點的操作類似的，首先創(chuàng)建一個切片：update（用于保存在每一層，待刪除節(jié)點的前一個節(jié)點）。然后在每一層中進行查找，分數比當前節(jié)點小，就往后遍歷，比當前節(jié)點大就下沉，同時用update切片記錄每一層中待刪除節(jié)點的前一個節(jié)點。找到該節(jié)點之后，就可以進行刪除操作了。
先更新每一層索引的狀態(tài)：更新待刪除節(jié)點前一個節(jié)點的跨度以及forward指針的指向。
然后更新后面一個節(jié)點的回退指針，最后更新跳表中的最大層級即可。
// 尋找待刪除的節(jié)點
func (skiplist *skiplist) remove(member string, score float64) bool {
// 儲存待刪除節(jié)點每一層的上一個節(jié)點
update := make([]*node, maxLevel)
node := skiplist.header
// 尋找待刪除節(jié)點
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é)點的前一個節(jié)點
// 在最底層的索引處向后移動一位，剛好就是待刪除節(jié)點
node = node.level[0].forward
// 找到該節(jié)點
if node != nil && score == node.Score && node.Member == member {
skiplist.removeNode(node, update)
return true
}
return false
}
// 刪除找到的節(jié)點
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--
}
}
// 更新后面一個節(jié)點的回退指針
if node.level[0].forward != nil {
node.level[0].forward.backward = node.backward
} else {
skiplist.tail = node.backward
}
// 更新跳表中的最大層級
for skiplist.level > 1 && skiplist.header.level[skiplist.level-1].forward == nil {
skiplist.level--
}
skiplist.length--
}跳躍表的排名操作
獲取元素的排名
獲取元素的排名操作比較簡單，首先定義一個rank整型變量，用于在遍歷的時候累加跨度。
接著逐層進行查找，在某一層進行查找時，每往前遍歷一個元素，就使用rank變量累加上它們索引之間的跨度，當遍歷到第0層時，就找到了這個節(jié)點，rank變量就是當前節(jié)點在整個跳躍表中的排名。
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
}
通過排名獲取元素
首先定義一個變量i用于累加每一層索引的跨度，接著在每一層索引中進行遍歷，如果i累加上當前節(jié)點層與下一個節(jié)點層的跨度值小于rank，就繼續(xù)往后遍歷，否則就下沉。當i等于rank時，就找到了該節(jié)點。
func (skiplist *skiplist) getByRank(rank int64) *node {
// 記錄從頭節(jié)點開始的跨度
var i int64 = 0
// 用于遍歷節(jié)點的指針
n := skiplist.header
// 從最高層級開始遍歷
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)建了一個ScoreBorder結構體用于封裝跳表的分數，提供了比較大小以及創(chuàng)建ScoreBorder等API。
const (
// 負無窮
negativeInf int8 = -1
// 正無窮
positiveInf int8 = 1
)
type ScoreBorder struct {
// 標記當前分數是否為無窮
Inf int8
// 分數值
Value float64
// 標記兩個分數相等時，是否返回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 根據參數構造并返回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的分數區(qū)間內（是否有重合）
判斷有三個指標：
- 判斷[min, max]區(qū)間本身是否有效。
- 判斷min是否大于跳表的最大分數值（與表尾元素的分數作比較）。
- 判斷max是否小于跳表的最小分數值（與表頭元素的分數作比較）。
func (skiplist *skiplist) hasInRange(min *ScoreBorder, max *ScoreBorder) bool {
// [min, max]無意義或為空
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ū)間的最小值
實現思路比較簡單，我們找到跳表中分數第一個大于min的節(jié)點即可。找到之后我們還需要將該節(jié)點的分數與max作比較，如果大于max，則不存在。
func (skiplist *skiplist) getFirstInScoreRange(min *ScoreBorder, max *ScoreBorder) *node {
if !skiplist.hasInRange(min, max) {
return nil
}
n := skiplist.header
// 找到第一個大于等于min的節(jié)點
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é)點的分數在[min, max]區(qū)間之外
if !max.greater(n.Score) {
return nil
}
return n
}刪除跳表中分數值處在[min, max]區(qū)間內的元素，并返回它們的切片
首先遍歷跳表，然后找到分數值大于min的第一個節(jié)點，從這個節(jié)點開始刪除，刪除一個就繼續(xù)往后遍歷，刪除的過程中還得判斷，待刪除的節(jié)點分數是否超出了[min, max]區(qū)間。
func (skiplist *skiplist) RemoveRangeByScore(min *ScoreBorder, max *ScoreBorder) (removed []*Element) {
// 儲存待刪除節(jié)點每一層的前驅節(jié)點
update := make([]*node, maxLevel)
removed = make([]*Element, 0)
// 找到待刪除節(jié)點每一層的前驅節(jié)點
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é)點
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ū)間內的元素，并返回它們的切片
首先定義一個i變量，作為刪除節(jié)點的迭代器，接著找到排名為start的節(jié)點，然后從這個節(jié)點往后刪除即可。
func (skiplist *skiplist) RemoveRangeByRank(start int64, stop int64) (removed []*Element) {
// 排名迭代器
var i int64 = 0
update := make([]*node, maxLevel)
removed = make([]*Element, 0)
// 找到待刪除的第一個節(jié)點的前驅節(jié)點，并儲存在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ū)間的第一個節(jié)點
node = node.level[0].forward
// 開始刪除節(jié)點
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
}完整實現
https://github.com/omlight95/GoRedis/blob/master/datastruct/sortedset/skiplist.go
到此這篇關于GO實現跳躍表的示例詳解的文章就介紹到這了,更多相關GO跳躍表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:
相關文章
這篇文章主要介紹了Go-RESTful實現下載功能,文件下載包括文件系統(tǒng)IO和網絡IO，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-10-10
這篇文章主要為大家介紹了golang逗號ok模式整合demo,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-11-11
項目開發(fā)過程中，隨著需求的迭代，代碼的發(fā)布會頻繁進行，在發(fā)布過程中，Golang如何讓程序做到優(yōu)雅的退出？本文就來詳細為大家講講2022-06-06
這篇文章主要介紹了go開發(fā)中引用靜態(tài)庫.a文件的方法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-11-11
這篇文章主要介紹了golang中context的作用,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
這篇文章主要為大家介紹了Golang實現秒讀32GB大文件的示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-12-12
Go并發(fā):使用sync.WaitGroup實現協(xié)程同步方式
這篇文章主要介紹了Go并發(fā):使用sync.WaitGroup實現協(xié)程同步方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-05-05
這篇文章主要介紹了詳解Golang使用MongoDB通用操作,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
這篇文章主要為大家詳細介紹了golang實現文件上傳并轉存數據庫功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
Go語言中三個輸入函數(scanf,scan,scanln)的區(qū)別解析
本文詳細介紹了Go語言中三個輸入函數Scanf、Scan和Scanln的區(qū)別,包括用法、功能和輸入終止條件等,本文給大家介紹的非常詳細,感興趣的朋友跟隨小編一起看看吧2024-10-10