想慢慢的给大家自然的引入跳表。

 

想想,我们

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) { } }
 

技术
©2019-2020 Toolsou All rights reserved,
LinkedHashMap基本用法&使用实现简单缓存 dedecms网站被黑 劫持到其他网站如何解决苹果不送充填器耳机真为环保?可能还是为了赚钱吧图片格式转换错误总结-myBatis plus 分页numpy:多维数组的创建用C语言做很简单的飞机游戏Keras保存与加载模型(JSON+HDF5)福布斯中国汽车富豪榜:何小鹏第11 李想第14 李斌第15hive大量小文件处理方法总结