手把手教你用go語言實作跳躍表

前言

有序集合在生活中較常見，如根據成績對學生進行排名、根據得分對游戲玩家進行排名等，對于有序集合的底層實作，我們可以使用陣列、鏈表、平衡樹等結構，陣列不便于元素的插入和洗掉;鏈表的查詢效率低，需要遍歷所有元素;平衡樹或者紅黑樹等結構雖然效率高但實作復雜，Redis采用了一種新型的資料結構——跳躍表，跳躍表的效率堪比紅黑樹，然而其實作卻遠比紅黑樹簡單，

1、redis有序集合介紹

skiplist 編碼的有序集合物件使用 zet 結構作為底層實作，一個 zset 結構同時包含一個字典和一個跳躍表：

typedef struct zset{
     //跳躍表
     zskiplist *zsl;
     //字典
     dict *dict;
} zset;

• 字典的鍵保存元素的值，字典的值則保存元素的分值；跳躍表節點的 object 屬性保存元素的成員，跳躍表節點的 score 屬性保存元素的分值，故查詢元素的分值，時間復雜度為O(1)，獲取分值的元素，時間復雜度為O(logn)，

• 這兩種資料結構會通過指標來共享相同元素的成員和分值，所以不會產生重復成員和分值，造成記憶體的浪費，

2、跳躍表實作原理

2.1 跳躍表介紹

跳躍表是一個有序鏈表，其中每個節點包含不定數量的鏈接，節點中的第i個鏈接構成的單向鏈表跳過含有少于i個鏈接的節點，

2.2 隨機層數值

level的初始值為1，通過while回圈，每次生成一個隨機值，小于rate=0.25倍的maxheight=64 時，level的值加1﹔否則退出 while回圈，

下面計算節點的期望層高，p=0.25

2.3 代碼實作

代碼運行結果，跳躍表結構如下，包含A、B、C、D、E五個節點：

跳躍表插入節點的核心，找到需要插入的位置，找到需要更新的節點，

如下圖，在箭頭位置插入層數為3的新節點，先找到需要更新的前一個節點，記錄在update陣列中（圖淺藍色標識），記錄head節點到更新節點的累計跨度到rank陣列，接下來，就是更新update陣列和新節點的后繼節點，以及span跨度，

代碼如下：

package main

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

const (
	maxheight = 64
	rate      = 0.25
	name      = "zksip"
)

type zskipList struct {
	head   *zskipListNode
	tail   *zskipListNode
	length int
	level  int
}
type zskipLevel struct {
	forward *zskipListNode
	span    int
}
type zskipListNode struct {
	ele      string
	score    float32
	backward *zskipListNode
	level    []zskipLevel
}

var zlist *zskipList

func createNode(num int) *zskipListNode {
	node := new(zskipListNode)
	node.level = make([]zskipLevel, num)
	return node
}
func createZskipList() {
	zlist = new(zskipList)
	zlist.head = createNode(maxheight)
	zlist.level = 1
	zlist.tail = nil
}

//隨機獲取層數
func getLevel() int {
	level := 1
	//return 3
	for i := 0; i < maxheight; i++ {
		num := rand.Intn(maxheight)
		if num < rate*maxheight {
			return level
		}
		level += 1
	}
	return level
}
func insert(ele string, score float32) {
	//創建該節點
	level := getLevel()
	node := createNode(level)
	fmt.Printf("當前層數%d,值=%.1f\n", level, score)
	node.ele = ele
	node.score = score

	//update陣列記錄插入節點的前一個節點bef（bef節點為需要修改的節點）
	update := make([]*zskipLevel, zlist.level)
	//rank陣列記錄從head到bef節點的累計跨度
	rank := make([]int, zlist.level)
	//第一次插入
	if zlist.length == 0 {
		for i := level - 1; i >= 0; i-- {
			zlist.head.level[i].forward = node
			zlist.head.level[i].span = 1
		}
		zlist.tail = node
		zlist.level = level
	} else {
		p := zlist.head
		rankSum := 0
		//從最高層開始找，尋找每一層的bef節點
		for i, k := zlist.level-1, 0; i >= 0; {
			//當前節點的next節點為空，或者next節點的score值比新節點值大，則
			//當前節點即為bef節點
			if (p.level[i].forward == nil) || (score < p.level[i].forward.score) {
				update[i] = &p.level[i]
				rank[k] = rankSum
				i--
				k++
			} else {
				rankSum += p.level[i].span
				//當前層還未尋找到bef節點，當前層rank值繼續累加
				p = p.level[i].forward
			}
		}
		temp := rank[len(rank)-1]
		var rankIndex int
		for i := 0; i < level && i < len(update); i++ {
			rankIndex = len(rank) - 1 - i
			//更新節點的next節點
			node.level[i].forward = update[i].forward
			//更新節點的span
			node.level[i].span = update[i].span - (temp - rank[rankIndex])

			update[i].forward = node
			update[i].span = temp - rank[rankIndex] + 1
		}

		//當新建節點層數大于zskip的最大層數，更新head到node節點的跨度
		for i := level; i > zlist.level; i-- {
			zlist.head.level[i-1].forward = node
			zlist.head.level[i-1].span = temp + 1
		}
		//當新建節點層數小于zskip的最大層數，update陣列中level~zlist.level層數節點的跨度+1
		for i := level; i < zlist.level; i++ {
			update[i].span++
		}
	}

	if zlist.level < level {
		zlist.level = level
	}
	zlist.length += 1
}
func printLevelDetail(head zskipLevel, layer int) {

	headDesc := fmt.Sprintf("%d:[head],%d -> ", layer+1, head.span)
	desc := fmt.Sprintf("%15s", headDesc)
	for i := 0; i < head.span-1; i++ {
		desc += fmt.Sprintf("%15s", "-> ")
	}
	p := head.forward
	for p != nil {
		item := fmt.Sprintf("[%s,%.1f],%d -> ", p.ele, p.score, p.level[layer].span)
		itemSpan := ""
		for i := 0; i < p.level[layer].span-1; i++ {
			itemSpan += fmt.Sprintf("%15s", "-> ")
		}
		desc += fmt.Sprintf("%15s", item) + itemSpan
		p = p.level[layer].forward
	}
	fmt.Println(desc)
}

//結構化列印跳表資料結構
func printZskipDetail() {
	for i := zlist.level - 1; i >= 0; i-- {
		printLevelDetail(zlist.head.level[i], i)
	}
}

func main() {
	rand.Seed(time.Now().UnixNano())
	//創建空跳表
	createZskipList()
	//插入元素
	insert("A", 10)
	insert("B", 12)
	insert("C", 13)
	insert("D", 11)
	insert("E", 12.5)
	//格式化列印
	printZskipDetail()
}