一,概述

跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，目前在Redis和LeveIDB中都有用到

二,代码实现以及图解

2.1声明结点结构

2.1.1代码

//跳表的结点
    public static class SkipListNode{
        public Integer value;
        public ArrayList<SkipListNode> nextNodes;
        
        public SkipListNode(Integer value)
        {
            this.value=value;
            nextNodes=new ArrayList<SkipListNode>();
        }
    }

2.1.2声明图解 图片.png

2.2 声明跳表结构

2.2.1 代码

    public static class SkipList{
        //头结点(相当于链表,直到了头结点,就获得了整个结构)
        private SkipListNode head;
        //最大高度
        private int maxLevel;
        //当前结点的个数
        private int size;
        //根据这个常量获取新结点的level
        private static final double PROBABILITY = 0.5;

2.2.2 图解 图片.png

2.2.3 初始化

public SkipList()
        {
            size=0;
            maxLevel=0;
            head=new SkipListNode(null);//最左端
            head.nextNodes.add(null);//没有一个指向
        }

2.3 功能

2.3.1 添加

public void add(Integer newValue)
        {
            //添加
            //如果不包含该值,就添加
            //包含就不添加
            if(!contains(newValue))
            {
                size++;
                int level=0;
                //如果随机数大于0.5就跳出
                //所有层数越高,概率越小
                while(Math.random()<PROBABILITY)
                {
                    level++;
                }
                //如果得到的层数超过了maxLevel
                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);
            }
        }

图片.png

1,contains(newValue)

查看整个结构中是否包括添加的值

2,findNext(newValue,current,level)

查询小于newvalue同时离newValue最近的值,此例中为5

3,newNode.nextNodes.add(0,current.nextNodes.get(level));

从高层向底层遍历,所有每次最新的current.nextNodes.get(level)都要放在nextNodes的最头部

2.3.2 删除

public void delete(Integer deleteValue)
        {
            if(contains(deleteValue))
            {       //通过find函数查找到要删除的结点
                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);
            }
        }

重点代码

if(deleteNode.nextNodes.size()>level) {

current.nextNodes.set(level,

deleteNode.nextNodes.get(level));

}

图片.png

2.3.3 查询

查找到距离e最近的Node

private SkipListNode findNext(Integer e,SkipListNode current,int level)
        {
            SkipListNode next=current.nextNodes.get(level);
            while(next!=null)
            {
                Integer value =next.value;
                // e<value
                if(lessThan(e,value))
                {
                    break;
                }
                current=next;
                next=current.nextNodes.get(level);
            }
            return current;
        }

   private SkipListNode find(Integer e)
        {
            return find(e,head,maxLevel);
        }
        
        private SkipListNode find(Integer e,SkipListNode current,int level)
        {
            do{
                current=findNext(e,current,level);
            }while(level-->0);
            return current;
        }

2.3.4 其他函数

public boolean contains(Integer value)
        {
            SkipListNode node = find(value);
            return node != null && node.value != null && equalTo(node.value, value);
        }
        
        private boolean lessThan(Integer a,Integer b)
        {
            return a.compareTo(b)<0;
        }
        
        private boolean equalTo(Integer a,Integer b)
        {
            return a.compareTo(b)==0;
        }
    }