[Приквел Redis] Напишите стратегию LRU самостоятельно | Поймайте хвост времени

задняя часть
[Приквел Redis] Напишите стратегию LRU самостоятельно | Поймайте хвост времени

Это 23-й день моего участия в Gengwen Challenge.Подробности о мероприятии:Обновить вызов

1. Описание темы

146. Механизм кэширования LRU

Используя свои знания о структурах данных, спроектируйте и внедритеLRU(Наименее недавно использовавшийся) механизм кэширования. выполнить LRUCacheсвоего рода:

LRUCache(int capacity)Инициализировать с положительным целым числом в качестве емкости емкостиLRUтайник int get(int key) Возвращает значение ключа, если ключ существует в кэше, иначе -1. void put(int key, int value) Если ключ уже существует, измените его значение данных, если ключ не существует, вставьте набор "ключ-значение". Когда емкость кэша достигает верхнего предела, он должен удалить самые старые неиспользуемые значения данных перед записью новых данных, чтобы освободить место для новых значений данных.

Для продвинутых: можете ли вы выполнить обе операции с временной сложностью O(1)?

image-20210611091820720

2. Анализ мыслей

первая мысль

  • Когда я впервые увидел этот вопрос, я не думал об этом и думал, что буду использовать очередь, потому что очередь FIFO может удалить данные в конце, но если вы тщательно обдумаете этот вопрос, его нужно устранить.Наименее недавно использованныйДанные, если только последние данные, то очереди легко реализовать. В сочетании с частотой использования это связано с частым перемещением данных. Ясно, что очередь не может быть завершена.
  • Итак, существуют ли последовательно добавляемые данные, которые перемещают данные вперед к одному концу каждый раз, когда они извлекаются? Ответ - да!LinkedHashMap
  • LinkedHashMapНезнакомые друзья могут просто понять это какHashMap. На рисунке ниже показаноHashMapструктура хранения

image-20210611091747182

  • Для вышеперечисленных элементов я сделал анимацию, чтобы продемонстрировать весь процесс! ! !

动画演示

  • иLinkedHashMapЭто просто дополнительный связанный список для соединения элементов в нем.

  • Вот почемуLinkedHashMapхранятся по порядку. ноLinkedHahsMapНельзя ли отсортировать по частоте использования? Всем известно, что он в порядке сложения! ! !

*LinkedHashMap* Модернизация

  • оригинальныйLinkedHashMapУложиться в ситуацию действительно невозможно, но если мы немного посмотрим на исходный код, то обнаружим, что он будет выполняться после put.afterNodeInsertionСюда. Это тожеHashMapуехатьLinkedHashMapДелай расширение!

image-20210611095540549

image-20210611100631032

  • removeNodeзаключается в том, чтобы поставить передние данные. Чтобы войти в этот метод, вам нужноremoveEldestEntryсудить.LinkedHashMapЗначение по умолчанию — false, поэтому нам просто нужно переопределить его. Но как сохранить значение в конце при получении значения? Если мы внимательно посмотрим на исходный код, то обнаружим, что вgetЕсть такой методafterNodeAccess. Его роль состоит в том, чтобы сместить элемент отставания от значения. как раз для насLRUстратегические особенности

image-20210611101435521

  • Подводить итоги! мы используемLinkedHashMapРеализовать стратегию LRU очень просто!

image-20210611101819720

реализовать это самостоятельно

  • Но смысл этого вопроса в том, чтобы изучить, как мы реализуем это сами, а не гениально модифицировать существующие инструменты! Однако, столкнувшисьLinkedHashMapНельзя отрицать, что трансформация очень случайна! Попробуем сделать это сами!

  • Прежде всего, нам нужно определить необходимость использования хэша в сочетании со связанным списком для достижения цели. Хэш, который мы используем естественноHashMapЦель хранения данных — облегчить позиционирование данных. Чтобы найти данные, необходимо использовать связанный список, чтобы переместить данные в конец связанного списка значений в режиме реального времени. Чтобы облегчить нашу работу со связанным списком, связанный список здесь должен быть двойным связным списком!

единица связанного списка

image-20210611104201991

  • Сначала мы определяем внутренний класс! Базовая единица для связанных списков. В нем хранятся ключ и значение, чтобы упростить поиск узла по содержимому, хранящемуся в хэше!preNode,nextNodeУкажите на передний и задний узлы соответственно

image-20210611105808351

  • Инициализируйте емкость и размер связанного списка в построителе и инициализируйте граничный узел, чтобы облегчить нам сдвиг и удаление в рабочем узле.

image-20210611105924364

  • Возвращает -1, если он не был добавлен при получении данных, и перемещает узел, соответствующий данным, в конец связанного списка для добавленных данных.

image-20210611110148633

  • При добавлении в первый раз нам нужно сохранить размер связанного списка и проверить, нужно ли нам удалять данные, Если это не первое добавление, нам нужно только обновить значение и положение соответствующий узел в связанном списке.

image-20210611110255277

имя метода эффект
addToTail Добавьте узел в конец списка значений
moveToTail Переместить узел, который уже существует в связанном списке, в конец связанного списка
removeHeadNode Удалите первый узел в связанном списке, обратите внимание на первый узел после граничного узла

image-20210611110451514

4. Резюме

  • Хотя время выполнения и потребление памяти немного великоваты! Но я просто не оптимизирую.
  • Этот вопрос в основном усложняется при перемещении связанного списка. Нам нужно поддерживать порядок между ними в порядке добавления и частоте использования. Пока этот порядок поддерживается, нет проблем!
Категории