跳表（跳跃表）（SkipList）的java实现-蒲公英云

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

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

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

跳跃表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 +
                    '}';
        }
    }
}