跳表介绍和实现

左手的ㄟ右手 2022-04-24 06:00 154阅读 0赞

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

想想，我们

1）在有序数列里搜索一个数

2）或者把一个数插入到正确的位置

都怎么做？

很简单吧

对于第一个操作，我们可以一个一个比较，在数组中我们可以二分，这样比链表快

对于第二个操作，二分也没什么用，因为找到位置还要在数组中一个一个挪位置，时间复杂度依旧是o(n)。

那我们怎么发明一个查找插入都比较快的结构呢？

![2019041808591256.png][]

可以打一些标记：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

这样我们把标记连起来，搜索一个数时先从标记开始搜起下一个标记比本身大的话就往下走，因为再往前就肯定不符合要求了。

比如我们要搜索18：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1][]

因为一次可以跨越好多数呀，自然快了一些。

既然可以打标记，我们可以改进一下，选出一些数来再打一层标记：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2][]

这样我们搜索20是这样的：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3][]

最终我们可以打好多层标记，我们从最高层开始搜索，一次可以跳过大量的数（依旧是右边大了就往下走）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4][]

比如搜索26：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 5][]

最好的情况，就是每一层的标记都减少一半，这样到了顶层往下搜索，其实和二分就没什么两样，我们最底层用链表串起来，插入一个元素也不需要移动元素，所谓跳表就完成了一大半了。

现在的问题是，我们对于一个新数，到底应该给它打几层标记呢？

（刚开始一个数都没有，所以解决了这个问题，我们一直用这个策略更新即可）

答案是。。。。。投硬币，全看脸。

我其实有点惊讶，我以为会有某些很强的和数学相关的算法，可以保证一个很好的搜索效率，是我想多了。

我们对于一个新数字，有一半概率可以打一层标记，有一半概率不可以打。

对于打了一层标记的数，我们依旧是这个方法，它有一半概率再向上打一层标记，依次循环。

所以每一层能到达的概率都少一半。

各层的节点数量竟然就可以比较好的维护在很好的效率上（最完美的就是达到了二分的效果）

再分析一下，其实对于同一个数字：

![20190418091828787.png][]![20190418091837900.png][]等等。。

其实没必要全都用指针，因为我们知道，通过指针找到一个数可比下标慢多了。

所以同一个数字的所有标记，没必要再用指针，效率低还不好维护，用一个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) {
    
    	}
    
    }

[2019041808591256.png]: /images/20220218/d29e0f0a61eb48c5941aa300f10dea0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220218/e98eeb1c91d648d5b3018c00be37c0ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 1]: /images/20220218/61e6d39b232c44698e61e6f0d2582ec5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 2]: /images/20220218/cf2577b0e833483389db3c5e299966fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 3]: /images/20220218/19fa0bdd87c24317b9de5d327b8bda0f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 4]: /images/20220218/56d5b3fe93fa49cfb3788b72e65e25a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70 5]: /images/20220218/b06779a718224d9b82ad616052156b6e.png
[20190418091828787.png]: https://img-blog.csdnimg.cn/20190418091828787.png
[20190418091837900.png]: /images/20220218/11531796d8b1440da15e1aacc2339cb0.png