我们知道二叉搜索算法能够高效的查询数据，但是需要一块连续的内存，而且增删改效率很低。
跳表，是基于链表实现的一种类似“二分”的算法。它可以快速的实现增，删，改，查操作。
我们先来看一下单向链表如何实现查找
image.png
当我们要在该单链表中查找某个数据的时候需要的时间复杂度为O(n).
怎么提高查询效率呢？如果我们给该单链表加一级索引，将会改善查询效率。
image.png
如图所示，当我们每隔一个节点就提取出来一个元素到上一层，把这一层称作索引，其中的down指针指向原始链表。
当我们查找元素16的时候，单链表需要比较10次，而加过索引的两级链表只需要比较7次。当数据量增大到一定程度的时候，效率将会有显著的提升。
如果我们再加多几级索引的话，效率将会进一步提升。这种链表加多级索引的结构，就叫做跳表。
image.png
跳表的查询时间复杂度可以达到O(logn)
代码设计
- 通过上文的阐述，我们可以把跳表种的元素设为单独的结构，记为
SkipListNode,跳表中的每一个节点都是一个一个待插入的元素，跳表中的节点个数也就是跳表的整个大小。 -
SkipListNode具有两个属性，一个就是当前节点代表的值大小value, 另外再加一个List<SkipListNode>,用于存放该层中下面第一个比他元素值大的node。 - 代码如下：
// 跳表的节点类
public static class SkipListNode {
public Integer value; // 属性一：该节点代表的值
public ArrayList<SkipListNode> nextNodes; // 属性二：该节点所的node列表
public SkipListNode(Integer value) { // 构造器
this.value = value;
nextNodes = new ArrayList<SkipListNode>();
}
}
public static class SkipListIterator implements Iterator<Integer> {
SkipList list;
SkipListNode current;
public SkipListIterator(SkipList list) {
this.list = list;
this.current = list.getHead();
}
public boolean hasNext() {
return current.nextNodes.get(0) != null;
}
public Integer next() {
current = current.nextNodes.get(0);
return current.value;
}
}
// 跳表类
public static class SkipList {
private SkipListNode head; // 填表的头节点
private int maxLevel; // 调表的最大高度
private int size; // 当前容量
private static final double PROBABILITY = 0.5;
// 构造器
public SkipList() {
size = 0;
maxLevel = 0;
head = new SkipListNode(null);
head.nextNodes.add(null);
}
// 获取头节点
public SkipListNode getHead() {
return head;
}
// 向跳表中添加元素
public void add(Integer newValue) {
// 如果当前跳表里面不包含这个newValue
if (!contains(newValue)) {
size++; //向跳表里面添加节点，size增长
int level = 0; // 随机出层数
while (Math.random() < PROBABILITY) {
level++;
}
// 如果随机出来的level层数大于最大层数maxLevel,则maxLevel增加
while (level > maxLevel) {
head.nextNodes.add(null);
maxLevel++;
}
// 创建该newValue对应的跳表
SkipListNode newNode = new SkipListNode(newValue);
SkipListNode current = head;
do {
current = findNext(newValue, current, level); // 针对每一层，找到第一个比newValue小的地方
newNode.nextNodes.add(0, current.nextNodes.get(level)); // 将当前跳表接单的第一个加上current的下一个节点，以这种方式将跳表全部连接起来
current.nextNodes.set(level, newNode); // 将current的当前层节点放上newValue的节点
} while (level-- > 0);
}
// 如果跳表中存在此value，不进行任何操作
}
public void delete(Integer deleteValue) {
if (contains(deleteValue)) {
SkipListNode deleteNode = find(deleteValue);
size--;
int level = maxLevel;
SkipListNode current = head;
do {
current = findNext(deleteNode.value, current, level);
if (deleteNode.nextNodes.size() > level) {
// 删除操作直接取消连接就可以了
current.nextNodes.set(level, deleteNode.nextNodes.get(level));
}
} while (level-- > 0);
}
}
// Returns the skiplist node with greatest value <= e
private SkipListNode find(Integer e) {
// 给定元素e，查询其所在的跳表节点
return find(e, head, maxLevel);
}
// Returns the skiplist node with greatest value <= e
// Starts at node start and level
private SkipListNode find(Integer e, SkipListNode current, int level) {
do {
current = findNext(e, current, level);
} while (level-- > 0);
return current; // 一直查到最下面一层
}
// Returns the node at a given level with highest value less than e
private SkipListNode findNext(Integer e, SkipListNode current, int level) {
// 首先获取当前层的下一个节点
SkipListNode next = current.nextNodes.get(level);
while (next != null) {
Integer value = next.value;
if (lessThan(e, value)) { // e < value 如果当前e小于下一层的节点值，则直接break，进入下一层
break;
}
current = next;
next = current.nextNodes.get(level);
}
// 如果下一层为null,直接返回给父函数find(),进入下一层
return current;
}
public int size() {
return size;
}
// 检查跳表中是否存在此value
public boolean contains(Integer value) {
// 首先根据指定的值查询value在跳表种存在的节点
SkipListNode node = find(value);
// 查到的节点值和当前的值一样，则表示已经查到了
return node != null && node.value != null && equalTo(node.value, value);
}
public Iterator<Integer> iterator() {
return new SkipListIterator(this);
}
/******************************************************************************
* Utility Functions *
******************************************************************************/
private boolean lessThan(Integer a, Integer b) {
return a.compareTo(b) < 0;
}
private boolean equalTo(Integer a, Integer b) {
return a.compareTo(b) == 0;
}
}
网友评论