跳表介紹和實現

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

想想，我們

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 eprivate 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 < valuebreak;}current = next;next = current.nextNodes.get(level);}return current;}

這樣我們就寫一個一層層往下找的方法，并且封裝成find(Integer e)的形式：

		// Returns the skiplist node with greatest value <= eprivate SkipListNode find(Integer e) {return find(e, head, maxLevel);}// Returns the skiplist node with greatest value <= e// Starts at node start and levelprivate 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 <= eprivate SkipListNode find(Integer e) {return find(e, head, maxLevel);}// Returns the skiplist node with greatest value <= e// Starts at node start and levelprivate 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 eprivate 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 < valuebreak;}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) {}}