// 未分类
SkipList「Golang实现」
发布 2021-02-23 · 永久链接
心血来潮写个跳表，有很多优化空间
``` json
package skiptable
import (
"math/rand"
"time"
)
func init() {
rand.Seed(time.Now().UnixNano())
}
// New get a new table
func New(maxLevel int) *SkipTable {
st := SkipTable{}
st.init(maxLevel)
return &st
}
// node
type node struct {
Level int
Key string
Value interface{}
Next []*node
}
// SkipTable table
type SkipTable struct {
MaxLevel int
Size int
Head *node
Tail *node
}
// PrintTable print this table
func (st *SkipTable) PrintTable() {
i := st.MaxLevel - 1
for i >= 0 {
c := st.Head
if c == st.Head {
print("[")
}
for c != st.Tail {
print(c.Key, "-")
c = c.Next[i]
}
if c == st.Tail {
print("]")
}
i = i - 1
println()
}
}
func (st *SkipTable) init(maxLevel int) {
st.MaxLevel = maxLevel
st.Tail = &node{
// Key: "tail"
}
st.Head = &node{
// Key: "head",
Level: 0,
Next: make([]*node, maxLevel),
}
a := 0
for a < len(st.Head.Next) {
st.Head.Next[a] = st.Tail
a = a + 1
}
}
// Put add data
func (st *SkipTable) Put(key string, value interface{}) {
pre := make([]*node, st.MaxLevel)
curr := st.Head
a := st.MaxLevel - 1
for a >= 0 {
if curr.Next[a] == st.Tail || curr.Next[a].Key > key {
pre[a] = curr
} else {
for curr.Next[a] != st.Tail && curr.Next[a].Key < key {
curr = curr.Next[a]
}
// equal
if curr.Next[a] != st.Tail && curr.Next[a].Key == key {
curr.Next[a].Value = value
return
}
pre[a] = curr
}
a = a - 1
}
level := getLevel(st.MaxLevel)
temp := &node{
Key: key,
Value: value,
Level: level,
Next: make([]*node, level),
}
a = 0
for a < level {
temp.Next[a] = pre[a].Next[a]
pre[a].Next[a] = temp
a = a + 1
}
st.Size = st.Size + 1
}
// Del delete value by key
func (st *SkipTable) Del(key string) {
pre := make([]*node, st.MaxLevel)
curr := st.Head
top := st.MaxLevel - 1
for top >= 0 {
if curr.Next[top] == st.Tail || curr.Next[top].Key > key {
pre[top] = nil
} else {
for curr.Next[top] != st.Tail && curr.Next[top].Key < key {
curr = curr.Next[top]
}
if curr.Next[top] != st.Tail && curr.Next[top].Key == key {
pre[top] = curr
} else {
pre[top] = nil
}
}
top = top - 1
}
top = st.MaxLevel - 1
for top >= 0 {
if pre[top] != nil {
println("pre[top].Next[top]-->", pre[top].Next[top].Key)
pre[top].Next[top] = pre[top].Next[top].Next[top]
}
top = top - 1
}
}
// Get get value by key
func (st *SkipTable) Get(key string) interface{} {
curr := st.Head
top := st.MaxLevel - 1
for top >= 0 {
for curr.Next[top] != st.Tail && curr.Next[top].Key < key {
curr = curr.Next[top]
}
if curr.Next[top].Key == key {
return curr.Next[top].Value
}
top = top - 1
}
return nil
}
func getLevel(max int) int {
level := 1
for {
temp := rand.Int()
if temp%2 == 0 && level < max {
level = level + 1
} else {
break
}
}
return level
}
```
跳表是我很喜欢的一种结构，好像之前也用java写过，就当用来熟悉语言了.
这是种空间换时间的数据结构, 第一次听说是在redis的zset里，当然，里边的实现要复杂多，还维护了`score`、额外的`后退指针`等