LinkedHashMap removeEldestEntry Entfernen von 2 Elementen?

Question

Ich sah diesen Thread: LinkedHashMap removeEldestEntry: How many elements are removed?

Und es besagt, dass removeEldestEntry nur 1 Element entfernt. Das macht für mich Sinn, aber wenn ich über meinen Code debugge, scheint es 2 Elemente zu entfernen. Ich bin mir nicht sicher warum.

public class LRUCache { 
    LinkedHashMap<Integer, Integer> LRUMap; 

    public LRUCache(int capacity) { 
     LRUMap = new LinkedHashMap<Integer, Integer>() { 
      @Override 
      protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 
       return LRUMap.size() > capacity; 
      } 
     }; 
    } 

    public int get(int key) { 
     if (LRUMap.containsKey(key)) { 
      int val = LRUMap.remove(key); 
      LRUMap.put(key, val); 
      return val; 
     } 
     return -1; 
    } 

    public void set(int key, int value) { 
     LRUMap.put(key, value); 
    } 

    public static void main(String[] args) {  
     LRUCache c = new LRUCache(2); 
     c.set(2,1); 
     c.set(1,1); 
     c.set(2,3); 
     c.set(4,1); 
    } 
} 

So kann man daraus ersehen, dass es eingefügt wird: (2,1) und (1,1). Das nächste Element ist, wo die Dinge unordentlich werden. Da der Schlüssel 2 bereits vorhanden ist, wird das Element (2,1) mit (2,3) überschrieben. Danach, wenn ich (4,1) einfügen, habe ich bereits 2 Elemente, so sollte es den ältesten Eintrag entfernen: (1,1). Es entfernt jedoch beide (2,3) und (1,1), so dass ich nur mit (4,1) in der Karte.

Irgendwelche Ideen warum? Ich nehme an, das hat etwas damit zu tun, dass der Schlüssel ersetzt wird und (2,3) am Anfang der Liste steht, wie es der älteste Eintrag ist, obwohl es nicht sein sollte. Aber ich bin immer noch verwirrt, warum es 2 Elemente entfernen würde.

Nebenbei bemerkt sieht es so aus, als würde es das älteste Element an der Vorderseite des speichern, was uns auch eine konstante Zeitentfernung des ältesten Eintrags geben würde. Ist das wahr?

Answer 1

Der Schlüssel Verhaltensmerkmal LinkedHashMap zu verstehen ist, dass die Map.Entry<Integer, Integer> Mitglieder der Karte organisiert sind Auftrag, zu erhalten, die die Fragen beantwortet, die Sie für die Bestellung der Mitglieder innerhalb der Map bezogen haben. Wenn wir also durch jede Zeile Code in Ihre main Methode gehen, werden wir folgendes sehen:

1. Nach c.set(2,1) der Inhalt LRUMap wird: {2=1}.
2. Nach c.set(1,1) wird der Inhalt LRUMap sein: {2=1, 1=1}.
3. Nach c.set(2,3) wird der Inhalt LRUMap wird: {2=3, 1=1}. Diese Aktion aktualisiert einfach den für den Schlüssel (2) von 1 bis 3 abgebildeten Wert und ist nicht betrachtet als eine strukturelle Änderung, so dass die Reihenfolge der Mitglieder beibehalten wird.
4. Nach c.set(4,1) wird der Inhalt von LRUMap sein: {1=1, 4=1}. Das Mapping: 2=3 gilt als der älteste Eintrag, daher wird es entfernt (und das Mapping: 1=1 bleibt erhalten).

Da es klar aus Ihrer Absicht ist, dass Sie einen am wenigsten kürzlich verwendeten Cache erstellen möchten, sollten Sie den Bau Ihres LinkedHashMap Wechsel betrachten weg von Einsetzen Ordnung Element-Speicher zugunsten zu bewegen von last-access Mitglied Bestellung.Die LinkedHashMap Klasse einen alternativen Konstruktor stellt diese Art der Nutzung zu unterstützen:

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 

Wenn Sie den Wert übergeben: true für den accessOrder Parameter werden die Mitgliedszuordnungen in Zugriff Ordnung gespeichert werden (das, was Sie für einen LRU-Cache verwenden möchten) oder wenn Sie den Wert false für den Parameter accessOrder übergeben, werden die Elementzuordnungen in Einfügereihenfolge gespeichert.