对于一个链表的查询和列表不同。如果列表是有序的那么可以用二分查找,时间复杂度为log n，链表即便是有序的，查询一个元素也是要从头遍历，时间复杂度为O(n) 。为了解决链表的查询效率问题，出现了一些特殊的数据结构，例如：树类的包括1、二叉树 2、平衡二叉树（理想最好情况）3、红黑树 4、b 树 5、b+ 树 等等，还有一种区别于树类型的数据结构：跳跃表。跳跃表类似多维链表，最高纬跳跃最大，最低纬就是普通的链表存储了所有的数据。例如链表 7 - 21 - 32 - 37 -71 - 85 如下图
image.png
1、初始化先由下到上创建一个head竖向链表，Node的值为空，无穷小。
2、跳跃表的查找过程，例如查找的是节点32。红线是指针变化过程，虚线是判断过程。如图
image.png
3、插入：首先查找到需要插入节点的最低纬链表的位置指针，并且记录每个维度最左位置的指针。然后随机生成高度。例如插入的数值为35，随机高度为4，如图
image.png
4、性能
查找、插入和删除操作的时间复杂度都为: O(logn)
随机跳跃表表现性能也非常不错，节省了大量复杂的调节平衡树的代码。其效率与红黑树、伸展树等这些平衡树能够说相差不大。
但跳跃表还在并发环境下有优势。在并发环境下。假设要更新数据，跳跃表须要更新的部分就比較少，锁的东西也就比較少。所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。跳跃表的缺点是，存储空间占用相对较大一些。
5、应用
jdk 中有对跳跃表的并发实现：
ConcurrentSkipListMap
ConcurrentSkipListSet
了解过Redis的都知道，Redis有一个非常实用的数据结构：SortSet，基于它，我们能够非常轻松的实现一个Top N的应用。这个SortSet底层就是利用跳表实现的。
总结
作为一种简单的数据结构，在大多数应用中Skip lists可以取代平衡树。Skiplists算法很easy实现、扩展和改动。
Skip lists和进行过优化的平衡树有着相同高的性能 （红黑树）。
java代码实现：
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
public class SkipList<E, C extends Comparable<? super C>> {
//最大层级
static final int MAX_LEVEL = 1 << 6;
static final int DEFAULT_LEVEL = 4;
//跳跃表 down node 的层级
int level;
//头节点
Node<E, C> head;
ThreadLocalRandom random = ThreadLocalRandom.current();
public SkipList() {
this(DEFAULT_LEVEL);
}
//跳跃表的初始化
public SkipList(int level) {
this.level = level;
int i = level;
Node<E, C> temp = null;
Node<E, C> prev = null;
//从底部节点开始创建链表
while (i-- != 0) {
temp = new Node(null, (T) -> -1);
temp.down = prev;
prev = temp;
}
head = temp;//头节点
}
public void put(E val, C score) {
Node<E, C> t = head;
//存储每个层级，插入新节点的最左边节点
List<Node<E, C>> paths = new ArrayList<>();
//1，找到需要插入的位置
while (t != null) {
//表示存在该值的点，表示需要更新该节点
if (t.score.compareTo(score) == 0) {
Entity e = t.entity;
//插入到链表尾部
e.next = new Entity(val, null);
return;
}
//查找插入的位置
if (t.next == null || t.next.score.compareTo(score) > 0) {
paths.add(t);
t = t.down;
} else {
t = t.next;
}
}
//随机生成新节点的层级
int lev = randomLevel();
// 如果随机的层级数，大于head节点的层级数
// 需要更新head这一列的节点数量,保证head列数量最多
if (lev > level) {
Node<E, C> temp = null;
Node<E, C> prev = head;
while (level++ != lev) {
temp = new Node(null, (T) -> -1);
paths.add(0, temp);
temp.down = prev;
prev = temp;
}
head = temp;
//更新层级
level = lev;
}
//从后向前遍历path中的每一个节点，在其后面增加一个新的节点
Node<E, C> down = null, newNade = null, path = null;
Entity<E> e = new Entity<>(val, null);
for (int i = level - 1; i >= level - lev; i--) {
//创建新的节点
newNade = new Node<E, C>(e, score);
path = paths.get(i);
newNade.next = path.next;
path.next = newNade;
newNade.down = down;
down = newNade;
}
}
/**
* 查找跳跃表中的一个值
*/
public List<E> get(C score) {
Node<E, C> t = head;
while (t != null) {
if (t.score.compareTo(score) == 0) {
return t.entity.toList();
}
if (t.next == null || t.next.score.compareTo(score) > 0) {
t = t.down;
} else {
t = t.next;
}
}
return null;
}
/**
* 查找跳跃表中指定范围的值
*/
public List<E> find(final C begin, C and) {
Node<E, C> t = head;
Node<E, C> beginNode = null;
//确定下界索引
while (t != null) {
beginNode = t;
if (t.next == null || t.next.score.compareTo(begin) >= 0) {
t = t.down;
} else {
t = t.next;
}
}
//循环链表
List<E> list = new ArrayList<>();
for (Node n = beginNode.next; n != null; n = n.next) {
if (n.entity != null && n.score.compareTo(and) < 0)
list.addAll(n.entity.toList());
}
return list;
}
/**
* 根据score的值来删除节点。
*/
public void delete(C score) {
//1,查找到节点列的第一个节点的前驱
Node<E, C> t = head;
while (t != null) {
if (t.next == null || t.next.score.compareTo(score) > 0) {
//向下查找
t = t.down;
} else if (t.next.score.compareTo(score) == 0) {
// 在这里说明找到了该删除的节点
t.next = t.next.next;
//向下查找
t = t.down;
} else {
//向右查找
t = t.next;
}
}
}
/**
* 高度随机增加一
*/
private int randomLevel() {
int lev = 1;
//产生一个非负整数
while (random.nextInt() % 2 == 0)
lev++;
return Math.min(lev, MAX_LEVEL);
}
/**
* 跳跃表的节点链表
*/
static class Node<E, C extends Comparable> {
Entity<E> entity;//存储的数据
C score; //需要排序的字段
Node<E, C> next;//指向下一个节点的指针
Node<E, C> down;//指向下一层的指针
Node(Entity<E> entity, C score) {
this.entity = entity;
this.score = score;
}
@Override
public String toString() {
return "Node{score=" + score + '}';
}
}
static class Entity<E> {
E val;
Entity<E> next;
Entity(E val, Entity<E> next) {
this.val = val;
this.next = next;
}
List<E> toList() {
List<E> list = new ArrayList<>();
list.add(val);
for (Entity<E> e = next; e != null; e = e.next) {
list.add(e.val);
}
return list;
}
@Override
public String toString() {
return "Entity{" + "val=" + val + '}';
}
}
}
网友评论