跳表（跳跃表）（SkipList）的java实现

小咪咪 2023-02-10 03:46 97阅读 0赞

跳表的详细数据结构解释见如下blog：

## **[跳跃表Skip List的原理和实现(Java)][Skip List_Java]** ##

**参照上述博文的实现如下：**

package com.foraixh.datastructure;
    
    import java.util.Random;
    
    /**
     * @author myvina@qq.com
     * @date 2020/5/19  19:28
     * @usage 跳跃表的简单实现
     */
    
    public class SkipList<V> {
        /**
         * 跳跃表的头指针
         */
        private Entry<V> head;
        /**
         * 跳跃表的尾指针
         */
        private Entry<V> tail;
        /**
         * 存储的数据量
         */
        private int size;
        /**
         * 跳跃表的高度
         */
        private int height;
        /**
         * 决定是否能进入到上一层
         */
        private Random coinToss;
    
        private final Entry<V> MIN_ENTRY = new Entry<>(Integer.MIN_VALUE, null);
        private final Entry<V> MAX_ENTRY = new Entry<>(Integer.MAX_VALUE, null);
    
        public SkipList() {
            size = 0;
            height = 0;
            coinToss = new Random();
            
            head = MIN_ENTRY;
            tail = MAX_ENTRY;
    
            MIN_ENTRY.right = MAX_ENTRY;
            MAX_ENTRY.left = MIN_ENTRY;
        }
    
        public static void main(String[] args) {
            SkipList<String> skipList = new SkipList<>();
    
            for (int i = 0; i < 10; i++) {
                skipList.put(i, "值：" + i);
            }
            skipList.show();
        }
    
        private void show() {
            Entry<V> p = head;
            while (p != null) {
                Entry<V> q = p;
    
                System.out.print(p);
                while (p.right != null) {
                    System.out.print("->" + p.right);
                    p = p.right;
                }
                System.out.println();
    
                p = q.down;
            }
        }
    
        private Entry<V> findEntry(Integer key) {
            Entry<V> p = head;
    
            while (true) {
                // 从左向右查找，直到右节点的key值大于要查找的key值
                while (!p.right.getScore().equals(MAX_ENTRY.getScore()) && p.right.getScore().compareTo(key) <= 0) {
                    p = p.right;
                }
    
                // 如果有更低层的节点，则向低层移动
                if (p.down != null) {
                    p = p.down;
                } else {
                    break;
                }
            }
    
            // 返回p 注意这里p的key值是小于等于传入key的值的（p.key <= key）
            return p;
        }
    
        public V get(Integer key) {
            Entry<V> p = findEntry(key);
            if (p.getScore().equals(key)) {
                return p.value;
            }
            return null;
        }
    
        public void put(Integer score, V value) {
            Entry<V> q = new Entry<>(score, value);
    
            // 第一步：查找适合插入的节点
            Entry<V> p = findEntry(score);
    
            // 第二部：如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
            if (p.getScore().equals(score)) {
                p.setValue(value);
                return;
            }
    
            // 第三步：如果跳跃表中不存在含有key值的节点，则进行新增操作
            insertEntryToRight(p, q);
    
            // 第四步：再使用随机数决定是否要向更高level攀升
            // 插入的新节点一定是在最底层
            int level = 0;
            // 如果新增的节点q的左右节点已经是边界了，则不允许新增一层
            while ((Integer.MIN_VALUE != q.left.getScore() || Integer.MAX_VALUE != q.right.getScore()) && coinToss.nextBoolean()) {
                // 如果新元素的级别已经达到跳跃表的最大高度，则新建空白层
                if (level >= height) {
                    addEmptyLevel();
                }
    
                while (p.up == null) {
                    p = p.left;
                }
                p = p.up;
    
                // 新增和q指针指向的节点含有相同key值的节点对象
                // 这里需要注意的是除底层节点之外的节点对象是不需要value值的
                Entry<V> z = new Entry<>(score, null);
    
                insertEntryToRight(p, z);
    
                z.down = q;
                q.up = z;
    
                q = z;
    
                level++;
            }
    
            size++;
        }
    
        public V remove(Integer key) {
            Entry<V> p = findEntry(key);
    
            if (!p.getScore().equals(key)) {
                return null;
            }
    
            V oldValue = p.getValue();
            Entry<V> q;
            while (p != null) {
                q = p.up;
                p.left.right = p.right;
                p.right.left = p.left;
                p = q;
            }
    
            return oldValue;
        }
    
        private void addEmptyLevel() {
            Entry<V> p = new Entry<>(Integer.MIN_VALUE, null);
            Entry<V> q = new Entry<>(Integer.MAX_VALUE, null);
    
            p.right = q;
            p.down = head;
    
            q.left = p;
            q.down = tail;
    
            head.up = p;
    
            tail.up = q;
    
            head = p;
            tail = q;
    
            height++;
        }
    
        /**
         * 在节点p的右边插入节点q
         */
        private void insertEntryToRight(Entry<V> p, Entry<V> q) {
            q.left = p;
            q.right = p.right;
            p.right.left = q;
            p.right = q;
        }
    
        public static class Entry<V> {
    
            /**
             * 根据score进行排序
             */
            private Integer score;
            private V value;
    
            /**
             * 前后左右的指针
             */
            Entry<V> up;
            Entry<V> down;
            Entry<V> left;
            Entry<V> right;
    
            public Entry() {
    
            }
    
            public Entry(Integer score, V value) {
                this.score = score;
                this.value = value;
            }
    
            public Integer getScore() {
                return score;
            }
    
            public void setScore(Integer score) {
                this.score = score;
            }
    
            public V getValue() {
                return value;
            }
    
            public void setValue(V value) {
                this.value = value;
            }
    
            @Override
            public String toString() {
                return "Entry{" +
                        "score=" + score +
                        ", value=" + value +
                        '}';
            }
        }
    }

[Skip List_Java]: https://blog.csdn.net/DERRANTCM/article/details/79063312