CKTIS / Java
Een LRU-cache met LinkedHashMap
Bouw in Java SE 21 een cache voor twee items en ontdek waarom het lezen van een sleutel bepaalt welk item bij de volgende invoeging verdwijnt.
Versie: Java SE 21
Syntax
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
@Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest)
V put(K key, V value)
V get(Object key)
V remove(Object key)
boolean remove(Object key, Object value)
Collection<V> values()
int size()
Set<K> keySet()In Java SE 21 verwacht LinkedHashMap(int, float, boolean) de begincapaciteit van de hashtabel, de vulfactor en de ordeningsmodus. De eerste twee argumenten beperken het aantal items niet. Met true loopt de iteratie van het langst geleden gebruikte item naar het laatst gebruikte: een geslaagde get(key) of een put(key, value) verplaatst het betrokken item naar het einde. Met false geldt de invoegvolgorde: het lezen van een bestaand item of het vervangen van de waarde met put verandert zijn positie niet.
Voor LRU, waarbij het langst geleden gebruikte item verdwijnt, overschrijf je in een subklasse de beschermde methode removeEldestEntry(Map.Entry<K,V> eldest). Nadat put of putAll een nieuw item heeft toegevoegd, laat size() > 2 de map het eerste item verwijderen zodra er drie zijn. Het vervangen van een waarde activeert dit mechanisme niet. Wijzig de map niet in deze methode als je true retourneert: het effect van die combinatie is niet gespecificeerd.
put(K,V) voegt een waarde toe of vervangt deze, en remove(Object) verwijdert een koppeling op basis van de sleutel. Beide geven de vorige waarde terug, of null als de koppeling ontbrak of de waarde null was. De overload remove(Object,Object) verwijdert de koppeling alleen als de waarde overeenkomt en geeft een boolean terug. Wijzigen is optioneel in Map, maar LinkedHashMap ondersteunt het. size() telt de sleutel-waardekoppelingen.
keySet() geeft een verzameling unieke sleutels terug; values() geeft een collectie die dubbele waarden kan bevatten. Het zijn weergaven die aan de map gekoppeld blijven, geen kopieën: iteratie volgt de volgorde van de map zonder items als opnieuw gebruikt te markeren, verwijderen via een weergave wijzigt de map en toevoegen wordt niet ondersteund. De limiet geldt voor het aantal items, niet voor hun levensduur. De map is niet gesynchroniseerd; zelfs get kan de volgorde wijzigen en een actieve iterator ongeldig maken.
Voorbeelden
import java.util.LinkedHashMap;
import java.util.Map;
public class Main {
private static final class LruCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_ENTRIES = 2;
LruCache() {
super(4, 0.75f, true);
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > MAX_ENTRIES;
}
}
private static void show(String label, Map<String, Integer> cache) {
System.out.println(label + ": keys=" + cache.keySet()
+ ", values=" + cache.values() + ", size=" + cache.size());
}
public static void main(String[] args) {
Map<String, Integer> noRead = new LruCache<>();
noRead.put("A", 1);
noRead.put("B", 2);
noRead.put("C", 3);
show("No read, after put(C)", noRead);
Map<String, Integer> withRead = new LruCache<>();
withRead.put("A", 1);
withRead.put("B", 2);
System.out.println("get(A) = " + withRead.get("A"));
show("With read, before put(C)", withRead);
withRead.put("C", 3);
show("With read, after put(C)", withRead);
System.out.println("remove(A) = " + withRead.remove("A"));
show("After remove(A)", withRead);
}
}Resultaat
No read, after put(C): keys=[B, C], values=[2, 3], size=2 get(A) = 1 With read, before put(C): keys=[B, A], values=[2, 1], size=2 With read, after put(C): keys=[A, C], values=[1, 3], size=2 remove(A) = 1 After remove(A): keys=[C], values=[3], size=1
Zonder leestoegang verdrijft het invoegen van `C` het item `A`. Na `get("A")` is de volgorde `[B, A]`, dus het invoegen van `C` verdrijft `B`. De laatste `remove("A")` geeft `1` terug; alleen `C` blijft over.
Gerelateerde lessen
- Java · Les 47 · Gevorderd · Versie: 2