数据结构之实现跳表

阅读学习极客时间《数据结构与算法之美》教程中跳表章节，为了验证跳表的查询速度究竟有多快，使用 go 语言实现了一个简单的跳表，下面简要介绍一下跳表是什么。

我们知道，如果要在一个单链表中实现查找，需要遍历整个链表，时间复杂度是 O(n)，而我们所熟知的二分查找时间复杂度是 O(logn)，跳表所要实现的就是，将使用链表存储的数据的查找时间复杂度变为 O(logn)，其核心就是建立一些索引链表，通过这些索引链表快速定位目标位置，如图：

可以看到，跳表就是在原始数据基础上，建立一个链表网格，每一层网格之间的节点数据宽度不一样，越往上层走，宽度越大，在数据量较大的时候，就可以明显的看出速度优势，因为索引可以显著的减少判断次数，迅速缩小节点查找范围。

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，其优势是简单，可读性好，不容易出错，因此更容易上手实现。

下面是基础的查询代码实现和查询时间对比，可以看到，速度优势明显。

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// 最简单的跳表实现，仅有构建跳表和查询跳表

package main

import (
	"fmt"
	"math/rand"
	"time"
)

// 设计链表的节点，为了方便，原始链表节点和索引节点使用同样的结构
type ListNode struct {
	Val   int
	Next  *ListNode
	Down  *ListNode
	Value string
}

var r *rand.Rand

func init() {
	r = rand.New(rand.NewSource(time.Now().Unix()))
}

// 生产随机字符串
func RandString(len int) string {
	bytes := make([]byte, len)
	for i := 0; i < len; i++ {
		b := r.Intn(26) + 97
		bytes[i] = byte(b)
	}
	return string(bytes)
}

// 构建索引
func buildSkipList(originList *ListNode) *ListNode {
	lists := []*ListNode{originList}

	// 这里我采用每间隔一个节点，创建一个索引的方式
	originCount := 1
	head := originList
	for head.Next != nil {
		originCount++
		head = head.Next
	}

	// 利用节点数量得出需要建立的索引层数
	for i := 1; (originCount >> uint(i)) != 0; i++ {
		head := lists[len(lists)-1]
		// 建立一个哨兵节点
		newHead := &ListNode{0, nil, nil, ""}
		lists = append(lists, newHead)

		// 形成二叉网格，每隔一个节点创建一个索引
		flag := true
		for true {
			if flag {
				newNode := &ListNode{head.Val, nil, head, head.Value}
				newHead.Next = newNode
				newHead = newNode
				flag = false
			} else {
				flag = true
			}
			if head.Next == nil {
				// 去掉哨兵节点
				lists[len(lists)-1] = lists[len(lists)-1].Next
				break
			}
			head = head.Next
		}
	}

	// 返回索引的头结点，通过这个节点就可以找到这个跳表上的所有子节点
	return lists[len(lists)-1]
}

// 查询跳表
func querySkipList(key int, headNode *ListNode) *ListNode {
	var result *ListNode
	head := headNode
	for true {
		if head == nil {
			break
		}
		if head.Val == key {
			result = head
			break
		}
		if head.Next == nil && head.Down == nil {
			break
		}
		// 在两个节点之间家/小于索引头节点/达到索引尾节点 就向下一层继续查询
		// 否则就沿着索引继续向后查找
		if head.Val < key && head.Next != nil && key < head.Next.Val {
			head = head.Down
		} else if key < head.Val {
			head = head.Down
		} else if head.Next == nil && head.Val < key {
			head = head.Down
		} else {
			head = head.Next
		}
	}
	return result
}

func skipList(originList *ListNode, k int) {
	headNode := buildSkipList(originList)

	// 跳表查找
	t := time.Now().UnixNano()
	var r *ListNode
	r = querySkipList(k, headNode)
	if r != nil {
		fmt.Println(r.Value)
	} else {
		fmt.Println("nil")
	}
	fmt.Println("跳表查找耗时：", time.Now().UnixNano()-t, "纳秒")
}

func ergodicList(originList *ListNode, k int) {
	// 顺序查找
	t := time.Now().UnixNano()
	h := originList
	for true {
		if h.Val == k {
			fmt.Println(h.Value)
			break
		}
		if h == nil {
			break
		}
		h = h.Next
	}
	fmt.Println("顺序查找耗时：", time.Now().UnixNano()-t, "纳秒")
}

func main() {
	// 建数据
	eleCount := 10000000 // 节点数量
	strCount := 5        // 随机生成 value 的长度
	k := 9000000         // 要查询的 key
	originList := &ListNode{0, nil, nil, ""}
	tempHead := originList
	for i := 1; i <= eleCount; i++ {
		tempHead.Next = &ListNode{i, nil, nil, RandString(strCount)}
		tempHead = tempHead.Next
	}
	originList = originList.Next

	skipList(originList, k)
	ergodicList(originList, k)
}

/*
下面是几次测试结果

一千万个节点，测试不同的 key 跑出结果耗时

k = 10000
dhanh
跳表查找耗时： 85000 纳秒
dhanh
顺序查找耗时： 98000 纳秒

k = 1000000
ulyvl
跳表查找耗时： 43000 纳秒
ulyvl
顺序查找耗时： 8541000 纳秒

k = 5000000
qhblp
跳表查找耗时： 64000 纳秒
qhblp
顺序查找耗时： 40690000 纳秒

k = 9000000
zuwza
跳表查找耗时： 46000 纳秒
zuwza
顺序查找耗时： 73129000 纳秒

由上面几次测试结果可以看出，跳表在大数据量情况下的优势非常明显
其 O(logn) 复杂度可以节省很多时间
*/
◀        
        ▶