简介
SkipList(跳表)这种数据结构是由William Pugh于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList的设计初衷是作为替换平衡树的一种选择。
我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树。
但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，Skip需要更新的部分比较少，锁的东西也更少，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能。
SkipList还有一个优势就是实现简单，SkipList的实现只花了2个小时，而红黑树，我可能得2天。
时隔将近三十多年，SkipList这种数据结构仍在许多途径有用武之地，比如Redis, 还有Google的著名项目Bigtable.
特性
- 原理简单，方便实现
- 与平衡树相比空间占用会大，但时间复杂度相同，在内存如此便宜的阶段差异不大
- 区间查找方式要比平衡树更高效率。（指针大于递归）
应用实现
1.JDK
ConcurrentSkipListMap concurrentSkipListMap = new ConcurrentSkipListMap();
ConcurrentSkipListSet<String> concurrentSkipListSet = new ConcurrentSkipListSet<>();
2.Redis
Redis当中的Sorted-set这种有序的集合，正是对于跳表的改进和应用。
3.Google的著名项目Bigtable
跳表java实现
- 版本1
public class SkipList{
//结点“晋升”的概率
private static final double PROMOTE_RATE = 0.5;
private Node head,tail;
private int maxLevel;
public SkipList() {
head = new Node(Integer.MIN_VALUE);
tail = new Node(Integer.MAX_VALUE);
head.right = tail;
tail.left = head;
}
//查找结点
public Node search(int data){
Node p= findNode(data);
if(p.data == data){
System.out.println("找到结点：" + data);
return p;
}
System.out.println("未找到结点：" + data);
return null;
}
//找到值对应的前置结点
private Node findNode(int data){
Node node = head;
while(true){
while (node.right.data!=Integer.MAX_VALUE && node.right.data<=data) {
node = node.right;
}
if (node.down == null) {
break;
}
node = node.down;
}
return node;
}
//插入结点
public void insert(int data){
Node preNode= findNode(data);
//如果data相同，直接返回
if (preNode.data == data) {
return;
}
Node node=new Node(data);
appendNode(preNode, node);
int currentLevel=0;
//随机决定结点是否“晋升”
Random random = new Random();
while (random.nextDouble() < PROMOTE_RATE) {
//如果当前层已经是最高层，需要增加一层
if (currentLevel == maxLevel) {
addLevel();
}
//找到上一层的前置节点
while (preNode.up==null) {
preNode=preNode.left;
}
preNode=preNode.up;
//把“晋升”的新结点插入到上一层
Node upperNode = new Node(data);
appendNode(preNode, upperNode);
upperNode.down = node;
node.up = upperNode;
node = upperNode;
currentLevel++;
}
}
//在前置结点后面添加新结点
private void appendNode(Node preNode, Node newNode){
newNode.left=preNode;
newNode.right=preNode.right;
preNode.right.left=newNode;
preNode.right=newNode;
}
//增加一层
private void addLevel(){
maxLevel++;
Node p1=new Node(Integer.MIN_VALUE);
Node p2=new Node(Integer.MAX_VALUE);
p1.right=p2;
p2.left=p1;
p1.down=head;
head.up=p1;
p2.down=tail;
tail.up=p2;
head=p1;
tail=p2;
}
//删除结点
public boolean remove(int data){
Node removedNode = search(data);
if(removedNode == null){
return false;
}
int currentLevel=0;
while (removedNode != null){
removedNode.right.left = removedNode.left;
removedNode.left.right = removedNode.right;
//如果不是最底层，且只有无穷小和无穷大结点，删除该层
if(currentLevel != 0 && removedNode.left.data == Integer.MIN_VALUE && removedNode.right.data == Integer.MAX_VALUE){
removeLevel(removedNode.left);
}else {
currentLevel ++;
}
removedNode = removedNode.up;
}
return true;
}
//删除一层
private void removeLevel(Node leftNode){
Node rightNode = leftNode.right;
//如果删除层是最高层
if(leftNode.up == null){
leftNode.down.up = null;
rightNode.down.up = null;
}else {
leftNode.up.down = leftNode.down;
leftNode.down.up = leftNode.up;
rightNode.up.down = rightNode.down;
rightNode.down.up = rightNode.up;
}
maxLevel --;
}
//输出底层链表
public void printList() {
Node node=head;
while (node.down != null) {
node = node.down;
}
while (node.right.data != Integer.MAX_VALUE) {
System.out.print(node.right.data + " ");
node = node.right;
}
System.out.println();
}
//链表结点类
public class Node {
public int data;
//跳表结点的前后和上下都有指针
public Node up, down, left, right;
public Node(int data) {
this.data = data;
}
}
public static void main(String[] args) {
SkipList list=new SkipList();
list.insert(50);
list.insert(15);
list.insert(13);
list.insert(20);
list.insert(100);
list.insert(75);
list.insert(99);
list.insert(76);
list.insert(83);
list.insert(65);
list.printList();
list.search(50);
list.remove(50);
list.search(50);
}
}
网友评论