欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

跳跃表的原理及Java实现

程序员文章站 2022-04-02 18:13:06
...

原理参考:SkipList跳表

这里我使用Java实现其原理:

首先是SkipListNode的定义:

SkipListNode.java

package skiplist;

/**
 * Created by zhuxinquan on 17-3-11.
 */
public class SkipListNode implements Comparable {

    private int value;
    private SkipListNode next = null;
    private SkipListNode downNext = null;

    @Override
    protected void finalize() throws Throwable {
        super.finalize();
        System.out.printf("123");
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public SkipListNode getNext() {
        return next;
    }

    public void setNext(SkipListNode next) {
        this.next = next;
    }

    public SkipListNode getDownNext() {
        return downNext;
    }

    public void setDownNext(SkipListNode downNext) {
        this.downNext = downNext;
    }

    @Override
    public int compareTo(Object o) {
        return this.value > ((SkipListNode)o).value ? 1 : -1;
    }
}

然后是跳跃表的具体操作,操作过程在开始部分处的链接已明了,这里直接模拟实现:

SkipList.java

package skiplist;

import java.util.Random;

/**
 * Created by zhuxinquan on 17-3-11.
 */
public class SkipList {

    public int level = 0;
    public SkipListNode top = null;

    public SkipList() {
        this(4);
    }

    //跳跃表的初始化
    public SkipList(int level) {
        this.level = level;
        SkipListNode skipListNode = null;
        SkipListNode temp = top;
        SkipListNode tempDown = null;
        SkipListNode tempNextDown = null;
        int tempLevel = level;
        while(tempLevel -- != 0){
            skipListNode = createNode(Integer.MIN_VALUE);
            temp = skipListNode;
            skipListNode = createNode(Integer.MAX_VALUE);
            temp.setNext(skipListNode);
            temp.setDownNext(tempDown);
            temp.getNext().setDownNext(tempNextDown);
            tempDown = temp;
            tempNextDown = temp.getNext();
        }
        top = temp;
    }

    //随机产生数k,k层下的都需要将值插入
    public int randomLevel(){
        int k = 1;
        while(new Random().nextInt()%2 == 0){
            k ++;
        }
        return k > level ? level : k;
    }

    //查找
    public SkipListNode find(int value){
        SkipListNode node = top;
        while(true){
            while(node.getNext().getValue() < value){
                node = node.getNext();
            }
            if(node.getDownNext() == null){
                //返回要查找的节点的前一个节点
                return node;
            }
            node = node.getDownNext();
        }
    }

    //删除一个节点
    public boolean delete(int value){
        int tempLevel = level;
        SkipListNode skipListNode = top;
        SkipListNode temp = skipListNode;
        boolean flag = false;
        while(tempLevel -- != 0){
            while(temp.getNext().getValue() < value){
                temp = temp.getNext();
            }
            if(temp.getNext().getValue() == value){
                temp.setNext(temp.getNext().getNext());
                flag = true;
            }
            temp = skipListNode.getDownNext();
        }
        return flag;
    }

    //插入一个节点
    public void insert(int value){
        SkipListNode skipListNode = null;
        int k = randomLevel();
        SkipListNode temp = top;
        int tempLevel = level;
        SkipListNode tempNode = null;
        //当在第n行插入后,在第n - 1行插入时需要将第n行backTempNode的DownNext域指向第n - 1的域
        SkipListNode backTempNode = null;
        int flag = 1;
        while(tempLevel-- != k){
            temp = temp.getDownNext();
        }

        tempLevel++;
        tempNode = temp;
        //小于k层的都需要进行插入
        while(tempLevel-- != 0){
            //在第k层寻找要插入的位置
            while(tempNode.getNext().getValue() < value){
                tempNode = tempNode.getNext();
            }
            skipListNode = createNode(value);
            //如果是顶层
            if(flag != 1){
                backTempNode.setDownNext(skipListNode);
            }
            backTempNode = skipListNode;
            skipListNode.setNext(tempNode.getNext());
            tempNode.setNext(skipListNode);
            flag = 0;
            tempNode = tempNode.getDownNext();
        }
    }

    //创建一个节点
    private SkipListNode createNode(int value){
        SkipListNode node =  new SkipListNode();
        node.setValue(value);
        return node;
    }
}

然后再定义一个测试类如下:

SkipListTest.java

package skiplist;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * Created by zhuxinquan on 17-3-11.
 */
public class SkipListTest {
    public static void main(String[] args) {
        long startTime = 0;
        long endTime = 0;
        SkipList skipList = new SkipList(12);
        Set<Integer> set = new HashSet();
        List<Integer> list = new LinkedList<>();

        //测试跳跃表性能
        startTime = System.currentTimeMillis();
        for (int i = 1; i < 100000; i++) {
            skipList.insert(i);
        }
        endTime = System.currentTimeMillis();
        System.out.printf("createSkipList:%d\n", endTime - startTime);
        startTime = System.currentTimeMillis();
        System.out.printf("find(555):%d\n", skipList.find(55555).getNext().getValue());
        endTime = System.currentTimeMillis();
        System.out.printf("skipListFindTime:%d\n\n", endTime - startTime);

        //测试LinkedList性能
        startTime = System.currentTimeMillis();
        for (int i = 1; i < 100000; i++) {
            list.add(i);
        }
        endTime = System.currentTimeMillis();
        System.out.printf("createList:%d\n", endTime - startTime);
        startTime = System.currentTimeMillis();
        System.out.printf("find(555):%b\n", list.contains(55555));
        endTime = System.currentTimeMillis();
        System.out.printf("linkedListFindTime:%d\n\n", endTime - startTime);

        //测试hashSet性能
        startTime = System.currentTimeMillis();
        for (int i = 1; i < 100000; i++) {
            set.add(i);
        }
        endTime = System.currentTimeMillis();
        System.out.printf("createSet:%d\n", endTime - startTime);
        startTime = System.currentTimeMillis();
        System.out.printf("find(555):%b\n", set.contains(55555));
        endTime = System.currentTimeMillis();
        System.out.printf("hashSetFindTime:%d\n", endTime - startTime);
    }
}

 

上述测试类对100000条数据进行插入和查找,分别统计使用跳跃表、LinkedList、HashSet时插入和查找的时间,结果如下:

跳跃表的原理及Java实现

下面是50000整数中查找38555这个值消耗的时间:

跳跃表的原理及Java实现


上图很明显的可以看出,跳跃表的查找效率还是很高的(在数据量高的时候),同时,跳跃表也肯定消耗了不少的额外空间。

上述代码只是个人根据自己的理解简单实现了跳跃表的原理,其中自然有不少瑕疵,也有好多可优化的地方,比如可以将每层的起点节点的引用保存在一个一维数组当中、跳表中存储键值对这样的数据结构等等

相关标签: java 跳跃表