Какие структуры данных обычно используются для кэшей LRU и быстрого поиска объектов?

Я намеревался реализовать HashTable для быстрого поиска объектов, что важно для моего приложения.

Однако мне не нравится идея сканирования и, возможно, блокировка всей таблицы, чтобы найти, какой объект был в последний раз доступ. Таблицы могут быть довольно большими.

Какие структуры данных обычно используются для преодоления этого?

например. Я думал, что могу бросить объекты в FIFO, а также в кеш, чтобы узнать, сколько лет прошло. Но это не будет поддерживать алгоритм LRU.

Любые идеи? как кальмары делают это?

Ответы

Ответ 1

Связанные списки хороши для кэшей LRU. Для индексированных запросов внутри связанного списка (для перемещения записи к последнему используемому концу связанного списка) используйте HashTable. Самая последняя использованная запись всегда будет последней в связанном списке.

Ответ 2

Вы можете найти это article в реализации LRU кэша, используя интересные контейнеры STL (или альтернативу boost::bimap). С помощью STL в основном вы используете комбинацию карты (для быстрого поиска по ключевым словам) и отдельный список ключей или итераторов в эту карту (для упрощения ведения истории доступа).