Как работают списки пропуска
Skip List — это структура данных, поддерживающая быстрый поиск. Для операций вставки, поиска и удаления требуется толькоO(log n)При логарифмическом уровне временной сложности его эффективность можно сравнить даже с бинарными сбалансированными деревьями типа красно-черных деревьев, а сложность реализации намного проще, чем у красно-черных деревьев.
Основная идея Skip List состоит в том, чтобы объединить связанный список с бинарным поиском. Он поддерживает многоуровневую структуру связанного списка (обмен пространством на время). Skip List можно рассматривать как набор связанных списков с несколькими строками, каждая строка связанный список. Такой однострочный связанный список называется слоем, и каждый слой является «ускоренным переходом» к следующему слою, т. е. если оба слоя x и y содержат элемент a, то a на уровне x соединен с a на слое y (вертикальный). Самый нижний связанный список — это обычная последовательность, содержащая все узлы, и чем ближе к верхнему связанному списку, тем меньше узлов он содержит.
Поиск целевого элемента начинается с головного элемента связанного списка верхнего уровня, а затем проходит по связанному списку до тех пор, пока не будет найден узел с элементом, большим или равным целевому элементу, и если текущий элемент точно равен к цели, он возвращается напрямую. Если текущий элемент меньше целевого элемента, он переместится по вертикали на следующий уровень для продолжения поиска.Если текущий элемент больше целевого или достигает конца связанного списка, перейдите к позиции предыдущего узла, а затем опуститься вертикально на следующий уровень. Поскольку процесс поиска в списке пропуска будет постоянно переходить от одного слоя к другому, он называется списком пропуска.
У Skip List также есть очевидная особенность, заключающаяся в том, что это неточная вероятностная структура, потому что Skip List решает, следует ли избыточно копировать узлы на предыдущий уровень (а при достижении или превышении верхнего уровня ему необходимо, чтобы новый верхний уровень) опирался на вероятность функции, например, мы используем одну из простейших функций вероятности: подбрасывая монету, вероятностьPза0.5, то список пропуска, реализованный на основе этой функции вероятности, будет постоянно «подбрасывать монету», если монета выпадет орлом, узел будет скопирован на предыдущий уровень до тех пор, пока монета не перевернется.
Нетрудно понять принцип Skip List, ниже мы будем использовать Java для реализации Skip List, поддерживающего базовые потребности (поиск, вставка и удаление).
Автор этой статьиSylvanasSun(sylvanas.sun@gmail.com), впервые опубликовано вБлог SylvanasSun. Исходная ссылка: https://sylvanassun.github.io/2017/12/31/2017-12-31-skip_list/ (Для перепечатки просьба сохранить заявление в этом абзаце и сохранить гиперссылку.)
Узел и базовая реализация
Для обычного узла связанного списка он обычно содержит только один указатель на последующий узел (узел двусвязного списка содержит два указателя, один указывает на предыдущий узел, а другой указывает на следующий узел). многоуровневая структура связанного списка, наша разработка Чтобы позволить узлу иметь четыре указателя, соответствующие передней, задней, левой и правой части узла, чтобы удобно разместить главный связанный список наверху навсегда, атрибут int необходимо установить, чтобы указать уровень связанного списка.
protected static class Node<K extends Comparable<K>, V> {
private K key;
private V value;
private int level; // 该节点所处的层级
private Node<K, V> up, down, next, previous;
public Node(K key, V value, int level) {
this.key = key;
this.value = value;
this.level = level;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("Node[")
.append("key:");
if (this.key == null)
sb.append("None");
else
sb.append(this.key.toString());
sb.append(" value:");
if (this.value == null)
sb.append("None");
else
sb.append(this.value.toString());
sb.append("]");
return sb.toString();
}
// 余下都是get,set方法, 这里省略
.....
}
Далее идет базовая реализация SkipList.Для того, чтобы Key можно было сравнивать, мы оговариваем, что тип Key должен реализовывать интерфейс Comparable.В то же время для поддержки цикла ForEach этот класс также реализует интерфейс Iterable .
public class SkipList<K extends Comparable<K>, V> implements Iterable<K> {
// 一个随机数生成器
protected static final Random randomGenerator = new Random();
// 默认的概率
protected static final double DEFAULT_PROBABILITY = 0.5;
// 头节点
private Node<K, V> head;
private double probability;
// SkipList中的元素数量（不计算多个层级中的冗余元素）
private int size;
public SkipList() {
this(DEFAULT_PROBABILITY);
}
public SkipList(double probability) {
this.head = new Node<K, V>(null, null, 0);
this.probability = probability;
this.size = 0;
}
.....
}
Нам также нужно определить несколько вспомогательных методов следующим образом (все простые):
// 对key进行检查
// 因为每条链表的头节点就是一个key为null的节点，所以不允许其他节点的key也为null
protected void checkKeyValidity(K key) {
if (key == null)
throw new IllegalArgumentException("Key must be not null!");
}
// a是否小于等于b
protected boolean lessThanOrEqual(K a, K b) {
return a.compareTo(b) <= 0;
}
// 概率函数
protected boolean isBuildLevel() {
return randomGenerator.nextDouble() < probability;
}
// 将y水平插入到x的后面
protected void horizontalInsert(Node<K, V> x, Node<K, V> y) {
y.setPrevious(x);
y.setNext(x.getNext());
if (x.getNext() != null)
x.getNext().setPrevious(y);
x.setNext(y);
}
// x与y进行垂直连接
protected void verticalLink(Node<K, V> x, Node<K, V> y) {
x.setDown(y);
y.setUp(x);
}
найти
Процесс поиска узла выглядит следующим образом:
-
Он проходит от головы связанного списка верхнего уровня и сравнивает размер элемента каждого узла с размером целевого элемента.
-
Если текущий элемент меньше целевого элемента, продолжайте обход.
-
Возвращает узел, если текущий элемент равен целевому элементу.
-
Если текущий элемент больше целевого элемента, перейдите к предыдущему узлу (должен быть меньше или равен целевому элементу), а затем перейдите на следующий уровень, чтобы продолжить обход.
-
При перемещении в конец связанного списка перейдите на следующий уровень, чтобы продолжить перемещение.
protected Node<K, V> findNode(K key) {
Node<K, V> node = head;
Node<K, V> next = null;
Node<K, V> down = null;
K nodeKey = null;
while (true) {
// 不断遍历直到遇见大于目标元素的节点
next = node.getNext();
while (next != null && lessThanOrEqual(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;
}
public V get(K key) {
checkKeyValidity(key);
Node<K, V> node = findNode(key);
// 如果找到的节点并不等于目标元素，则目标元素不存在于SkipList中
if (node.getKey().compareTo(key) == 0)
return node.getValue();
else
return null;
}
вставлять
Процесс операции вставки немного сложнее, в основном в операции копирования узлов на предыдущий слой и построения нового слоя.
public void add(K key, V value) {
checkKeyValidity(key);
// 直接找到key，然后修改对应的value即可
Node<K, V> node = findNode(key);
if (node.getKey() != null && node.getKey().compareTo(key) == 0) {
node.setValue(value);
return;
}
// 将newNode水平插入到node之后
Node<K, V> newNode = new Node<K, V>(key, value, node.getLevel());
horizontalInsert(node, newNode);
int currentLevel = node.getLevel();
int headLevel = head.getLevel();
while (isBuildLevel()) {
// 如果当前层级已经到达或超越顶层
// 那么需要构建一个新的顶层
if (currentLevel >= headLevel) {
Node<K, V> newHead = new Node<K, V>(null, null, headLevel + 1);
verticalLink(newHead, head);
head = newHead;
headLevel = head.getLevel();
}
// 找到node对应的上一层节点
while (node.getUp() == null) {
node = node.getPrevious();
}
node = node.getUp();
// 将newNode复制到上一层
Node<K, V> tmp = new Node<K, V>(key, value, node.getLevel());
horizontalInsert(node, tmp);
verticalLink(tmp, newNode);
newNode = tmp;
currentLevel++;
}
size++;
}
Удалить
Для удаления узла необходимо найти положение узла (положение в самом нижнем связанном списке), а затем удалить избыточную репликацию узла в каждой строке снизу вверх.
public void remove(K key) {
checkKeyValidity(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 = null;
Node<K, V> next = null;
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--;
}
итератор
Поскольку наш SkipList реализует интерфейс Iterable, нам также необходимо реализовать итератор. Для повторения списка пропуска просто найдите самый нижний связанный список и перейдите к его первому узлу, а затем пройдите по нему.
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node<K, V> node = head;
// 移动到最底层
while (node.getDown() != null)
node = node.getDown();
while (node.getPrevious() != null)
node = node.getPrevious();
// 第一个节点是头部节点，没有任何意义，所以需要移动到后一个节点
if (node.getNext() != null)
node = node.getNext();
// 遍历
while (node != null) {
sb.append(node.toString()).append("\n");
node = node.getNext();
}
return sb.toString();
}
@Override
public Iterator<K> iterator() {
return new SkipListIterator<K, V>(head);
}
protected static class SkipListIterator<K extends Comparable<K>, V> implements Iterator<K> {
private Node<K, V> node;
public 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;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
Полный кодовый адрес SkipList, реализованный в этой статье.