跳表概述

跳表是由William Pugh于1990年发明，他在论文中给出了跳表的描述：

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

与单向链表不同，每一个结点不单单只包含指向下一个结点的指针，可能包含很多个指向后续结点的指针，这样就可以跳过一些不必要的结点，从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针，后续节点个数是通过一个随机函数生成器得到，这样子就构成了一个跳跃表。

随机生成的跳跃表如下图所示：

这基本上就是跳表的核心思想，其实也是一种通过空间来换取时间的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。目前开源软件 Redis 和 LevelDB 都有用到它。

其增删改查的时间复杂度为O(log n).

跳表的Java简易实现

节点

如果一个节点存在k个向前的指针的话，那么称该节点是k层的节点。

一个跳表的MaxLevel为跳表中所有节点中最大的层数。

public static class SkipListNode {
   	public Integer value;	public ArrayList
   
     nextNodes;	public SkipListNode(Integer value) {
   		this.value = value;		nextNodes = new ArrayList
    
     ();	}}

跳表数据类型

public static class SkipList {
   	private SkipListNode head;	private int maxLevel;	private int size;	private static final double PROBABILITY = 0.5;}

PROBABILITY表示生成下一层的概率

初始化

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;	}}

查找操作

以查找19为例，先找到6，再找到25，19比25小，在6和25之间；再找到9，再找到17，再找到25,19比25小，在17和25节点之间，17再下一个即为19。

public static class SkipList {
   	private SkipListNode head;	private int maxLevel;	private int size;	private static final double PROBABILITY = 0.5;        // 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    // 关键方法：找到给定level中value小于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;	}        private boolean lessThan(Integer a, Integer b) {
   		return a.compareTo(b) < 0;	}	private boolean equalTo(Integer a, Integer b) {
   		return a.compareTo(b) == 0;	}}

插入操作

由于跳表数据结构整体上是有序的，所以在插入时，需要首先查找到合适的位置，然后就是修改指针（和链表中操作类似），然后更新跳表的level变量。

public static class SkipList {
   	private SkipListNode head;	private int maxLevel;	private int size;	private static final double PROBABILITY = 0.5;        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 boolean contains(Integer value) {
   		SkipListNode node = find(value);		return node != null && node.value != null && equalTo(node.value, value);	}}

删除操作

删除操作类似于插入操作，包含如下3步：查找到需要删除的结点、删除结点、调整指针。

public static class SkipList {
   	private SkipListNode head;	private int maxLevel;	private int size;	private static final double PROBABILITY = 0.5;        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);		}	}}

遍历

遍历第0层的节点即可。

public static class SkipList {
   	private SkipListNode head;	private int maxLevel;	private int size;	private static final double PROBABILITY = 0.5;        // Inner Class    public static class SkipListIterator implements Iterator
   
     {
   		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 Iterator
    
      iterator() {
   		return new SkipListIterator(this);	}}

全部代码

import java.util.ArrayList;import java.util.Iterator;public class SkipList_Simple {
   	public static class SkipListNode {
   		public Integer value;		public ArrayList
   
     nextNodes;		public SkipListNode(Integer value) {
   			this.value = value;			nextNodes = new ArrayList
    
     ();		}	}	public static class SkipListIterator implements Iterator
     
       {
   		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
      
        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) {
   	}}

ConcurrentSkipListMap

ConcurrentSkipListMap是JDK1.6以后提供的一个并发的SkipList。

从上面的构造我们可以看到，Index节点包含了Node节点，除此之外，Index还有两个指针，一个指向同一个layer的下一个节点right，一个指向下一层layer的节点down。采用自旋+CAS的方式进行增删改查。

转载地址：http://atgmi.baihongyu.com/

你可能感兴趣的文章