java是否有跳过列表实现

Question

我ConcurrentSkipListSet在Java Collection Framework中找到了,它使用跳过列表进行备份.但Java中是否有跳过列表？一个集合在我的用例中不起作用.我需要一个支持重复的可索引列表.

Answer 1

这个答案迟了3年但我希望它对那些想要从这一刻开始的Java跳过列表的人有用:)

此解决方案允许您按照要求进行重复.我大致遵循这里的指南http://igoro.com/archive/skip-lists-are-fascinating,所以复杂性与此类似,除了删除成本O(nlogn) - 因为我没有使用双重链接节点,我想这样做会把删除到O(logn).

代码包括:接口,实现接口的跳过列表,以及节点类.它也是通用的.

您可以调整参数LEVELS以获得性能,但请记住时空权衡.

import java.util.Random;

interface SkippableList<T extends Comparable<? super T>> {
    int LEVELS = 5;

    boolean delete(T target);
    void print();
    void insert(T data);
    SkipNode<T> search(T data);
}

public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {

    public static void main(String[] args) {
        SkipList<Integer> sl = new SkipList<>();
        int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
        for (int i : data) {
            sl.insert(i);
        }

        sl.print();
        sl.search(4);

        sl.delete(9);
        sl.print();

        sl.insert(69);
        sl.print();
        sl.search(69);
    }

    private final SkipNode<T> head = new SkipNode<>(null);
    private final Random rand = new Random();

    @Override
    public void insert(T data) {
        SkipNode<T> SkipNode = new SkipNode<>(data);
        for (int i = 0; i < LEVELS; i++) {
            if (rand.nextInt((int) Math.pow(2, i)) == 0) { //insert with prob = 1/(2^i)
                insert(SkipNode, i);
            }
        }
    }

    @Override
    public boolean delete(T target) {
        System.out.println("Deleting " + target.toString());
        SkipNode<T> victim = search(target, false);
        if (victim == null) return false;
        victim.data = null;

        for (int i = 0; i < LEVELS; i++) {
            head.refreshAfterDelete(i);
        }

        System.out.println();
        return true;
    }

    @Override
    public SkipNode<T> search(T data) {
        return search(data, true);
    }

    @Override
    public void print() {
        for (int i = 0; i < LEVELS; i++) {
            head.print(i);
        }

        System.out.println();
    }

    private void insert(SkipNode<T> SkipNode, int level) {
        head.insert(SkipNode, level);
    }

    private SkipNode<T> search(T data, boolean print) {
        SkipNode<T> result = null;
        for (int i = LEVELS-1; i >= 0; i--) {
            if ((result = head.search(data, i, print)) != null) {
                if (print) {
                    System.out.println("Found " + data.toString() + " at level " + i + ", so stoppped" );
                    System.out.println();
                }

                break;
            }
        }

        return result;
    }

}

class SkipNode<N extends Comparable<? super N>> {

    N data;
    @SuppressWarnings("unchecked")
    SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];

    SkipNode(N data) {
        this.data = data;
    }

    void refreshAfterDelete(int level) {
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.getNext(level) != null) {
            if (current.getNext(level).data == null) {
                SkipNode<N> successor = current.getNext(level).getNext(level);
                current.setNext(successor, level);
                return;
            }

            current = current.getNext(level);
        }
    }

    void setNext(SkipNode<N> next, int level) {
        this.next[level] = next;
    }

    SkipNode<N> getNext(int level) {
        return this.next[level];
    }

    SkipNode<N> search(N data, int level, boolean print) {
        if (print) {
            System.out.print("Searching for: " + data + " at ");
            print(level);
        }

        SkipNode<N> result = null;
        SkipNode<N> current = this.getNext(level);
        while (current != null && current.data.compareTo(data) < 1) {
            if (current.data.equals(data)) {
                result = current;
                break;
            }

            current = current.getNext(level);
        }

        return result;
    }

    void insert(SkipNode<N> SkipNode, int level) {
        SkipNode<N> current = this.getNext(level);
        if (current == null) {
            this.setNext(SkipNode, level);
            return;
        }

        if (SkipNode.data.compareTo(current.data) < 1) {
            this.setNext(SkipNode, level);
            SkipNode.setNext(current, level);
            return;
        }

        while (current.getNext(level) != null && current.data.compareTo(SkipNode.data) < 1 && 
                current.getNext(level).data.compareTo(SkipNode.data) < 1) {

            current = current.getNext(level);
        }

        SkipNode<N> successor = current.getNext(level);
        current.setNext(SkipNode, level);
        SkipNode.setNext(successor, level);
    }

    void print(int level) {
        System.out.print("level " + level + ": [");
        int length = 0;
        SkipNode<N> current = this.getNext(level);
        while (current != null) {
            length++;
            System.out.print(current.data.toString() + " ");
            current = current.getNext(level);
        }

        System.out.println("], length: " + length);
    }

}

Answer 2

修复了@PoweredByRice 提供的实现中的错误。当删除的节点是第一个节点时，它会抛出 NPE。其他更新包括重命名变量名称和反向打印跳过列表的顺序。

import java.util.Random;

interface SkippableList<T extends Comparable<? super T>> {

  int LEVELS = 5;

  boolean delete(T target);
  void print();
  void insert(T data);
  SkipNode<T> search(T data);
}

class SkipNode<N extends Comparable<? super N>> {

  N data;
  @SuppressWarnings("unchecked")
  SkipNode<N>[] next = (SkipNode<N>[]) new SkipNode[SkippableList.LEVELS];

  SkipNode(N data) {
    this.data = data;
  }

  void refreshAfterDelete(int level) {
    SkipNode<N> current = this;
    while (current != null && current.getNext(level) != null) {
      if (current.getNext(level).data == null) {
        SkipNode<N> successor = current.getNext(level).getNext(level);
        current.setNext(successor, level);
        return;
      }

      current = current.getNext(level);
    }
  }

  void setNext(SkipNode<N> next, int level) {
    this.next[level] = next;
  }

  SkipNode<N> getNext(int level) {
    return this.next[level];
  }

  SkipNode<N> search(N data, int level, boolean print) {
    if (print) {
      System.out.print("Searching for: " + data + " at ");
      print(level);
    }

    SkipNode<N> result = null;
    SkipNode<N> current = this.getNext(level);
    while (current != null && current.data.compareTo(data) < 1) {
      if (current.data.equals(data)) {
        result = current;
        break;
      }

      current = current.getNext(level);
    }

    return result;
  }

  void insert(SkipNode<N> skipNode, int level) {
    SkipNode<N> current = this.getNext(level);
    if (current == null) {
      this.setNext(skipNode, level);
      return;
    }

    if (skipNode.data.compareTo(current.data) < 1) {
      this.setNext(skipNode, level);
      skipNode.setNext(current, level);
      return;
    }

    while (current.getNext(level) != null && current.data.compareTo(skipNode.data) < 1 &&
      current.getNext(level).data.compareTo(skipNode.data) < 1) {

      current = current.getNext(level);
    }

    SkipNode<N> successor = current.getNext(level);
    current.setNext(skipNode, level);
    skipNode.setNext(successor, level);
  }

  void print(int level) {
    System.out.print("level " + level + ": [ ");
    int length = 0;
    SkipNode<N> current = this.getNext(level);
    while (current != null) {
      length++;
      System.out.print(current.data + " ");
      current = current.getNext(level);
    }

    System.out.println("], length: " + length);
  }

}

public class SkipList<T extends Comparable<? super T>> implements SkippableList<T> {

  private final SkipNode<T> head = new SkipNode<>(null);
  private final Random rand = new Random();

  @Override
  public void insert(T data) {
    SkipNode<T> skipNode = new SkipNode<>(data);
    for (int i = 0; i < LEVELS; i++) {
      if (rand.nextInt((int) Math.pow(2, i)) == 0) {
        //insert with prob = 1/(2^i)
        insert(skipNode, i);
      }
    }
  }

  @Override
  public boolean delete(T target) {
    System.out.println("Deleting " + target);
    SkipNode<T> victim = search(target, true);
    if (victim == null) return false;
    victim.data = null;

    for (int i = 0; i < LEVELS; i++) {
      head.refreshAfterDelete(i);
    }

    System.out.println("deleted...");
    return true;
  }

  @Override
  public SkipNode<T> search(T data) {
    return search(data, true);
  }

  @Override
  public void print() {
    for (int i = LEVELS-1; i >= 0 ; i--) {
      head.print(i);
    }
    System.out.println();
  }

  private void insert(SkipNode<T> SkipNode, int level) {
    head.insert(SkipNode, level);
  }

  private SkipNode<T> search(T data, boolean print) {
    SkipNode<T> result = null;
    for (int i = LEVELS-1; i >= 0; i--) {
      if ((result = head.search(data, i, print)) != null) {
        if (print) {
          System.out.println("Found " + data.toString() + " at level " + i + ", so stopped" );
          System.out.println();
        }
        break;
      }
    }

    return result;
  }

  public static void main(String[] args) {
    SkipList<Integer> sl = new SkipList<>();
    int[] data = {4,2,7,0,9,1,3,7,3,4,5,6,0,2,8};
    for (int i : data) {
      sl.insert(i);
    }

    sl.print();
    sl.search(4);

    sl.delete(4);

    System.out.println("Inserting 10");
    sl.insert(10);
    sl.print();
    sl.search(10);
  }

}

Answer 3

由于您提到了一个既可索引（我假设您想要快速检索）又需要允许重复的列表，我建议您使用带有 LinkedList 或 ArrayList 的自定义集。

您需要有一个基本 Set（例如 HashSet），并不断向其中添加值。如果您遇到重复项，则该 Set 的值应指向 List。因此，您将拥有快速检索，当然您将以伪集合的方式存储您的对象。

这将为您提供良好的检索效率。理想情况下，如果您的密钥不重复，您将实现 O(1) 作为检索速度。