06、数据结构和算法 - 实战:Java实现跳表

1.1 什么是跳表(Skip List)

跳表确实是一种性能比较优秀的动态数据结构,跳表(skip list) 对标的是平衡树(AVL Tree),是一种 插入/删除/搜索 都是 O(log n) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树,如 redis, leveldb 等。跳表的数据结构模型如图:

前置条件:跳表处理的是有序的链表

这个链表中,如果要搜索一个数,需要从头到尾比较每个元素是否匹配,直到找到匹配的数为止,即时间复杂度是 O(n)。同理,插入一个数并保持链表有序,需要先找到合适的插入位置,再执行插入,总计也是 O(n) 的时间。

 

添加索引,提高搜索的速度

我们新创建一个链表,它包含的元素为前一个链表的若干元素。这样在搜索一个元素时,我们先在上层链表进行搜索,当元素未找到时再到下层链表中搜索。例如搜索数字120时的路径,Head->60->90->120

 

先在上层中搜索,到达节点 90 时发现下一个节点为 170,已经大于 120,于是转到下一层搜索,找到的目标数字 120。

多级索引,提高搜索的速度

在三层链表中搜索 250,在最上层搜索时就可以直接跳过 170 之前的所有节点,因此十分高效。

 

如果有 k 层,我们需要的搜索次数会小于 ⌈n2k⌉+k ,这样当层数 k 增加到 ⌈log2n⌉ 时,搜索的时间复杂度就变成了 logn。其实这背后的原理和二叉搜索树或二分查找很类似,通过索引来跳过大量的节点,从而提高搜索效率。

1.2 JAVA实现跳表

CustomLinkedList类是一个自定义实现了单向链表。

package com.yuanxw.datastructure.chapter2;

import java.util.Random;

/**
 * 跳表(Skip List)CustomSkipList
 */
public class CustomSkipList {
   
     
    // 头节点
    private Node head;
    // 尾节点
    private Node tail;
    // 大小
    private int size;
    // 层高
    private int hight;
    // 随机数:使用long参数的所有64位作为因子值。
    private static Random random = new Random(System.currentTimeMillis());

    // 构造函数
    public CustomSkipList() {
   
     
        // 初化化==>头尾节点
        head = new Node(Integer.MIN_VALUE, NodeTypeEnum.HEAD_NODE);
        tail = new Node(Integer.MAX_VALUE, NodeTypeEnum.TAIL_NODE);

        /**
         * 建立两端关系:
         * head ---> tail
         * head <--- tail
         */
        head.rightNode = tail;
        tail.leftNode = head;
    }
    /**
     * 查询元素
     *
     * @param element
     * @return
     */
    public Node find(Integer element) {
   
     
        if (element == null) {
   
     
            throw new RuntimeException("要查询的元素值不能为空!");
        }

        Node current = this.head;
        // 只要不满足条件,则一直查找。
        while (true) {
   
     
            // 从节点最左侧向右查找
            while (current.rightNode.nodeType != NodeTypeEnum.TAIL_NODE && current.rightNode.value <= element) {
   
     
                current = current.rightNode;
            }
            // 从节点下向下查找
            if (current.downNode != null) {
   
     
                current = current.downNode;
            } else {
   
     
                break;
            }
        }
        // 返回查询结果
        return current;
    }

    /**
     * 添加元素
     *
     * @param element
     * @return
     */
    public boolean add(Integer element) {
   
     
        // 获近似值 Node
        Node nearNode = this.find(element);
        // 新建 Node
        Node newNode = new Node(element);

        /**
         * 建立【nearNode】和【newNode】之间的关系:
         * x --> y--> z
         *
         * x ---> y
         * x <--- y
         * y ---> z
         * y <--- z
         */
        newNode.leftNode = nearNode;
        newNode.rightNode = nearNode.rightNode;

        nearNode.rightNode.leftNode = newNode;
        nearNode.rightNode = newNode;
        int currentLevel = 0;
        // 生成的随机数,小于0.3,则创建索引。索引层数 + 1
        while (random.nextDouble() < 0.3) {
   
     
            // 当前等级,大于总高,需要进行升级
            if (currentLevel >= hight) {
   
     
                Node newHead = new Node(Integer.MIN_VALUE, NodeTypeEnum.HEAD_NODE);
                Node newTail = new Node(Integer.MAX_VALUE, NodeTypeEnum.TAIL_NODE);

                newHead.rightNode = newTail;
                newHead.downNode = head;
                head.upNode = newHead;

                newTail.leftNode = newHead;
                newTail.downNode = tail;
                tail.upNode = newTail;

                head = newHead;
                tail = newTail;
                hight++;
            }

            // 从近似值向左可找,上级索引有空,就可以添加索引
            while ((nearNode != null) && nearNode.upNode == null) {
   
     
                nearNode = nearNode.leftNode;
            }

            nearNode = nearNode.upNode;

            // 建立【nearNode】和【upNode】之间上下左右的关系:
            Node upNode = new Node(element);
            upNode.leftNode = nearNode;
            upNode.rightNode = nearNode.rightNode;
            upNode.downNode = newNode;

            nearNode.rightNode.leftNode = upNode;
            nearNode.rightNode = upNode;

            newNode.upNode = upNode;

            // 连续提多层,newNode增赋给upNoe变成上一级的新Node
            currentLevel++;
            newNode = upNode;
        }
        // 元素个数 + 1
        size++;
        return true;
    }

    /**
     * 删除元素
     *
     * @param element
     * @return
     */
    public boolean remove(Integer element) {
   
     
        // 获近似值 Node
        Node nearNode = this.find(element);
        if (nearNode.value != element.intValue()) {
   
     
            return true;
        }
        while (nearNode != null) {
   
     
            // 删除操作
            nearNode.leftNode.rightNode = nearNode.rightNode;
            nearNode.rightNode.leftNode = nearNode.leftNode;
            nearNode.downNode = null;

            // 删除上下两边关系
            Node upNode = nearNode.upNode;
            nearNode.upNode = null;

            nearNode = upNode;
        }
        return true;
    }

    /**
     * 清空元素
     *
     * @return
     */
    public boolean clear() {
   
     
        Node current = this.head;
        for (int i = hight; i >= 0; i--) {
   
     
            Node rightNode = current;
            while (rightNode != null && rightNode.nodeType != NodeTypeEnum.TAIL_NODE){
   
     
                Node nextNode = rightNode.rightNode;
                rightNode.rightNode = null;
                rightNode = nextNode.rightNode;
            }
            current = current.downNode;
        }
        hight = 0;
        return true;
    }

    /**
     * 是否包含
     *
     * @param element
     * @return
     */
    public boolean contains(Integer element) {
   
     
        // 返回的近似值是否等于传过来的值。
        Node nearNode = this.find(element);
        return nearNode.value == element.intValue();
    }

    /**
     * 是否为空
     *
     * @return
     */
    public boolean isEmpty() {
   
     
        return size == 0;
    }

    /**
     * 打印跳表中的数据
     */
    public void printCustomSkipList() {
   
     
        System.out.println("===============================打印跳表数据集==开始=============================");
        Node current = this.head;
        for (int i = hight; i >= 0; i--) {
   
     
            System.out.print(String.format("总索引高度为:【%s】当前高度【%s】当前数据:", hight, i));
            Node right = current.rightNode;
            while (right != null && right.nodeType == NodeTypeEnum.DATA_NODE) {
   
     
                System.out.print(String.format("-->【%s】", right.value));
                right = right.rightNode;
            }
            System.out.println("");
            current = current.downNode;
        }
        System.out.println("===============================打印跳表数据集==结束=============================");
    }

    /**
     * 获得node中value值
     *
     * @param node
     * @return
     */
    public static Integer getNodeValue(Node node) {
   
     
        if (node != null) {
   
     
            return node.value;
        }
        return null;
    }
    /**
     * 节点类型
     **/
    private enum NodeTypeEnum {
   
     
        // 节点类型:头节点
        HEAD_NODE,
        // 节点类型:数据节点
        DATA_NODE,
        // 节点类型:尾节点
        TAIL_NODE
    }

    /**
     * 定义跳表数据结构
     */
    private class Node {
   
     
        // 数据值
        private Integer value;
        // 数据类型
        private NodeTypeEnum nodeType;

        // 上下左右节点
        private Node upNode;
        private Node downNode;
        private Node leftNode;
        private Node rightNode;

        /**
         * 定义构函数
         *
         * @param value
         */
        public Node(Integer value) {
   
     
            this(value, NodeTypeEnum.DATA_NODE);
        }

        public Node(Integer value, NodeTypeEnum nodeType) {
   
     
            this.value = value;
            this.nodeType = nodeType;
        }
    }

    public static void main(String[] args) {
   
     
        CustomSkipList customSkipList = new CustomSkipList();
        System.out.println("跳表中是否为空:" + customSkipList.isEmpty());
        customSkipList.add(196);
        System.out.println("跳表中是否为空:" + customSkipList.isEmpty());
        customSkipList.add(286);
        System.out.println("=================================向跳表中添加随机数===============================");
        for (int i = 0; i < 10; i++) {
   
     
            int ram = random.nextInt(5000);
            System.out.println(String.format("向跳表中添加随机数为:【%s】", ram));
            customSkipList.add(ram);
        }
        customSkipList.printCustomSkipList();
        System.out.println("查找是否存在元素【196】:" + customSkipList.contains(196));
        Node findNode = customSkipList.find(286);
        System.out.println(String.format("查找跳表中【286】元素相邻元素:上:【%s】,下:【%s】,左:【%s】,右:【%s】",
                getNodeValue(findNode.upNode),
                getNodeValue(findNode.downNode),
                getNodeValue(findNode.leftNode),
                getNodeValue(findNode.rightNode)));
        System.out.println("remove()方法,删除跳表中【286】元素:" + customSkipList.remove(286));
        customSkipList.printCustomSkipList();
        System.out.println("clear()方法,清空跳表中所有元素:" + customSkipList.clear());
        customSkipList.printCustomSkipList();
    }
}

执行结果:

跳表中是否为空:true
跳表中是否为空:false
=================================向跳表中添加随机数===============================
向跳表中添加随机数为:【2857】
向跳表中添加随机数为:【4749】
向跳表中添加随机数为:【1991】
向跳表中添加随机数为:【3266】
向跳表中添加随机数为:【887】
向跳表中添加随机数为:【148】
向跳表中添加随机数为:【2920】
向跳表中添加随机数为:【1649】
向跳表中添加随机数为:【2475】
向跳表中添加随机数为:【4276】
===============================打印跳表数据集==开始=============================
总索引高度为:【2】当前高度【2】当前数据:-->【2475】
总索引高度为:【2】当前高度【1】当前数据:-->【148】-->【2475】-->【3266】-->【4749】
总索引高度为:【2】当前高度【0】当前数据:-->【148】-->【196】-->【286】-->【887】-->【1649】-->【1991】-->【2475】-->【2857】-->【2920】-->【3266】-->【4276】-->【4749】
===============================打印跳表数据集==结束=============================
查找是否存在元素【196】:true
查找跳表中【286】元素相邻元素:上:【null】,下:【null】,左:【196】,右:【887】
remove()方法,删除跳表中【286】元素:true
===============================打印跳表数据集==开始=============================
总索引高度为:【2】当前高度【2】当前数据:-->【2475】
总索引高度为:【2】当前高度【1】当前数据:-->【148】-->【2475】-->【3266】-->【4749】
总索引高度为:【2】当前高度【0】当前数据:-->【148】-->【196】-->【887】-->【1649】-->【1991】-->【2475】-->【2857】-->【2920】-->【3266】-->【4276】-->【4749】
===============================打印跳表数据集==结束=============================
clear()方法,清空跳表中所有元素:true
===============================打印跳表数据集==开始=============================
总索引高度为:【0】当前高度【0】当前数据:
===============================打印跳表数据集==结束=============================