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

Я имею в виду две реализации:

1). Создайте две карты, которые выглядят примерно так

std::map<timestamp, k> time_to_key
std::map<key, std::pair<timestamp, V>> LRUCache

Чтобы вставить новый элемент, мы можем поместить текущую метку времени и значение вLRUCache, Хотя, когда размер кэша заполнен, мы можем удалить самый последний элемент, найдя наименьшую временную метку ввремя_to_ключ и удалив соответствующий ключ изLRUCache, Вставка нового элемента - O (1), обновление временной метки - O (n) (потому что мы должны искатьk соответствующий отметке времени ввремя_to_ключ.

2). Имейте связанный список, в котором наименее использованный кеш присутствует в заголовке, а новый элемент добавляется в конец. Когда прибывает элемент, который уже присутствует в кэше, узел, соответствующий ключу этого элемента, перемещается в конец списка. Вставка нового элемента - это O (1), обновление отметки времени - снова O (n) (потому что нам нужно перейти к концу списка), а удаление элемента - это O (1).

Теперь у меня есть следующие вопросы:

Какая из этих реализаций лучше для LRUCache.

Есть ли другой способ реализовать LRU Cache.

В Java, я должен использовать HashMap для реализации LRUCache

Я видел такие вопросы, как реализация общего LRU-кэша, а также такие вопросы, как реализация LRU-кэша. Отличается ли общий кэш LRU от кеша LRU?

Заранее спасибо!!!

РЕДАКТИРОВАТЬ:

Другой способ (самый простой способ) реализовать LRUCache в Java - использовать LinkedHashMap и переопределить логическую функцию removeEldestEntry (Map.entry eldest).