Как сделать простой LRU-кеш

Короткий ответ

LRU-кеш хранит ограниченное число записей и при переполнении удаляет ту, к которой дольше всего не обращались. LinkedHashMap с порядком доступа делает это за вас:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    LruCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
 
void main() {
    var cache = new LruCache<String, Integer>(2);
    cache.put("a", 1);
    cache.put("b", 2);
    cache.get("a");
    cache.put("c", 3);
 
    IO.println(cache);
}

Результат:

{a=1, c=3}

Третий аргумент конструктора true включает порядок доступа: get("a") переносит a в конец, поэтому вытесняется b.

Кеш вычислений

Вместе с computeIfAbsent() кеш запоминает результаты дорогих вычислений:

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
 
    LruCache(int capacity) {
        super(16, 0.75f, true);
        this.capacity = capacity;
    }
 
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }
}
 
int slowSquare(int n) {
    IO.println("computing " + n);
    return n * n;
}
 
void main() {
    var cache = new LruCache<Integer, Integer>(100);
 
    IO.println(cache.computeIfAbsent(4, this::slowSquare));
    IO.println(cache.computeIfAbsent(4, this::slowSquare));
}

Результат:

computing 4
16
16

Частая ошибка

Забыть третий аргумент конструктора. Без него LinkedHashMap хранит порядок добавления, и вытесняется самая старая запись, даже если её только что читали:

void main() {
    var cache = new LinkedHashMap<String, Integer>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
            return size() > 2;
        }
    };
    cache.put("a", 1);
    cache.put("b", 2);
    cache.get("a");
    cache.put("c", 3);
 
    IO.println(cache);
}

Результат:

{b=2, c=3}

Этот кеш не потокобезопасен. Если к нему обращаются несколько потоков, оберните его в Collections.synchronizedMap() или используйте готовую библиотеку вроде Caffeine.

Спасибо, что читаете!

Короткий ответ

Кеш вычислений

Частая ошибка

Функции из этого ответа

Спасибо, что читаете!