有关SkipList的定义，请参考跳跃表（可能需要科学上网）。我们知道，有序链表，无论是单向还是双向，增删改查时间复杂度都是O(n)。跳跃表的存在就是为了解决这个问题，解决思路为空间换时间，不过空间复杂度没有提升，仍然为O(n)（理论上使用的空间变为原来的1-2倍，数学期望为n+log(n)倍），但是增删改查的时间复杂度降低为O(log(n))，其性能可以媲美二叉树家族（AVL树，红黑树），但在并发情况下，二叉树在增删操作后进行重新平衡需要加锁的节点要比跳跃表多，所以整体性能表现上，跳跃表要优于二叉树。
本文将使用go语言实现跳跃表的增、删、改、查操作，考虑到业务上的使用场景，该实现将支持协程安全。
一个典型的单向四层跳跃表如图1：
图1.单向四层跳跃表示意图
由图1可以看到，跳跃表具有以下特性：
1、层数（LEVEL）越高，链上的节点越少，大致呈P=0.5的几何分布。
2、每一层的节点均有序且不重复。
跳跃表层数（LEVEL）的设置，应当与数据量息息相关，合理的取值应该为log(n)，对数底数为2，当然，考虑到数据量增长，大于log(n)也是可以的。比如，数据量为30亿条，则合理的层数取值应该为31<log(3000000000)<32，故LEVEL应取32。
首先，定义节点结构体：
type SkipListNode struct {
key int
data interface{}
next []*SkipListNode
}
其中，key为排序使用的字段，对应图1中的数字1~9；data为实际存储的数据，可以为任何类型，图1中并没有体现；next为节点指针切片，比如图1中的"HEAD"节点的next应该为[&5, &3, &1, &1]，“3”节点的next应该为[&5, &5, &4]，其中&n表示key为n节点的地址。
定义跳跃表结构体：
type SkipList struct {
head *SkipListNode
tail *SkipListNode
length int
level int
mut *sync.RWMutex
rand *rand.Rand
}
head：头节点
tail：尾节点
length： 数据总量
level：层数
mut：互斥锁，用于保证协程安全
rand：随机数生成器，用于生成随机层数，随机生成的层数要满足P=0.5的几何分布，大致可以理解为：掷硬币连续出现正面的次数，就是我们要的层数。所以随机生成层数的方法可以定义如下：
func (list *SkipList) randomLevel() int {
level := 1
for ; level < list.level && list.rand.Uint32() & 0x1 == 1; level ++{}
return level
}
补上一个工厂构造方法：
func NewSkipList(level int) *SkipList {
list := &SkipList{}
if level <=0 {
level =32
}
list.level = level
list.head = &SkipListNode{next:make([]*SkipListNode, level, level)}
list.tail = &SkipListNode{}
list.mut = &sync.RWMutex{}
list.rand = rand.New(rand.NewSource(time.Now().UnixNano()))
for index :=range list.head.next {
list.head.next[index] = list.tail
}
return list
}
接下来实现数据插入方法。假设我们目前的跳跃表已经有如下数据：
图2.需要插入数据的跳跃表
我们需要插入一个3，并且调用randomLevel得到的层数为3，那么插入3需要如下几部：
1、沿着LEVEL3的链查找第一个比3大的节点或者TAIL节点，记录下该节点的前一个节点——HEAD和层数——3。
2、沿着LEVEL2的链查找第一个比3大的节点或者TAIL节点，记录下该节点的前一个节点——&1和层数——2。
3、沿着LEVEL1的链查找第一个比3大的节点或者TAIL节点，记录下该节点的前一个节点——&2和层数——1。
4、生成一个新的节点newNode，key赋值为3，将newNode插入HEAD、&1、&2之后，即HEAD.next[3]=&3，&1.next[2]=&3，&2.next[1]=&3。
5、给newNode的next赋值，即步骤4中HEAD.next[3]、&1.next[2]、2.next[1]原本的值。
注意：为了易于理解，上述步骤中所有索引均从1开始，而代码中则从0开始，所以代码中均有索引=层数-1的关系。
那么，插入的代码可以写成这样：
func (list *SkipList) Add(key int, data interface{}) {
list.mut.Lock()
defer list.mut.Unlock()
//1.确定插入深度
level := list.randomLevel()
//2.查找插入部位
update :=make([]*SkipListNode, level, level)
node := list.head
for index := level -1; index >=0; index -- {
for {
node1 := node.next[index]
if node1 == list.tail || node1.key > key {
update[index] = node//找到一个插入部位
break
}else if node1.key == key{
node1.data = data
return
}else {
node = node1
}
}
}
//3.执行插入
newNode := &SkipListNode{key, data, make([]*SkipListNode, level, level)}
for index, node :=range update {
node.next[index],newNode.next[index] = newNode,node.next[index]
}
list.length ++
}
实际上，删除、查找的方法与插入变化不大。
删除方法：
func (list *SkipList) Remove(key int) bool {
list.mut.Lock()
defer list.mut.Unlock()
//1.查找删除节点
node := list.head
remove :=make([]*SkipListNode, list.level, list.level)
var target *SkipListNode
for index :=len(node.next) -1; index >=0; index -- {
for {
node1 := node.next[index]
if node1 == list.tail || node1.key > key{
break
}else if node1.key == key {
remove[index] = node//找到啦
target = node1
break
}else {
node = node1
}
}
}
//2.执行删除
if target != nil {
for index, node1 :=range remove {
if node1 != nil {
node1.next[index] = target.next[index]
}
}
list.length --
return true
}
return false
}
查找方法：
func (list *SkipList)Find(key int) interface{} {
list.mut.RLock()
defer list.mut.RUnlock()
node := list.head
for index :=len(node.next) -1; index >=0; index -- {
for {
node1 := node.next[index]
if node1 == list.tail || node1.key > key {
break
}else if node1.key == key {
return node1.data
}else {
node = node1
}
}
}
return nil
}
最后，是获取数据总量方法：
func (list *SkipList) Length() int {
list.mut.RLock()
defer list.mut.RUnlock()
return list.length
}
就这样，一个单向的跳跃表就实现了，是不是很简单呢？
网友评论