LRU, метод вытеснения из кэша

[Frozik]

А чем двусвязный список + hash не угодил, зачем хранить время?

[Pr0grammer]

Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.

[Goder]

По-моему, стопка листов, в которую новый кладем сверху, а самый старый забираем снизу, понятнее.

[Pr0grammer]

Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.

[ToSHiC]

Варианты с одной очередью не очень хороши — однократно запрошенные элементы будут вытеснять чуть менее популярные элементы, которые запрашивали много раз. В интернетах встречаются статьи про кэши 2Q, где эта проблема частично решена: хэш-таблица для поиска элементов и 2 очереди. Сначала элемент попадает в нижнюю очередь, а если его запросили второй раз и он всё ещё в кэше — то тогда в верхнюю. Когда верняя очередь заканчиваются — элементы из неё вытесняются в нижнюю, из нижней же элементы вытесняются совсем и удаляются из кэша. Получается константное время поиска записи и её добавления

Кстати, в бусте есть контейнер, который отлично подходят для подобных схем — intrusive list. Ну и ещё intrusive hashmap, чтобы уж совсем минимально с памятью работать.

[Pr0grammer]

Спасибо, читал в процессе написания статьи, и решил не грузить. Добавил ссылку для интересующихся.

[javaspecialist]

О том какие готовые решения предоставляет Java можно почитать в статье Java LRU Cache

[akalend]

А как решаем проблему консистентности?

[Tertium]

зачем решение с log(n), когда на листе и хеше элементарно сделать за n?

[C4ET4uK]

а что быстрее n или log(n)?