Как получить LRU-кэш на базе LinkedHashMap?

Нужны обе части. Флаг accessOrder переводит внутренний список из порядка вставки в порядок обращения: каждый get перемещает запись в конец, поэтому в голове списка всегда самая давно не используемая. Метод removeEldestEntry вызывается после вставки и по умолчанию возвращает false — пока его не переопределить, никакого вытеснения не будет. Ограничения, которые стоит назвать: реализация не потокобезопасна, а вытеснение происходит только при добавлении новой записи, поэтому карта, в которую перестали писать, не сжимается. Для конкурентного кэша с TTL берут специализированную библиотеку.

class 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; }
}