跳表的数据结构
跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
跳表的数据结构
其中-1表示INT_MIN， 链表的最小值，1表示INT_MAX，链表的最大值。
跳表的性质
- 由很多层结构组成
- 每一层都是一个有序的链表
- 最底层(Level 1)的链表包含所有元素
- 如果一个元素出现在Level i的链表中，则它在Level i之下的链表也都会出现。
- 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
1. 跳表的get操作
查找元素117的过程
例子：查找元素 117
- 比较21，比21大，往后面找
- 比较37, 比37大，比链表最大值小，从37的下面一层开始找
- 比较71, 比71大，比链表最大值小，从71的下面一层开始找
- 比较85，比85大，从后面找
- 比较117，等于117， 找到了节点。
2. 跳表的insert操作
先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）
然后在 Level 1 ... Level K 各个层的链表都插入元素。
例子：插入 119， K = 2
跳表的insert操作
如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4
跳表的insert操作
丢硬币决定K的值
插入元素的时候，元素所占有的层数完全是随机的，通过一下随机算法产生：
public int random_level() {
int k = 1;
while (Math.random() <= 0.5f) {
k++;
}
return k;
}
相当于做一次丢硬币的实验，如果遇到正面，继续丢，遇到反面，则停止。各个元素的层数，期望值是2层。
3. 跳表的delete操作
在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。
例子：删除 71
跳表的delete操作
实现步骤
- 定义一个跳表的Node类
- 私有变量，保存层数K和链表最高层最小的节点（即最左结点）
- 按照上面的图，写出每个函数，注意边界判断
需求只要很明确，接下来都是体力活了。代码就不写了，毕竟跳跃表只是个思想，很多细节东西都是因人而异，因业务而异。
总结
大部分编程语言中的Map类型都是通过红黑树实现的，我们在写程序的时候，可以直接拿过来用，不用自己再去实现一个红黑树。但是跳表并没有一个现成的实现，所以在开发中，如果要使用跳表这种数据结构，需要自己先去实现。
哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我
网友评论