Поиск в WeChat »bigsai"Подпишитесь на этого интересного программиста Ваши три последовательных лайка должны быть очень важны для меня! Статьи включены вМой Github bigsai-алгоритмприветственная звезда
предисловие
Таблица пропуска — это структура данных, которую часто задают в интервью. Она используется во многих промежуточных слоях и языках. Мы знакомы с таблицей пропуска Redis. И во многих сценах интервью вас могут попросить, а изредка попросят попробовать от руки (таблица пропуска может быть написана от руки, а красно-черное дерево невозможно) Нет, пусть все восстанавливают сцену:
Но не паникуйте, не бойтесь встретить интервьюера как грибную голову, потому что вы читаете эту статью (горжусь 😏), не смущайтесь, как панда.
Для структуры данных или алгоритма количество людей, которые слышали название, понимают основные принципы, четко выполняют процесс и могут писать от руки, показывает тенденцию к тряске. Потому что основные принципы многих структур данных и алгоритмов могут быть простыми, но чтобы знать процесс выполнения, вам нужно подумать об этом своим мозгом, но если вы можете это написать, вы должны спроектировать и реализовать его шаг за шагом. Написание может занять много времени, и может быть много материала для поиска.
Эта статья знакомит с таблицей пропуска в начале, а последняя часть подробно знакомит с дизайном и реализацией таблицы пропуска.Чтобы понять таблицу пропуска, этой статьи действительно достаточно.
Быстрый взгляд на таблицу пропуска
Таблица скипов (сокращенно от skip table) была разработана американскими учеными-компьютерщиками.Изобретен Уильямом Пью в 1989 году.. В своей статье «Списки пропуска: вероятностная альтернатива сбалансированным деревьям» он подробно представил структуру данных списков пропуска и такие операции, как вставка и удаление.
Список пропуска (SkipList, полное название списка пропуска) — это структура данных, используемая для быстрого поиска и поиска упорядоченных последовательностей элементов.Список пропуска — это рандомизированная структура данных, которая по сути представляет собой упорядоченный связанный список, способный выполнять бинарный поиск . Список пропуска добавляет многоуровневый индекс к исходному упорядоченному связанному списку и использует индекс для быстрого поиска. Пропуск таблиц может повысить не только производительность поиска, но и производительность операций вставки и удаления. Его производительность сравнима с красно-черным деревом и деревом AVL, но принцип таблицы пропуска очень прост, а реализация намного проще, чем у красно-черного дерева.
Здесь вы можете увидеть некоторые ключевые слова: связанный список (упорядоченный связанный список), индекс, бинарный поиск. Предположительно, у вас в голове уже сложилось приблизительное представление, но вы можете еще не знать, сколько стоит этот «прыгающий связанный список», и у вас может даже возникнуть небольшое сомнение: какое отношение он имеет к следованию за машиной? Вы узнаете достаточно скоро ниже!
Оглядываясь назад на связанные списки, мы знаем, что связанные списки и последовательные списки (массивы) обычно любят и убивают друг друга, появляясь парами, каждый со своими преимуществами и недостатками. Преимущество связанного списка заключается в более эффективной вставке и удалении.Проблема в том, что запрос очень медленный! Каждый запрос представляет собой операцию сложности O(n), а связанный список оценивается как рассерженный и готовый плакать😢.
Это связанный список с головным узлом (головной узел эквивалентен фиксированной записи и не хранит значимых значений), каждый поиск требует перечисления, что довольно медленно, Можем ли мы немного оптимизировать его, чтобы сделать его Как насчет небольшой прыжок? Ответ — да, мы знаем множество алгоритмов и структур данных.поменять пространство на время, мы добавляем слой индекса сверху, чтобы некоторые узлы могли быть непосредственно расположены в верхнем слое, так что время запроса связанного списка сокращается почти вдвое.Хотя сам связанный список не радует, он откладывает его плачущее лицо.
Таким образом, когда запрашивается узел, он сначала быстро находит диапазон, в котором находится узел из предыдущего слоя. Если конкретный диапазон находится ниже, стоимость поиска очень мала. Конечно, нисходящий индекс будет добавлен в структуру таблицы (указатель), используемый для поиска базового узла. Средняя скорость поиска в среднем составляет O(n/2). Но когда количество узлов велико, он все равно очень медленный. Мы все знаем, что бинарный поиск можно каждый раз сокращать вдвое, чтобы сжать диапазон поиска.Было бы идеально, если бы упорядоченный связанный список мог так прыгать. ВерноСтруктура данных, которая позволяет связанному списку иметь почти бинарную эффективность поиска., принцип по-прежнему заключается в том, чтобы добавить несколько слоев индексов к вышеперечисленным для оптимизации скорости поиска.
Как видно из приведенного выше рисунка, производительность поиска в упорядоченном связанном списке по такой структуре данных может быть почти в два раза выше. Он заключается в том, чтобы поддерживать на нем так много уровней индексов.Сначала найти последнюю позицию в индексе самого высокого уровня, которая меньше текущего элемента поиска, а затем перейти к индексу следующего уровня, чтобы продолжить поиск, пока он не перейдет к нижний слой. В это время он очень близок к поисковой позиции элемента (если элемент поиска существует). Поскольку несколько элементов могут быть пропущены одновременно в соответствии с индексом, скорость поиска с пропуском также выше.
Для идеального списка с пропусками количество индексных узлов в каждом верхнем слое равно 1/2 следующего слоя.Тогда, если n узлов увеличить количество узлов (1/2+1/4+…) Вышеизложенное имеет небольшое представление о том, что такое таблица пропуска, поэтому здесь я расскажу о процессе добавления, удаления, изменения и проверки таблицы пропуска. В процессе реализации этой таблицы скипов, для облегчения операции мы устанавливаем ключ головного узла (head) таблицы скипов на минимальное значение int (он должен удовлетворять маленькому левому и правому большому для облегчения сравнение). Для настроек каждого узла установите его в класс SkipNode.Чтобы новички не путали следующий вниз или вправо, напрямую установите указатели вправо и вниз. Структура и инициализация таблицы пропуска также очень важны, ее основными параметрами и методами инициализации являются: Во многих случаях связанный список может быть связан и таким образом, только в качестве критерия упорядочения используется определенный элемент или ключ. Так что вполне возможно, что внутри связанного списка есть какие-то значения. Однако модификация и запрос на самом деле являются операцией по поиску номера ключа (ключа). И процесс поиска тоже очень простой, установите временный узел team=head. когдакоманда не нулеваяПроцесс примерно такой: (1) Начиная с командного узла,Если ключ текущего узла равен ключу запроса, затем вернитесь к текущему узлу (если это операция модификации, то измените значение до конца). (2) Если ключи не равны, иправая сторона нулевая, то доказательство может быть только вниз (результат может появиться в нижнем правом направлении), в это время team=team.down (3) Если ключи не равны и правая часть не равна нулю, иКлюч правого узла меньше запрашиваемого ключа. Тогда это значит, что этот же уровень может уйти и вправо, на этот раз team=team.right (4) (В противном случае), если ключи не равны и правая часть не равна нулю, иКлюч правого узла больше запрашиваемого ключа. Тогда это означает, что если и есть результат, то он находится между этим индексом и следующим индексом, в это время team=team.down. В конце концов, согласно этому шагу будет возвращен правильный узел или нуль (описание не найдено). Например, на приведенном выше рисунке для запроса 12 узлов первый шаг — начать с головы и обнаружить, что правая сторона не пуста и 7
И этот блок кода тоже очень прост: Операция удаления немного сложнее, чем запрос, но проще, чем вставка. Удаление требует изменения структуры связанного списка, поэтому необходимо разобраться со связью между узлами. Для операций удаления необходимо иметь в виду следующее: (1) Удаление текущего узла связано с узлами до и после этого узла. (2) После удаления узла текущего слоя следует также удалить узел ключа в следующем слое, пока не будет удален нижний слой. Анализируйте по этим двум пунктам: если текущий узел найден,Как найти предыдущий узел этого?? Это невозможно пройти заново! Некоторые используют указатели в четырех направлениях (вверх, вниз, влево и вправо), чтобы найти левый узел. да, но вотособый уход, не судите напрямую и не управляйте узлом, сначала найдитеУзел слева от удаляемого узла. Удаление может быть завершено через этот узел, а затем этот узел напрямую спускается вниз, чтобы найти левый узел, подлежащий удалению, в следующем слое. Установите временный узел team=head,когда команда не нулеваяКонкретный процесс цикла: (1) ЕслиПравая часть команды равна нулю, затем team=team.down (причина, по которой я осмеливаюсь судить напрямую, заключается в том, что с левой стороны есть головной узел, не беспокойтесь об особых случаях) (2) если правая часть команды не равна нулю, иКлюч справа равен удаляемому ключу, затем сначала удалите узел, а затем команду team=team.down, чтобы удалить нижний узел. (3) если правая часть команды не равна нулю, иПравый ключ меньше удаляемого ключа, тогда правильная команда team=team.right. (4) если правая часть команды не равна нулю, иКлюч справа больше, чем ключ, который нужно удалить, затем team переходит к team=team.down и продолжает поиск и удаление узлов на нижнем уровне. Например, удалите 10 узлов на приведенном выше рисунке.Во-первых, team=head начинается с team, а 7
Код, реализующий операцию удаления, выглядит следующим образом: Операции вставки наиболее сложны в реализации и требуют наибольшего внимания. Оглядываясь назад на запрос, нет необходимости перемещать индекс; просмотр удаления, если есть удаление в каждом индексе. Но вставка отличается,При вставке необходимо учитывать, следует ли вставлять индекс, вставлять несколько слоевИ другие вопросы. Из-за необходимости вставки и удаления мы, конечно, не можем поддерживать полностью идеальную структуру индекса, потому что это слишком дорого. но мы используемрандомизироватьметод, чтобы определить, следует ли вставлять индекс на верхний уровень. То есть, если генерируется случайное число [0-1], индекс будет вставлен вверх, если он меньше 0,5.После вставки случайное число будет использоваться снова, чтобы определить, следует ли вставлять индекс вверх. Если повезет, значение может быть многоуровневым индексом, если не повезло, вставляется только нижний слой (который вставляется на 100%). Однако индекс не может не ограничивать высоту, мы обычно устанавливаем максимальное значение индекса, если оно больше этого значения, и не будем продолжать добавлять индекс вверх. Разбираем, как это сделать шаг за шагом, процесс (1) Сначала найдите способ через вышеуказанный поисклевый узел для вставки. Если вы вставляете, нижний слой должен быть вставлен, поэтому вставьте узел через связанный список (необходимо учитывать, является ли он конечным узлом) (2) После вставки этого слоя необходимо рассмотреть, вставлен ли предыдущий слой.Во-первых, определить текущий уровень индекса.Если он больше максимального значения, остановить его (например, он достиг самого высокого уровня индекса) . В противном случае установите случайное число с вероятностью 1/2, чтобы вставить слой индекса вверх (поскольку в идеальном состоянии индексный узел создается для каждых 2). (3) Продолжайте операцию (2) до тех пор, пока вероятность не выйдет или число индексных слоев не превысит максимальный индексный слой. существуетВставить вверх, есть на самом деле очень важные детали для рассмотрения. во-первыхКак найти узел для вставки в верхний слой? У каждого способа реализации это может быть разным, если есть указатели, указывающие влево и вверх, то можно найти узел, который нужно вставить в верхний слой влево и вверх, а если есть только указатели вправо и вниз , мы также можемГениально записывайте нисходящие узлы во время процесса запроса. Поскольку узел, который необходимо вставить, находится в обратном порядке отброшенных узлов, и нижний слой не является исключением (поскольку нет соответствующего значения, оно упадет до нуля, чтобы завершить цикл). здесь я используюкучаЭта структура данных сохраняется, конечно, также можно использовать список. На рисунке ниже представлена схема вставки. Второй, если слой является текущиминдекс верхнего уровня,необходимостьПродолжайте наращивать индексТо, что должно быть сделано? Во-первых, таблица пропуска должна сначала не иметь индекса, а затем потихоньку добавлять узлы, чтобы были одноуровневые и двухуровневые индексы, но если добавляемый этим узлом индекс пробивает текущий верхний уровень, что делать? В этот моменттребует вниманияТеперь нужно изменить заголовок таблицы пропуска, создать новый узел ListNode в качестве нового заголовка, указать его вниз на старый заголовок и добавить этот головной узел в стек (то есть этот узел используется как узел будет вставлен в следующий раз), просто Например, если вышеуказанным 9 узлам посчастливится построить слой узлов, он будет таким. При вставке верхнего слоя обратите внимание, что все узлы должны быть заново созданы (скопированы), кроме правого, указывающего вниз, нельзя забывать, что нижний указывает на предыдущий узел, а временный узел можно использовать как узел-предшественник. Если количество слоев превышает текущий верхний слой, необходимо изменить головной узел (вход). Более подробная информация об этой части объяснена в комментариях к коду.Подробный код: Для вышеизложенного полный анализ таблицы пропуска завершен.Конечно, вы можете увидеть реализацию различных разновидностей таблиц пропуска, а некоторые используют массив для выражения отношения между верхним и нижним уровнями, но эта статья только определяет два направления вправо и вниз.Связанный список является более чистым объяснением списка пропуска. Для таблицы пропуска и ее конкурента: красно-черного дерева, почему упорядоченный набор Redis (zset) использует таблицу пропуска? Поскольку таблица пропуска имеет ту же эффективность, что и красно-черное дерево, за исключением обслуживания поиска и вставки.Это связанный список и может определять интервал диапазона, и проблема интервала может быть не так удобна для запроса по дереву. в то время как JDKПропустить таблицы ConcurrentSkipListSet и ConcurrentSkipListMap.Если вам интересно, вы также можете проверить исходный код. Для обучения очень важен полный код, здесь я выложу полный код и заберу его, если он вам нужен. Проверьте это, и вы обнаружите, что таблица пропуска по-прежнему совершенна (хвастайтесь собой). Оригинальность непростая, бигсай просит друзей помочь с двумя вещами: Ставьте лайки, смотрите, делитесь и поддерживайте, вы должны быть источником моего творения. Поиск в WeChat »bigsai», обратите внимание на мой официальный аккаунт, я не только вышлю вам бесплатные электронные книги, но и впервые поделюсь знаниями и технологиями на официальном аккаунте. Вы также можете втянуть вас в группу перфокарт, чтобы вместе пробить LeetCode. Увидимся в следующий раз!Добавляйте, удаляйте, изменяйте и проверяйте таблицу пропуска
class SkipNode<T>
{
int key;
T value;
SkipNode right,down;//右下个方向的指针
public SkipNode (int key,T value) {
this.key=key;
this.value=value;
}
}
public class SkipList <T> {
SkipNode headNode;//头节点，入口
int highLevel;//当前跳表索引层数
Random random;// 用于投掷硬币
final int MAX_LEVEL = 32;//最大的层
SkipList(){
random=new Random();
headNode=new SkipNode(Integer.MIN_VALUE,null);
highLevel=0;
}
//其他方法
}
операция запроса
public SkipNode search(int key) {
SkipNode team=headNode;
while (team!=null) {
if(team.key==key)
{
return team;
}
else if(team.right==null)//右侧没有了，只能下降
{
team=team.down;
}
else if(team.right.key>key)//需要下降去寻找
{
team=team.down;
}
else //右侧比较小向右
{
team=team.right;
}
}
return null;
}
удалить операцию
public void delete(int key)//删除不需要考虑层数
{
SkipNode team=headNode;
while (team!=null) {
if (team.right == null) {//右侧没有了，说明这一层找到，没有只能下降
team=team.down;
}
else if(team.right.key==key)//找到节点，右侧即为待删除节点
{
team.right=team.right.right;//删除右侧节点
team=team.down;//向下继续查找删除
}
else if(team.right.key>key)//右侧已经不可能了，向下
{
team=team.down;
}
else { //节点还在右侧
team=team.right;
}
}
}
операция вставки
public void add(SkipNode node)
{
int key=node.key;
SkipNode findNode=search(key);
if(findNode!=null)//如果存在这个key的节点
{
findNode.value=node.value;
return;
}
Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点，这些节点可能在右侧插入节点
SkipNode team=headNode;//查找待插入的节点 找到最底层的哪个节点。
while (team!=null) {//进行查找操作
if(team.right==null)//右侧没有了，只能下降
{
stack.add(team);//将曾经向下的节点记录一下
team=team.down;
}
else if(team.right.key>key)//需要下降去寻找
{
stack.add(team);//将曾经向下的节点记录一下
team=team.down;
}
else //向右
{
team=team.right;
}
}
int level=1;//当前层数，从第一层添加(第一层必须添加，先添加再判断)
SkipNode downNode=null;//保持前驱节点(即down的指向，初始为null)
while (!stack.isEmpty()) {
//在该层插入node
team=stack.pop();//抛出待插入的左侧节点
SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
nodeTeam.down=downNode;//处理竖方向
downNode=nodeTeam;//标记新的节点下次使用
if(team.right==null) {//右侧为null 说明插入在末尾
team.right=nodeTeam;
}
//水平方向处理
else {//右侧还有节点，插入在两者之间
nodeTeam.right=team.right;
team.right=nodeTeam;
}
//考虑是否需要向上
if(level>MAX_LEVEL)//已经到达最高级的节点啦
break;
double num=random.nextDouble();//[0-1]随机数
if(num>0.5)//运气不好结束
break;
level++;
if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
{
highLevel=level;
//需要创建一个新的节点
SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
highHeadNode.down=headNode;
headNode=highHeadNode;//改变head
stack.add(headNode);//下次抛出head
}
}
}
Суммировать
import java.util.Random;
import java.util.Stack;
class SkipNode<T>
{
int key;
T value;
SkipNode right,down;//左右上下四个方向的指针
public SkipNode (int key,T value) {
this.key=key;
this.value=value;
}
}
public class SkipList <T> {
SkipNode headNode;//头节点，入口
int highLevel;//层数
Random random;// 用于投掷硬币
final int MAX_LEVEL = 32;//最大的层
SkipList(){
random=new Random();
headNode=new SkipNode(Integer.MIN_VALUE,null);
highLevel=0;
}
public SkipNode search(int key) {
SkipNode team=headNode;
while (team!=null) {
if(team.key==key)
{
return team;
}
else if(team.right==null)//右侧没有了，只能下降
{
team=team.down;
}
else if(team.right.key>key)//需要下降去寻找
{
team=team.down;
}
else //右侧比较小向右
{
team=team.right;
}
}
return null;
}
public void delete(int key)//删除不需要考虑层数
{
SkipNode team=headNode;
while (team!=null) {
if (team.right == null) {//右侧没有了，说明这一层找到，没有只能下降
team=team.down;
}
else if(team.right.key==key)//找到节点，右侧即为待删除节点
{
team.right=team.right.right;//删除右侧节点
team=team.down;//向下继续查找删除
}
else if(team.right.key>key)//右侧已经不可能了，向下
{
team=team.down;
}
else { //节点还在右侧
team=team.right;
}
}
}
public void add(SkipNode node)
{
int key=node.key;
SkipNode findNode=search(key);
if(findNode!=null)//如果存在这个key的节点
{
findNode.value=node.value;
return;
}
Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点，这些节点可能在右侧插入节点
SkipNode team=headNode;//查找待插入的节点 找到最底层的哪个节点。
while (team!=null) {//进行查找操作
if(team.right==null)//右侧没有了，只能下降
{
stack.add(team);//将曾经向下的节点记录一下
team=team.down;
}
else if(team.right.key>key)//需要下降去寻找
{
stack.add(team);//将曾经向下的节点记录一下
team=team.down;
}
else //向右
{
team=team.right;
}
}
int level=1;//当前层数，从第一层添加(第一层必须添加，先添加再判断)
SkipNode downNode=null;//保持前驱节点(即down的指向，初始为null)
while (!stack.isEmpty()) {
//在该层插入node
team=stack.pop();//抛出待插入的左侧节点
SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建
nodeTeam.down=downNode;//处理竖方向
downNode=nodeTeam;//标记新的节点下次使用
if(team.right==null) {//右侧为null 说明插入在末尾
team.right=nodeTeam;
}
//水平方向处理
else {//右侧还有节点，插入在两者之间
nodeTeam.right=team.right;
team.right=nodeTeam;
}
//考虑是否需要向上
if(level>MAX_LEVEL)//已经到达最高级的节点啦
break;
double num=random.nextDouble();//[0-1]随机数
if(num>0.5)//运气不好结束
break;
level++;
if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点
{
highLevel=level;
//需要创建一个新的节点
SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null);
highHeadNode.down=headNode;
headNode=highHeadNode;//改变head
stack.add(headNode);//下次抛出head
}
}
}
public void printList() {
SkipNode teamNode=headNode;
int index=1;
SkipNode last=teamNode;
while (last.down!=null){
last=last.down;
}
while (teamNode!=null) {
SkipNode enumNode=teamNode.right;
SkipNode enumLast=last.right;
System.out.printf("%-8s","head->");
while (enumLast!=null&&enumNode!=null) {
if(enumLast.key==enumNode.key)
{
System.out.printf("%-5s",enumLast.key+"->");
enumLast=enumLast.right;
enumNode=enumNode.right;
}
else{
enumLast=enumLast.right;
System.out.printf("%-5s","");
}
}
teamNode=teamNode.down;
index++;
System.out.println();
}
}
public static void main(String[] args) {
SkipList<Integer>list=new SkipList<Integer>();
for(int i=1;i<20;i++)
{
list.add(new SkipNode(i,666));
}
list.printList();
list.delete(4);
list.delete(8);
list.printList();
}
}