手把手教你用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()
}