大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
想慢慢的给大家自然的引入跳表。
想想，我们
1）在有序数列里搜索一个数
2）或者把一个数插入到正确的位置
都怎么做？
很简单吧
对于第一个操作，我们可以一个一个比较，在数组中我们可以二分，这样比链表快
对于第二个操作，二分也没什么用，因为找到位置还要在数组中一个一个挪位置，时间复杂度依旧是o(n)。
那我们怎么发明一个查找插入都比较快的结构呢？
可以打一些标记：
这样我们把标记连起来，搜索一个数时先从标记开始搜起下一个标记比本身大的话就往下走，因为再往前就肯定不符合要求了。
比如我们要搜索18：
因为一次可以跨越好多数呀，自然快了一些。
既然可以打标记，我们可以改进一下，选出一些数来再打一层标记：
这样我们搜索20是这样的：
最终我们可以打好多层标记，我们从最高层开始搜索，一次可以跳过大量的数（依旧是右边大了就往下走）。
比如搜索26：
最好的情况，就是每一层的标记都减少一半，这样到了顶层往下搜索，其实和二分就没什么两样，我们最底层用链表串起来，插入一个元素也不需要移动元素，所谓跳表就完成了一大半了。
现在的问题是，我们对于一个新数，到底应该给它打几层标记呢？
（刚开始一个数都没有，所以解决了这个问题，我们一直用这个策略更新即可）
答案是。。。。。投硬币，全看脸。
我其实有点惊讶，我以为会有某些很强的和数学相关的算法，可以保证一个很好的搜索效率，是我想多了。
我们对于一个新数字，有一半概率可以打一层标记，有一半概率不可以打。
对于打了一层标记的数，我们依旧是这个方法，它有一半概率再向上打一层标记，依次循环。
所以每一层能到达的概率都少一半。
各层的节点数量竟然就可以比较好的维护在很好的效率上（最完美的就是达到了二分的效果）
再分析一下，其实对于同一个数字：
等等。。
其实没必要全都用指针，因为我们知道，通过指针找到一个数可比下标慢多了。
所以同一个数字的所有标记，没必要再用指针，效率低还不好维护，用一个list保存即可。
这样，我们就设计出来一个数字的所有标记组成的结构：
public static class SkipListNode {
public Integer value;//本身的值
public ArrayList<SkipListNode> nextNodes;
//指向下一个元素的结点组成的数组，长度全看脸。
public SkipListNode(Integer value) {
this.value = value;
nextNodes = new ArrayList<SkipListNode>();
}
}将integer比较的操作封装一下：
private boolean lessThan(Integer a, Integer b) {
return a.compareTo(b) < 0;
}
private boolean equalTo(Integer a, Integer b) {
return a.compareTo(b) == 0;
}找到在本层应该往下拐的结点：
// 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
break;
}
current = next;
next = current.nextNodes.get(level);
}
return current;
}这样我们就写一个一层层往下找的方法，并且封装成find(Integer e)的形式：
// Returns the skiplist node with greatest value <= e
private SkipListNode find(Integer 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;
}刚才的方法是找到最大的小于等于目标的值，如果找到的值等于目标，跳表中就存在这个目标。否则不存在。
public boolean contains(Integer value) {
SkipListNode node = find(value);
return node != null && node.value != null && equalTo(node.value, value);
}我们现在可以实现加入一个新点了，要注意把每层的标记打好：
public void add(Integer newValue) {
if (!contains(newValue)) {
size++;
int level = 0;
while (Math.random() < PROBABILITY) {
level++;//能有几层全看脸
}
while (level > maxLevel) {//大于当前最大层数
head.nextNodes.add(null);//直接连系统最大
maxLevel++;
}
SkipListNode newNode = new SkipListNode(newValue);
SkipListNode current = head;//前一个结点，也就是说目标应插current之后
do {//每一层往下走之前就可以设置这一层的标记了，就是链表插入一个新节点
current = findNext(newValue, current, level);
newNode.nextNodes.add(0, current.nextNodes.get(level));
current.nextNodes.set(level, newNode);
} while (level-- > 0);
}
}删除也是一样的
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);
}
}作为一个容器，Iterator那是必须有的吧，里面肯定有hasNext和next吧？
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;
}
}这个跳表我们就实现完了。
现实工作中呢，我们一般不会让它到无限多层，万一有一个数它人气爆炸随机数冲到了一万层呢？
所以包括redis在内的一些跳表实现，都是规定了一个最大层数的。
别的好像也没什么了。
最后贴出所有代码。
import java.util.ArrayList;
import java.util.Iterator;
public SkipListDemo {
public static class SkipListNode {
public Integer value;
public ArrayList<SkipListNode> nextNodes;
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) {
if (!contains(newValue)) {
size++;
int level = 0;
while (Math.random() < PROBABILITY) {
level++;
}
while (level > maxLevel) {
head.nextNodes.add(null);
maxLevel++;
}
SkipListNode newNode = new SkipListNode(newValue);
SkipListNode current = head;
do {
current = findNext(newValue, current, level);
newNode.nextNodes.add(0, current.nextNodes.get(level));
current.nextNodes.set(level, newNode);
} while (level-- > 0);
}
}
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) {
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
break;
}
current = next;
next = current.nextNodes.get(level);
}
return current;
}
public int size() {
return size;
}
public boolean contains(Integer 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;
}
}
public static void main(String[] args) {
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/230866.html原文链接：https://javaforall.net
