跳跃表是一种有效的数据结构，它能够在n个元素的有序序列中实现O(log n)搜索复杂度和O(log n)插入复杂度。因此，它既是最佳的数组（便于搜索），同时也维护了一个类似链表的结构。通过维护子序列的链接层次结构，使得快速搜索成为可能，每个后续子序列跳过的元素比前一个子序列少（见下图）。
搜索通常从最稀疏的子序列开始（一般是自顶向下），直到找到两个连续的元素，一个小于或等于搜索目标的元素，另一个大于或等于搜索目标的元素。通过链接的层次结构，链接到这两个元素间的下一层子序列，然后在该子序列中继续搜索，直到最终完成整个序列的检索。
图1-跳跃表数据结构的示意图
每个带箭头的框表示一个指针，每一行是一个链表，包含一个稀疏子序列；底部的编号框（黄色）表示有序的数据序列。查询集合中的元素时，一般从顶部最稀疏的子序列向下执行，直到找到可能包含目标元素的连续元素区间。
跳跃列表是分层构建的，底层是一个普通的有序链表。每个高层则充当“快车道”的角色。对目标元素的搜索从顶部列表中的head元素开始，水平地进行，直到当前元素大于或等于目标元素。如果当前元素等于目标，则说明已经找到它。
如果当前元素大于目标元素，或者搜索到达链表的末尾，此时则返回前一个元素并转向下一个较低层级的列表后重复该过程。每个链表中预期的步骤数最多为1/p，通过选择不同的p值，可以用搜索成本来交换存储成本。
跳跃列表不能提供与传统的平衡树数据结构相同的针对最坏情况的性能保证，但在实际应用中工作得很好（比如Redis和LevelDB底层存储都是基于跳跃表），而且层数随机算法中的随机平衡方案一般比平衡二叉搜索树中使用的确定性平衡方案更容易实现。跳跃列表在并行计算中也很有用，在某些场景下，可以并行地在跳跃列表的不同部分执行插入，而无需对数据结构进行任何全局的重新平衡。
图2 插入要跳转列表的元素
基于Golang的实现细节
首先定义链表及节点的基本数据结构如下：
type SkipListNode struct { //跳跃表节点定义
key int
value interface{}
next []*SkipListNode
}
type SkipList struct { // 跳跃表结构定义
head,tail SkipListNode
length,level int
mut sync.RWMutex
rand *rand.Rand
}
结构体中元素说明：
- key/value为跳跃表中每个节点的键值对。
- next数组为指向多层链表节点的数组。
- head/tail指向跳跃表的起始节点指针地址。
- length/level分别为跳跃表长度和层数。
- mutex用于控制集合的并发访问。
- rand为内部保留的随机数。
随机算法：如何能保证O(logN)的复杂度？假设K层节点的数量是K+1层节点的P倍，那么这个跳跃表可以看成是一棵平衡P叉树，从最顶层开始查找某个节点需要的时间是O(logpN)（其中P是常量）。
const P uint32 = 4
func (list *SkipList) random() int {
//当新增节点时随机生成层数，定义一个平衡P叉树
//有多种实现算法，redis及leveldb中一般采用P=4的平衡四叉树
level:= 1
for level < list.length && ((list.rand.Uint32() % P) == 0) {
level++
}
if level < list.level {
return level
} else {
return list.level
}
}
插入节点算法简单描述如下：
func (list SkipList) AddNode(key int, value interface{}) {
list.mut.Lock()
defer list.mut.Unlock()
//生成随机层数
level:= list.random()
// 定位新元素的插入点
update:= make([]SkipListNode, level)
node:= list.head
//从高到低逐层进行定位（此处默认0为最底层）
for index := level - 1; index >= 0; index-- {
for {
nextNode:= node.next[index]
// n最开始指向最高层的head的next节点，从head开始逐个比较
if nextNode== list.tail || nextNode.key > key {
update[index]= node
break
} else if nextNode.key == key {
//此处简化算法，如果key值相同则覆盖，即仅保留唯一的key值节点
nextNode.value= value
return
} else {
//如未达到队尾且新增元素key值大于当前位置节点的key值，则继续遍历列表
node= nextNode
}
}
}
//生成并初始化新节点
newNode:= &SkipListNode{key, value, make([]*SkipListNode, level)}
for index, node := range update {
node.next[index], newNode.next[index] = newNode, node.next[index]
}
list.length++
}
// 其他主要方法算法逻辑类似，不再赘述
对于以上代码测试如下：
func main() {
//跳表使用演示
//工厂方法用于生成空列表，层数设为3
list:= NewSkipList(3)
list.AddNode(3,"jack")
list.AddNode(33,"hulu")
list.AddNode(97,"sig")
list.AddNode(9,"james")
fmt.Println(list)
}
// OUTPUT:
level-2: tail
level-1: <9, james> --> tail
level-0: <3, jack> --> <9, james> --><33, hulu> --> <97, sig> --> tail
有疑问加站长微信联系（非本文作者）
