KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

CKTIS / Java

LRU-cache op basis van toegangsvolgorde

Gebruik een `LinkedHashMap` in toegangsvolgorde om bij overschrijding van de limiet het langst niet gebruikte item te verwijderen, niet het item dat als eerste werd toegevoegd.

Versie: Java SE 21

Syntax

new LinkedHashMap<K, V>(initialCapacity, loadFactor, true) { @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxEntries; } }

LRU (least recently used) verwijdert het item dat het langst niet is gebruikt. FIFO (first in, first out) verwijdert het item dat als eerste is toegevoegd: het lezen van dat item verandert de verwijdervolgorde niet. LRU kijkt dus naar de laatste toegang en FIFO naar het moment van invoegen.

Bij LinkedHashMap kiest het derde constructorargument, true, voor toegangsvolgorde in plaats van de standaard invoegvolgorde. Bij de bewerkingen in het voorbeeld komt tijdens iteratie het langst niet gebruikte item als eerste en het meest recent gebruikte item als laatste. In Java SE 21 plaatsen putFirst en putLast een item expliciet aan het begin of aan het einde zonder een toegang te registreren. Daardoor kan de iteratievolgorde afwijken van de volgorde van de laatste toegangen. Een get voor een aanwezige sleutel of een put die een bestaand item bijwerkt, verplaatst dat item naar het einde als het daar nog niet staat. Een get voor een ontbrekende sleutel en containsKey veranderen de volgorde niet.

Toegangsvolgorde alleen begrenst de map niet. Nadat put een nieuw item heeft toegevoegd, geeft de overschreven methode removeEldestEntry true terug als size() > maxEntries, waarna de map het eerste item verwijdert. initialCapacity is de begincapaciteit, geen limiet op het aantal items; door deze regel verlopen items niet na verloop van tijd.

LinkedHashMap is niet gesynchroniseerd. Als meerdere threads deze cache delen, synchroniseer dan de toegang van buitenaf, ook bij leesbewerkingen: get kan de iteratievolgorde wijzigen.

Voorbeelden

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

public class LruDemo {
    public static void main(String[] args) {
        int maxEntries = 2;
        Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
                return size() > maxEntries;
            }
        };

        cache.put("A", 1);
        cache.put("B", 2);
        cache.get("A");
        System.out.println(cache.keySet());

        cache.put("C", 3);
        System.out.println(cache.keySet());
    }
}

Resultaat

[B, A]
[A, C]

De limiet is twee items. `get("A")` verplaatst `A` achter `B`, dus bij het invoegen van `C` verdwijnt `B`. FIFO zou `A` verwijderen.

Gerelateerde lessen

  • Java · Les 40 · Gemiddeld · Versie: 2

Bronnen