增加了向前指针(或者叫向下指针)的链表叫作跳表。跳表全称叫做跳跃表,简称跳表。跳表是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引,通过索引来实现快速查找。跳表不仅能提高搜索性能,同时也可以提高插入和删除操作的性能。
其中一个比较好的办法就是跳表(就是比较废内存...)
在说跳表之前首先需要说的是二分查找。
猜数字游戏(应该都写过吧~):给定1 - 100中的随机一个数x,玩家猜一个数字,告诉你大了还是小了或者猜到了。问需要猜几次?每次我们取其中一半,逐渐缩小。如:50,25,12...对于n个数字,猜到的时间复杂度为O(logn)非常高效。
同理,如果我们在链表中找数字x前,先看x/2节点的值是大还是小,再向前遍历不就可以了吗?当然当我们在x/2节点过程中不能用遍历。
时间不够空间来凑。我们只需要在原有的链表基础上创建一个新的节点对象Node_m,其中 Node_m 包含中间节点的引用(其实是随机出的节点)和排序的分值。每次通过 Node_m 去找到对应的中间节点即可,然后判断大了还是小了进行向前或者向后查找(如果是单链表,就是从头开始,还是从中间开始向后查找)。就可以了
继续优化
如果我们要找的数字刚好在这个链表在前半部分或者最后。如:1 - 10亿,而我们要找的数字刚好是4_9999_9999。不还是从头开始遍历吗?这个时候,我们就可以考虑拆分粒度。二分查找可以变成三查找,四分查找,五分查找..X分查找(其实是概率函数)。
这样我们需要的外部节点就不是只有 Node_m 一个节点了,而是x个节点组成的集合,我们将这m个节点组成一个新的线性表。就相当于在原来的链表上面再加一层链表(索引),链表中的每一个节点都额外加指向原始链表的引用:
继续优化
如果原始链表的大小实在太大,如:10亿数据,我们上层的索引平均对应每100个一个节点,那么索引也要1千万个节点。遍历1千万节点的链表也需要一定的时间,有没有什么更快的办法呢?很简单,这就回到了我们最初问题的递归。有没有什么办法可以让一个链表查找速度更快呢?有加一层索引~
上述这种链表加多级索引的结构就称之为——跳表了。
在单链表中,一旦定位好要插入的位置,插入结点的时间复杂度是很低的,就是 O(1)。但是,这里为了保证原始链表中数据的有序性,我们需要先找到要插入的位置,这时就需要遍历O(n)来找到要插入位置。但是,对于跳表来说,查找的复杂度是 O(logn),所以这里查找某个数据应该插入的位置,方法也是类似的,时间复杂度也是 O(logn)。如下:
再来看删除操作。
如果删除的这个结点在索引中也有出现,我们除了要删除原始链表中的结点,还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点,然后通过指针操作完成删除。所以在查找要删除的结点的时候,一定要获取前驱结点。当然,如果我们用的是双向链表,就不需要考虑这个问题了。
当我们不停地往跳表中插入数据时,如果我们不更新索引,就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下,跳表还会退化成单链表。
作为一种动态数据结构,跳表需要维护索引与原始链表大小之间的平衡,也就是说,如果链表中结点多了,索引结点就相应地增加一些,避免复杂度退化,以及查找、插入、删除操作性能下降。
这里可以通过随机函数来维护前面提到的“平衡性”。当我们往跳表中插入数据的时候,我们可以选择同时将这个数据插入到部分索引层中。如何选择加入哪些索引层呢?我们通过一个随机函数,来决定将这个结点插入到哪几级索引中,比如随机函数生成了值 K,那我们就将这个结点添加到第一级到第 K 级这 K 级索引中。
也就是前面我们所谓的“n分查找”,不是基于一半或者多少个而是随机函数。
随机函数的选择很有讲究,从概率上来讲,能够保证跳表的索引大小和数据大小平衡性,不至于性能过度退化。至于随机函数的选择,感兴趣的话,可以去了解Redis 中关于有序集合的跳表实现。
import java.util.Random;
/**
* 1,跳表的一种实现方法,用于练习。跳表中存储的是正整数,并且存储的是不重复的。
* 2,本类是参考作者zheng ,自己学习,优化了添加方法
* 3,看完这个,我觉得再看ConcurrentSkipListMap 源码,会有很大收获
* Author:ldb
*/
public class SkipList2 {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
/**
* 带头链表
*/
private Node head = new Node(MAX_LEVEL);
private Random r = new Random();
public Node find(int value) {
Node p = head;
// 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
/**
* 优化了作者zheng的插入方法
*
* @param value 值
*/
public void insert(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层,如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
// 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level,所以加上判断
if (level > i) {
update[i] = p;
}
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
/**
* 优化了作者zheng的插入方法2
*
* @param value 值
*/
public void insert2(int value) {
int level = head.forwards[0] == null ? 1 : randomLevel();
// 每次只增加一层,如果条件满足
if (level > levelCount) {
level = ++levelCount;
}
Node newNode = new Node(level);
newNode.data = value;
Node p = head;
// 从最大层开始查找,找到前一节点,通过--i,移动到下层再开始查找
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
// 找到前一节点
p = p.forwards[i];
}
// levelCount 会 > level,所以加上判断
if (level > i) {
if (p.forwards[i] == null) {
p.forwards[i] = newNode;
} else {
Node next = p.forwards[i];
p.forwards[i] = newNode;
newNode.forwards[i] = next;
}
}
}
}
/**
* 作者zheng的插入方法,未优化前,优化后参见上面insert()
*
* @param value
* @param level 0 表示随机层数,不为0,表示指定层数,指定层数
* 可以让每次打印结果不变动,这里是为了便于学习理解
*/
public void insert(int value, int level) {
// 随机一个层数
if (level == 0) {
level = randomLevel();
}
// 创建新节点
Node newNode = new Node(level);
newNode.data = value;
// 表示从最大层到低层,都要有节点数据
newNode.maxLevel = level;
// 记录要更新的层数,表示新节点要更新到哪几层
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
/**
*
* 1,说明:层是从下到上的,这里最下层编号是0,最上层编号是15
* 2,这里没有从已有数据最大层(编号最大)开始找,(而是随机层的最大层)导致有些问题。
* 如果数据量为1亿,随机level=1 ,那么插入时间复杂度为O(n)
*/
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
// 这里update[i]表示当前层节点的前一节点,因为要找到前一节点,才好插入数据
update[i] = p;
}
// 将每一层节点和后面节点关联
for (int i = 0; i < level; ++i) {
// 记录当前层节点后面节点指针
newNode.forwards[i] = update[i].forwards[i];
// 前一个节点的指针,指向当前节点
update[i].forwards[i] = newNode;
}
// 更新层高
if (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
/**
* 随机 level 次,如果是奇数层数 +1,防止伪随机
*
* @return
*/
private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
/**
* 打印每个节点数据和最大层数
*/
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
/**
* 打印所有数据
*/
public void printAll_beautiful() {
Node p = head;
Node[] c = p.forwards;
Node[] d = c;
int maxLevel = c.length;
for (int i = maxLevel - 1; i >= 0; i--) {
do {
System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
} while (d[i] != null && (d = d[i].forwards)[i] != null);
System.out.println();
d = c;
}
}
/**
* 跳表的节点,每个节点记录了当前节点数据和所在层数数据
*/
public class Node {
private int data = -1;
/**
* 表示当前节点位置的下一个节点所有层的数据,从上层切换到下层,就是数组下标-1,
* forwards[3]表示当前节点在第三层的下一个节点。
*/
private Node forwards[];
/**
* 这个值其实可以不用,看优化insert()
*/
private int maxLevel = 0;
public Node(int level) {
forwards = new Node[level];
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
}
本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/数据结构基础06线性数据结构之跳表
最后更新:2020-01-26 20:37:27
Update your browser to view this website correctly. Update my browser now