Java实现跳跃表

目录

• 概要
• 运行性能
• 源码
• 致谢

---

概要

本文提供可复用的跳跃表实现（下称 SkipList），所用语言为 Java，使用场景为单机单线程。

跳跃表的特点为：数据有序、不可重复。查询的时间复杂度为 O(logN)。

读者可以从 源码 直接复制使用，或者从 gitee 下载使用。

返回目录

---

运行性能

由下表可知，SkipList 的插入性能是 TreeSet 的 56%~70%。

TreeSet 是 Java Collection 集合中的一员，该数据结构的特点是：数据有序、不可重复，查询的时间复杂度为 O(logN)。

为了测试 SkipList 的运行性能，将其与 TreeSet 进行比较，统计了两者连续插入随机数，所耗费的时间。读者可以从 性能测试 获取测试代码。

数据量分别为 10万条、100万条、1000万条，数据提前准备，不计入时间。

每个数据量下，重复测试 10 次，得到 10 个运行时间，去除最大值和最小值后，取平均值。

数据量/万条	10	100	1000
SkipList 平均运行时间/毫秒	58.7	1389.0	21726.5
TreeSet 平均运行时间/毫秒	34.0	783.3	15336.5
运行时间比 SkipList / TreeSet	1.73	1.77	1.42
性能比（运行时间比值的倒数）	58%	56%	70%

返回目录

---

源码

跳跃表抽象类

声明需要实现的方法。

import java.util.Collection;

public abstract class AbstractSkipList {

    public abstract int size();

    public abstract boolean isEmpty();

    public abstract boolean contains(E e);

    public abstract boolean add(E e);

    public abstract boolean remove(E e);

    public abstract void clear();

    public abstract boolean addAll(Collection c);

    public abstract E first();

    public abstract E last();

}

跳跃表实现类

实现跳跃表。

import java.util.Collection;
import java.util.Comparator;
import java.util.Random;

public class SkipList extends AbstractSkipList {

    private int topLevel = 0;

    private int size = 0;

    private Node head;

    private Random random;

    private final Comparator comparator;

    public SkipList() {
        this(null);
    }

    public SkipList(Comparator c) {
        head = new Node<>(null, 3);
        this.comparator = c;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean contains(E e) {
        return find(e) != null;
    }

    @Override
    public boolean add(E e) {
        if (e == null) {
            throw new NullPointerException();
        }

        int level = randomLevel();
        Node newNode;
        if (level > topLevel) {
            topLevel++;
            resize();
            newNode = new Node<>(e, topLevel);
        } else {
            newNode = new Node<>(e, level);
        }
        Node[] preNodes = getPreNodes(e, newNode.getLevel());
        for (int i = 0; i < preNodes.length; i++) {
            Node pre = preNodes[i];
            newNode.setNextNode(i, pre.getNextNode(i));
            pre.setNextNode(i, newNode);
        }
        size++;
        return true;
    }

    @Override
    public boolean remove(E e) {
        Node del = find(e);
        if (del == null) {
            return false;
        }
        Node[] preNodes = getPreNodes(e, del.getLevel());
        for (int i = 0; i < preNodes.length; i++) {
            Node pre = preNodes[i];
            pre.setNextNode(i, del.getNextNode(i));
            del.setNextNode(i, null);
        }
        while (topLevel > 0) {
            if (head.getNextNode(topLevel) == null) {
                topLevel--;
            } else {
                break;
            }
        }
        size--;
        return true;
    }

    @Override
    public void clear() {
        for (int i = 0; i <= topLevel; i++) {
            head.setNextNode(i, null);
        }
        topLevel = 0;
        size = 0;
    }

    @Override
    public boolean addAll(Collection c) {
        boolean modified = false;
        for (E e : c) {
            if (add(e)) modified = true;
        }
        return modified;
    }

    @Override
    public E first() {
        if (head.getNextNode(0) != null) {
            return head.getNextNode(0).getValue();
        }
        return null;
    }

    @Override
    public E last() {
        Node temp = head;
        for (int i = topLevel; i >= 0; i--) {
            while (temp.getNextNode(i) != null) {
                temp = temp.getNextNode(i);
            }
        }
        return temp.getValue();
    }

    @Override
    public String toString() {
        if (isEmpty()) return "[]";

        StringBuilder b = new StringBuilder();
        b.append('[');

        Node temp = head;
        while (temp.getNextNode(0) != null) {
            b.append(temp.getNextNode(0).getValue());
            temp = temp.getNextNode(0);
            if (temp.getNextNode(0) == null) {
                b.append(']');
                break;
            }
            b.append(", ");
        }
        return b.toString();
    }

    private int randomLevel() {
        if (random == null) {
            random = new Random();
        }
        int level = 0;
        int times = topLevel + 1;
        while (times-- > 0) {
            if (!random.nextBoolean()) {
                break;
            }
            level++;
        }
        return level;
    }

    private Node[] getPreNodes(E e, int level) {
        if (e == null) {
            return null;
        }
        Node[] preNodes = new Node[level + 1];
        Node temp = head;
        Comparator cpr = comparator;
        Node next;
        if (cpr != null) {
            for (int i = topLevel; i >= 0; i--) {
                while ((next = temp.getNextNode(i)) != null && cpr.compare(next.getValue(), e) < 0) {
                    temp = next;
                }
                if (i <= level) {
                    preNodes[i] = temp;
                }
            }
        } else {
            for (int i = topLevel; i >= 0; i--) {
                while ((next = temp.getNextNode(i)) != null && ((Comparable) next.getValue()).compareTo(e) < 0) {
                    temp = next;
                }
                if (i <= level) {
                    preNodes[i] = temp;
                }
            }
        }
        return preNodes;
    }

    private void resize() {
        if (topLevel > head.getLevel()) {
            Node newHead = new Node(null, topLevel);
            for (int i = 0; i <= head.getLevel(); i++) {
                newHead.setNextNode(i, head.getNextNode(i));
                head.setNextNode(i, null);
            }
            head = newHead;
        }
    }

    private Node find(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        Node temp = head;
        for (int i = topLevel; i >= 0; i--) {
            if (comparator != null) {
                while (temp.getNextNode(i) != null) {
                    int c = comparator.compare(temp.getNextNode(i).getValue(), e);
                    if (c < 0) {
                        temp = temp.getNextNode(i);
                    } else if (c == 0) {
                        return temp.getNextNode(i);
                    } else {
                        break;
                    }
                }
            } else {
                while (temp.getNextNode(i) != null) {
                    Comparable v = (Comparable) temp.getNextNode(i).getValue();
                    int c = v.compareTo(e);
                    if (c < 0) {
                        temp = temp.getNextNode(i);
                    } else if (c == 0) {
                        return temp.getNextNode(i);
                    } else {
                        break;
                    }
                }
            }
        }
        return null;
    }

    static final class Node {
        E value;
        int level;
        Node[] nextNode;

        public Node(E value, int level) {
            this.value = value;
            this.level = level;
            this.nextNode = new Node[level + 1];
        }

        public E getValue() {
            return value;
        }

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

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }

        public Node getNextNode(int level) {
            return this.nextNode[level];
        }

        public void setNextNode(int level, Node node) {
            this.nextNode[level] = node;
        }

    }

}

性能测试

import org.junit.Test;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

public class performanceTest {

    public Random random = new Random();
    public final int size = 1000_0000;
    public final int time = 10;

    @Test
    public void SkipListTest() {
        long[] res = new long[time];
        long begin, end;
        for (int i = 0; i < time; i++) {
            int[] nums = getRandomArray(size);
            SkipList skipList = new SkipList<>();
            begin = System.currentTimeMillis();
            for (Integer num : nums) {
                skipList.add(num);
            }
            end = System.currentTimeMillis();
            res[i] = end - begin;
        }
        Arrays.sort(res);
        long sum = 0;
        for (int i = 1; i < time - 1; i++) {
            sum += res[i];
        }
        double average = sum / 6.0;
        System.out.println("max: " + res[res.length -1]);
        System.out.println("min: " + res[0]);
        System.out.println("average: " + average);
        System.out.println(Arrays.toString(res));
    }

    @Test
    public void TreeSetTest() {
        long[] res = new long[time];
        long begin, end;
        for (int i = 0; i < time; i++) {
            int[] nums = getRandomArray(size);
            TreeSet treeSet = new TreeSet<>();
            begin = System.currentTimeMillis();
            for (Integer num : nums) {
                treeSet.add(num);
            }
            end = System.currentTimeMillis();
            res[i] = end - begin;
        }
        Arrays.sort(res);
        long sum = 0;
        for (int i = 1; i < time - 1; i++) {
            sum += res[i];
        }
        double average = sum / 6.0;
        System.out.println("max: " + res[res.length -1]);
        System.out.println("min: " + res[0]);
        System.out.println("average: " + average);
        System.out.println(Arrays.toString(res));
    }

    public int[] getRandomArray(int size) {
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = random.nextInt();
        }
        return nums;
    }

    public List getRandomList(int size) {
        List list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(random.nextInt());
        }
        return list;
    }
}

返回目录

单元测试

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.TreeSet;

public class SkipListImplTest{

    public final Random random = new Random();

    @Test
    public void sizeTest() {
        int size = 10000;
        List nums = getRandomList(size);

        SkipList skipList = new SkipList<>();
        TreeSet treeSet = new TreeSet<>();
        skipList.addAll(nums);
        treeSet.addAll(nums);
        Assert.assertEquals(treeSet.size(), skipList.size());
    }

    @Test
    public void isEmptyTest() {
        SkipList skipList = new SkipList<>();
        Assert.assertTrue(skipList.isEmpty());
        skipList.add(1);
        Assert.assertFalse(skipList.isEmpty());
        skipList.remove(1);
        Assert.assertTrue(skipList.isEmpty());
    }

    @Test
    public void containsTest() {
        SkipList skipList = new SkipList<>();
        int[] nums = new int[]{-99, -56, 1, 78, 265, Integer.MAX_VALUE};
        for (Integer num : nums) {
            skipList.add(num);
        }
        Assert.assertFalse(skipList.contains(Integer.MIN_VALUE));
        Assert.assertFalse(skipList.contains(-987867));
        Assert.assertFalse(skipList.contains(-98));
        Assert.assertFalse(skipList.contains(0));
        Assert.assertFalse(skipList.contains(264));
        Assert.assertFalse(skipList.contains(578676786));

        Assert.assertTrue(skipList.contains(-99));
        Assert.assertTrue(skipList.contains(-56));
        Assert.assertTrue(skipList.contains(1));
        Assert.assertTrue(skipList.contains(78));
        Assert.assertTrue(skipList.contains(265));
        Assert.assertTrue(skipList.contains(Integer.MAX_VALUE));
    }

    @Test
    public void addTest() {
        int size = 10000;
        int[] nums = getRandomArray(size);
        SkipList skipList = new SkipList<>();
        TreeSet set = new TreeSet<>();
        for (int num : nums) {
            skipList.add(num);
            set.add(num);
        }
        Assert.assertEquals(set.toString(), skipList.toString());
    }

    @Test
    public void removeTest() {
        int size = 10000;
        List nums = getRandomList(size);
        SkipList skipList = new SkipList<>();
        skipList.addAll(nums);
        for (Integer num : nums) {
            skipList.remove(num);
        }
        Assert.assertTrue(skipList.isEmpty());
    }

    @Test
    public void clearTest() {
        int size = 10000;
        List nums = getRandomList(size);
        SkipList skipList = new SkipList<>();
        skipList.addAll(nums);
        Assert.assertFalse(skipList.isEmpty());
        skipList.clear();
        Assert.assertTrue(skipList.isEmpty());
    }

    @Test
    public void addAllTest() {
        int size = 10000;
        List nums = getRandomList(size);
        SkipList skipList = new SkipList<>();
        TreeSet set = new TreeSet<>();
        skipList.addAll(nums);
        set.addAll(nums);
        Assert.assertEquals(set.toString(), skipList.toString());
    }

    @Test
    public void firstTest() {
        int size = 1000;
        List nums = getRandomList(size);
        SkipList skipList = new SkipList<>();
        TreeSet set = new TreeSet<>();
        skipList.addAll(nums);
        set.addAll(nums);
        Assert.assertEquals(set.first(), skipList.first());
    }

    @Test
    public void lastTest() {
        int size = 1000;
        List nums = getRandomList(size);
        SkipList skipList = new SkipList<>();
        TreeSet set = new TreeSet<>();
        skipList.addAll(nums);
        set.addAll(nums);
        Assert.assertEquals(set.last(), skipList.last());
    }

    public int[] getRandomArray(int size) {
        int[] nums = new int[size];
        for (int i = 0; i < size; i++) {
            nums[i] = random.nextInt();
        }
        return nums;
    }

    public List getRandomList(int size) {
        List list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(random.nextInt());
        }
        return list;
    }
}

返回目录

---

致谢

感谢 ExRoc 的指导与反馈，本文格式参考了 《C++ 实现BigInteger 类》。

返回目录

---