跳表数据结构

SkipList.java

package com.taimeitech.pv.alg;

import lombok.Data;

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

/**
 * <p>
 *     SkipList查找的规则为：
 *     <ul>
 *         <li>从顶层链表的头部开始进行遍历，比较每一个节点的元素与目标元素的大小</li>
 *         <li>如果当前元素小于目标元素，则继续遍历</li>
 *         <li>如果当前元素等于目标元素，则返回该节点</li>
 *         <li>如果当前元素大于目标元素，移动到前一个节点，然后跳跃到下一层继续遍历</li>
 *         <li>如果遍历至链表尾部，跳跃到下一层继续遍历</li>
 *     </ul>
 * </p>
 * @author Li Changwei
 * @version 2019-10-09 15:15
 */
@Data
public class SkipList<K extends Comparable<K>, V> implements Iterable<K> {

    /**
     * 随机生成器
     */
    private static final Random RANDOM_GEN = new Random();

    /**
     * 当前链表建立索引的默认概率
     */
    private static final double DEFAULT_PROBABILITY = 0.5;

    /**
     * 当前链表的头结点，key和value都为空
     */
    private Node<K, V> head;

    /**
     * 当前链表建立索引的概率
     */
    private double probability;

    /**
     * 当前链表的最底层元素的数量
     */
    private int size;

    SkipList() {
        this(DEFAULT_PROBABILITY);
    }

    private SkipList(double probability) {
        head = new Node<>(null, null, 0);
        this.probability = probability;
        size = 0;
    }

    /**
     * 根据元素的值获取指定的节点
     * @param key 需要获取的元素
     * @return 如果存在则返回指定的节点，否则返回null
     */
    public V get(K key) {
        checkKeyValid(key);
        Node<K, V> node = findNode(key);

        // 如果找到的节点等于目标元素，则返回该节点的值
        if (node.getKey().compareTo(key) == 0) {
            return node.getValue();
        }

        return null;
    }

    /**
     * 插入元素，如果元素已经存在，则覆盖原值，否则会插入新的节点
     * @param key 需要插入的元素
     * @param value 需要插入的数值
     */
    public void add(K key, V value) {
        checkKeyValid(key);

        // 如果找到key，则直接修改对应的value即可
        Node<K, V> node = findNode(key);
        if (node.getKey() != null && node.getKey().compareTo(key) == 0) {
            node.setValue(value);
            return;
        }

        // 将新的node水平插入到node之后
        Node<K, V> newNode = new Node<>(key, value, node.getLevel());
        horizontalInsert(node, newNode);

        int currentLevel = node.getLevel();
        int headLevel = head.getLevel();

        // 根据概率判断是否需要建立索引
        while (canBuildLevel()) {
            // 如果当前层级已经到达或超越顶层，则构建一个新的顶层
            if (currentLevel >= headLevel) {
                Node<K, V> newHead = new Node<>(null, null, headLevel + 1);
                verticalInsert(newHead, head);
                head = newHead;
                headLevel = head.getLevel();
            }

            // 找到node对应的上一层节点
            while (node.getUp() == null) {
                node = node.getPrevious();
            }
            node = node.getUp();

            Node<K, V> tmp = new Node<>(key, value, node.getLevel());
            horizontalInsert(node, tmp);
            verticalInsert(tmp, newNode);
            newNode = tmp;
            currentLevel++;
        }

        size++;
    }

    /**
     * 删除指定的元素
     * @param key 需要删除的元素
     * @throws NoSuchElementException 如果key不存在，则抛出元素不存在的异常
     */
    void remove(K key) {
        checkKeyValid(key);
        Node<K, V> node = findNode(key);
        if (node == null || node.getKey().compareTo(key) != 0) {
            throw new NoSuchElementException("The key is not exist !");
        }

        // 移动到最底层
        while (node.getDown() != null) {
            node = node.getDown();
        }

        Node<K, V> prev;
        Node<K, V> next;
        for (; node != null; node = node.getUp()) {
            prev = node.getPrevious();
            next = node.getNext();

            if (prev != null) {
                prev.setNext(next);
            }

            if (next != null) {
                next.setPrevious(prev);
            }
        }

        // 对顶层链表进行调整，去除无效的顶层链表
        while (head.getNext() == null && head.getDown() != null) {
            head = head.getDown();
            head.setUp(null);
        }

        size--;
    }

    boolean contains(K key) {
        return get(key) != null;
    }

    int size() {
        return size;
    }

    boolean empty() {
        return size == 0;
    }

    /**
     * 查找指定元素在链表中的位置
     * @param key 需要查找的元素
     * @return 如果key存在，则返回指定的节点，如果不存在，则返回小于该元素的最后一个节点
     */
    private Node<K, V> findNode(K key) {
        Node<K, V> node = head;
        Node<K, V> next;
        Node<K, V> down;
        K nodeKey;

        while (true) {
            // 不断遍历，直到遇到大于元素的节点
            next = node.getNext();
            while (next != null && lessThanEqual(next.getKey(), key)) {
                node = next;
                next = node.getNext();
            }

            // 当前元素等于目标元素，中断循环
            nodeKey = node.getKey();
            if (nodeKey != null && nodeKey.compareTo(key) == 0) {
                break;
            }

            // 否则，跳跃至下一层级
            down = node.getDown();
            if (down != null) {
                node = down;
            } else {
                break;
            }
        }

        return node;
    }

    /**
     * 检查元素是否合法，不能操作空值
     * @param key 需要校验的元素
     * @throws IllegalArgumentException 如果key值为空，则抛出非法参数的异常
     */
    private void checkKeyValid(K key) {
        if (key == null) {
            throw new IllegalArgumentException("Key must be not null");
        }
    }

    /**
     * 比较两个元素的大小
     * @param a 进行比较的元素
     * @param b 进行比较的元素
     * @return 如果a大于b则返回false，否则返回true
     */
    private boolean lessThanEqual(K a, K b) {
        return a.compareTo(b) <= 0;
    }

    /**
     * 根据概率决定是否建立新的索引
     * @return 如果概率小于设置的概率，则建立新索引，否则就不建索引
     */
    private boolean canBuildLevel() {
        return RANDOM_GEN.nextDouble() < probability;
    }

    /**
     * 水平方向插入y到x的后面
     * @param x 源节点
     * @param y 目标节点
     */
    private void horizontalInsert(Node<K, V> x, Node<K, V> y) {
        // x => y
        y.setPrevious(x);
        // y => x.next
        y.setNext(x.getNext());
        // x.next.previous => y
        if (x.getNext() != null) {
            x.getNext().setPrevious(y);
        }

        // x.next => y
        x.setNext(y);
    }

    /**
     * 垂直插入x到y的上面
     * @param x 源节点
     * @param y 目标节点
     */
    private void verticalInsert(Node<K, V> x, Node<K, V> y) {
        // x V y
        x.setDown(y);
        // y ^ x
        y.setUp(x);
    }

    @Override
    public Iterator<K> iterator() {
        return new SkipListIterator<>(head);
    }

    private static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {

        private Node<K, V> node;

        SkipListIterator(Node<K, V> node) {
            while (node.getDown() != null) {
                node = node.getDown();
            }

            while (node.getPrevious() != null) {
                node = node.getPrevious();
            }

            if (node.getNext() != null) {
                node = node.getNext();
            }

            this.node = node;
        }

        @Override
        public boolean hasNext() {
            return this.node != null;
        }

        @Override
        public K next() {
            K result = node.getKey();
            node = node.getNext();
            return result;
        }
    }
}

@Data
class Node<K extends Comparable<K>, V> {

    private K key;

    private V value;

    /**
     * 当前节点所在的层级
     */
    private int level;

    private Node<K, V> up;
    private Node<K, V> down;
    private Node<K, V> next;
    private Node<K, V> previous;

    Node(K key, V value, int level) {
        this.key = key;
        this.value = value;
        this.level = level;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("Node[").append("key:");

        if (key == null) {
            stringBuilder.append("None");
        } else {
            stringBuilder.append(key.toString());
        }

        stringBuilder.append(" value:");

        if (value == null) {
            stringBuilder.append("None");
        } else {
            stringBuilder.append(value.toString());
        }

        stringBuilder.append("]");

        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        SkipList<Integer, String> skipList = new SkipList<>();
        for (int i = 0; i < 10; i++) {
            skipList.add(i, String.valueOf(i));
        }
        System.out.println(skipList.size() != 10);
        System.out.println(skipList.empty());
        System.out.println(skipList.contains(11));
        System.out.println("5".equals(skipList.get(5)));
        int count = 0;
        for (Integer i : skipList) {
            System.out.println(i.equals(count++));
        }
        skipList.remove(9);
        System.out.println(skipList.size() == 9);
        System.out.println(skipList.get(9) == null);
        skipList.remove(8);
        skipList.remove(7);
        skipList.remove(6);
        skipList.remove(5);
        skipList.remove(4);
        skipList.remove(3);
        skipList.remove(2);
        skipList.remove(1);
        skipList.remove(0);
        System.out.println(skipList.size() == 0);
        System.out.println(skipList.empty());
    }

}