Go语言实现跳表(SkipList)

第一次,站长亲自招 Gopher 了>>>

跳表(skiplist)在redis/levelDB中属于核心数据结构,我简单粗暴的用Golang实现了下。

就我的简单理解来说,就一个普通的链表,在insert时,通过Random_level(),把一层变成很多层,

越上数据越小,跨度越大。 查找时从上往下找,如果在一层没找到,在下一层继续时,以此节点作为起始,

继续查找,是一种用空间换时间的方式。

测试代码:

package main
//SkipList
//author:Xiong Chuan Liang
//date:2014年1月28日
import (
	"github.com/xcltapestry/xclpkg/algorithm"
)
func main() {
	slt := algorithm.NewSkipList()
	for i := 100; i > 0; i-- {
		slt.Insert(i)
	}
	slt.PrintSkipList()
	slt.Search(15)
	slt.Search(93)
	slt.Remove(93)
	slt.PrintSkipList()
}

运行效果 :

SkipList-------------------------------------------
level: 7
--------------------------------------------------------
level: 6
--------------------------------------------------------
level: 5
--------------------------------------------------------
level: 4
--------------------------------------------------------
level: 3
93
--------------------------------------------------------
level: 2
36 93
--------------------------------------------------------
level: 1
6 10 22 23 25 36 42 47 48 54 55 61 72 75 78 82 89 93
--------------------------------------------------------
level: 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
--------------------------------------------------------
Current MaxLevel: 4
 Search() Level= 3
 93
 Search() Level= 2
 36
 Search() Level= 1
 6 10 22
 Search() Level= 0
 11 12 13 14 15
Found level= 0 key= 15
 Search() Level= 3
 93
Found level= 3 key= 93
Remove() level= 3 key= 93
Remove() level= 2 key= 93
Remove() level= 1 key= 93
Remove() level= 0 key= 93
SkipList-------------------------------------------
level: 7
--------------------------------------------------------
level: 6
--------------------------------------------------------
level: 5
--------------------------------------------------------
level: 4
--------------------------------------------------------
level: 3
--------------------------------------------------------
level: 2
36
--------------------------------------------------------
level: 1
6 10 22 23 25 36 42 47 48 54 55 61 72 75 78 82 89
--------------------------------------------------------
level: 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 
36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 94 95 96 97 98 99 100
--------------------------------------------------------
Current MaxLevel: 3

从上面可以很清楚的看到构成及查找过程.

跳表的结构体:

type Node struct {
	Forward []Node
	Value interface{}
}
type SkipList struct {
	Header *Node
	Level int
}

与普通List不同,因为跳表在从上层移到下层查找时,要跳过上层已遍历过的Node,所以,要求在下一层时,立马转到对应位置,因此在Node中定

义了Forward数组. 最初实现时,我使用分层次的普通List来做,构建,删除Node啥的都很方便,但发现查找怎么实现都不太对,才发现思路错了,

只好重构改成现在的方式.效果还比较理想.

实现代码放在Github上. https://github.com/xcltapestry/xclpkg/tree/master/algorithm

欢迎指正.

另外,图灵社区关于跳表的两篇文章相当不错: http://www.ituring.com.cn/article/59053

MAIL: xcl_168@aliyun.com
BLOG: http://blog.csdn.net./xcl168

---

本文来自:CSDN博客

感谢作者:xcltapestry

查看原文:Go语言实现跳表(SkipList)

6140 次点击

上一篇:Go语言struct的创建与初始化、函数调用

下一篇:GO语言运行cmd命令逐行实时输出执行过程

跳表 github http 代码

• 编辑
• 预览