new LinkedHashMap<>(cap, 0.75f, true) (accessOrder) + переопределённый removeEldestEntry, возвращающий size() > max. Get переносит запись в конец, самая давно неиспользуемая — в голове и вытесняется.
А ещё Caffeine (W-TinyLFU) обычно даёт больше попаданий, чем LRU
Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.
Нужны обе части. Флаг accessOrder переводит внутренний список из порядка вставки в порядок обращения: каждый get перемещает запись в конец, поэтому в голове списка всегда самая давно не используемая. Метод removeEldestEntry вызывается после вставки и по умолчанию возвращает false — пока его не переопределить, никакого вытеснения не будет. Ограничения, которые стоит назвать: реализация не потокобезопасна, а вытеснение происходит только при добавлении новой записи, поэтому карта, в которую перестали писать, не сжимается. Для конкурентного кэша с TTL берут специализированную библиотеку.
sottoclass Lru<K, V> extends LinkedHashMap<K, V> {
private final int max;
Lru(int max) { super(16, 0.75f, true); this.max = max; }
@Override protected boolean removeEldestEntry(Map.Entry<K, V> e) { return size() > max; }
}Один верный вариант. Подумайте, потом откройте ответ.
Порядок вставки против порядка доступа, связанный список поверх HashMap и реализация LRU через removeEldestEntry.
sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.