Implementarea unui cache de tip LRU

Astăzi vom împlementa un simplu cache de tipul LRU. De ce la ce vine LRU? Least Recently Used.

Cum funcționează un cache de acest tip? Forte simplu. Operația de find va aduce elementul din cache, dacă există, sau Optional.empty() dacă elementul nu există în cache. Pe lângă operația de get, cache-ul va expune și o operație de put, prin care se va putea actualiza valoarea unui element. Dacă elementul nu există deja în cache, atunci se va adăuga în acesta din urmă. În plus, un cache de acest gen trebuie să mai aibă și o capacitate maximă, pentru a evita problemele de genul – Out of memory. Dacă la adăugarea unui nou element se va depăși capacitatea, atunci elementul cel mai puțin utilizat va trebui să fie eliminat pentru a menține valoarea capacității.

Să recapitulăm:

• LeastRecentlyUsedCache(int capacity) – prin constructor vom inițializa capacitatea maximă a cache-ului nostru.

• Optional find(String key) – metoda prin care se va putea căuta un element în cache. Vorbim de un getter, dar am numit intenționat metoda find pentru că returnează un Optional.

• Optional putAndReturn(String key, String value) – metoda prin care se va putea scrie o valoare nouă în cache. Metoda va returna valoarea suprascrisă încapsulată într-un Optional, dacă există, altfel Optional.empty().

Cerința este să se implementeze în Java un cache de acest tip și să se aibă în vedere faptul că operațiile de tipul find și put să aibă complexitatea O(1).

Înainte de a trece la implementare, să luăm și un exemplu. Este foarte important să aveți un pix și o foaie și să petreceți cel puțin 5 minute, pentru a analiza problema pe foaie. Nu vă grăbiți niciodată să treceți direct la implementare!

Exemplu:

LeastRecentlyUsedCache cache = new LeastRecentlyUsedCache(3);
cache.putAndReturn("ka", "va"); // cache-ul are 1 element după operație
cache.putAndReturn("kb", "vb"); // cache-ul are 2 elemente după operație
cache.putAndReturn("kc", "vc"); // cache-ul are 3 elemente după operație
cache.find("ka"); // returnează Optional.of("va");
cache.find("kb"); // returnează Optional.of("vb");
cache.putAndReturn("kd", "vd"); // cache-ul are 4 elemente după operație. Vom scoate un element din acesta, pe cel mai puțin utilizat și anume "kc".
cache.find("kc"); // returnează Optional.empty();
cache.putAndReturn("ke", "ve"); // cache-ul are 4 elemente după operație. Vom scoate un element din acesta, pe cel mai puțin utilizat și anume "ka".
cache.find("ka"); // returnează Optional.empty();

Să trecem la soluție. Sunt mai multe implementări, cea mai simplă bazându-se pe un LinkedHashMap. Vă invit să petreceți puțin timp pentru a citi documentația oficială. Partea de eviction aici este puțin tricky, de aceea, din documentație, va trebui să puneți accentul pe metoda removeEldestEntry.

Totul este straight forward după ce ați citit documentația:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Optional;

public class LeastRecentlyUsedCache extends LinkedHashMap<String, String> {

    private final int capacity;

    public LeastRecentlyUsedCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public Optional<String> find(String key) {
        return Optional.ofNullable(get(key));
    }

    public Optional<String> putAndReturn(String key, String value) {
        return Optional.ofNullable(put(key, value));
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > capacity;
    }

}

Avem și un mic test:

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class LeastRecentlyUsedCacheTest {

    @Test
    public void testExample() {
        // given
        LeastRecentlyUsedCache cache = new LeastRecentlyUsedCache(3);

        // when & then
        Assertions.assertThat(cache.putAndReturn("ka", "va")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("kb", "vb")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("kc", "vc")).isNotPresent();
        Assertions.assertThat(cache.find("ka")).isPresent();
        Assertions.assertThat(cache.find("kb")).isPresent();
        Assertions.assertThat(cache.putAndReturn("kd", "vd")).isNotPresent();
        Assertions.assertThat(cache.find("kc")).isNotPresent();
        Assertions.assertThat(cache.putAndReturn("ke", "ve")).isNotPresent();
        Assertions.assertThat(cache.find("ka")).isNotPresent();
    }

}

Temă de casă: Implementarea noastră suferă la capitolul încapsulare. De ce? Pentru că prin extinderea clasei LinkedHashMap, vor fi expuse by default și metodele get și put din clasa părinte. Dvs. aveți responsabilitatea să vă gândiți cum puteți "să ascundeți" aceste metode.

Spor la treabă!