Implementera en LRU-cache

Du utvecklar en webbapplikation som ofta hämtar användarprofilinformation i form av strängar. För att förbättra prestandan vill du implementera en enkel cache som lagrar dessa profilsträngar och kan identifiera vilka poster som användes minst nyligen.

Klassen CacheEntry har förinsetts åt dig.

Den här övningen är en del av kursen

Optimera kod i Java

Visa kurs

Övningsinstruktioner

I metoden get() hämtar du cache-posten för den angivna key.
Uppdatera åtkomsttiden för key efter att du har hämtat den.
Efter att en post lagts till i cachen – om kapaciteten har överskridits – tar du bort den senast minst använda posten.

Interaktiv övning med praktiskt arbete

Testa den här övningen genom att slutföra den här exempelkoden.

public class StringCache {
    private final int capacity = 100;
    private final Map cache = new HashMap<>();
    
    public String get(String key) {
        // Get the entry for the specified key
        CacheEntry entry = ____.get(____);
        if (entry == null) return null;
        // Update its access time
        entry.____();
        return entry.value;
    }
    
    public void put(String key, String value) {
        cache.put(key, new CacheEntry(value));
        if (cache.size() > capacity) {
            // If capacity exceeded, remove least recently used
            ____();
        }
    }

    void removeLeastRecentlyUsed() {
        String lruKey = null;
        long oldest = Long.MAX_VALUE;
        for (Map.Entry e : cache.entrySet()) {
            if (e.getValue().lastAccessed < oldest) {
                oldest = e.getValue().lastAccessed;
                lruKey = e.getKey();
            }
        }
        if (lruKey != null) { cache.remove(lruKey); }
    }

    public static void main(String[] args) {}
}

Redigera och kör kod