Go语言实现跳表(SkipList)

xcltapestry · · 5398 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

           跳表(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)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

5398 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传