Дизайн кэша LRU
Последний использованный (LRU) Кэш должен отбросить последние использованные объекты сначала, Как делают Вас разработка и реализация такой класс кэша? Конструктивные требования следующие:
1) найдите объект с такой скоростью, как мы можем
2) Однажды неудачные обращения в кэш и кэш полны, мы должны заменить последний использованный объект максимально быстро.
Как проанализировать и реализовать этот вопрос с точки зрения дизайна шаблона разработки и алгоритма?
1 ответ
Связанный список + хеш-таблица указателей на узлы связанного списка - это обычный способ реализации кешей LRU. Это дает O (1) операций (при условии приличного хеширования). Преимущество этого (O (1)): вы можете создать многопоточную версию, просто заблокировав всю структуру. Вам не нужно беспокоиться о детальной блокировке и т. Д.
Вкратце, как это работает:
При доступе к значению вы перемещаете соответствующий узел в связанном списке в начало.
Когда вам нужно удалить значение из кеша, вы удаляете его из хвостовой части.
Когда вы добавляете значение в кеш, вы просто помещаете его в начало связанного списка.
Благодаря doublep, вот сайт с реализацией C ++: Разные шаблоны контейнеров .