Структура данных Sorted Keys для политик вытеснения LRU и MRU

Question

Я работаю над простой структурой данных, которая будет реализовывать политику удаления кеша. Я хочу реализовать два возможных сценария: LRU и MRU.

Я ищу похожую на карту структуру данных, где ключи - это, возможно, время (или, может быть, просто инкрементное целое число), чтобы узнать, какой блок кеша использовался последним или использовался реже всего. И значения - это идентификаторы блоков.

Существует ли существующая структура данных, которая сортирует данные по ключам при вставке и извлекает значение определенного ключа за время O(1)?

Например, HashMap в Java имеет постоянный поиск по времени, но мне нужно будет получить все ключи, отсортировать их и выбрать последний или первый в зависимости от алгоритма, который я реализую. Является ли SortedMap то, что я должен идти? Вы предлагаете какие-либо другие структуры данных, которые хорошо работают с реализациями LRU и MRU?

Спасибо

Answer 1

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

Из своего ага:

{@Link Map}, которая дополнительно обеспечивает полный порядок своих ключей. Карта упорядочена в соответствии с {@linkplain Comparable естественным порядком} ее ключей или {@link Comparator}, обычно предоставляемым во время создания отсортированной карты. Этот порядок отражается при переборе представлений коллекции отсортированной карты (возвращаемых методами entrySet, keySet и values). Несколько дополнительных операций предоставляются, чтобы воспользоваться преимуществами заказа.

Даже если записи и ключи возвращаются в отсортированном порядке возрастания от SortedMapтакже есть методы firstKey() а также lastKey(), что также может быть полезным.

В частности, для LRU: наиболее распространенным способом в Java является использование LinkedHashMap, который имеет метод removeEldestEntry(Map.Entry), По умолчанию он ничего не делает, но вы можете легко расширить класс и реализовать этот метод. Более подробную информацию вы можете найти здесь.