Zmiana kolejności wpisów LRUCache podczas używania get

Question

Sprawdziłem oficjalną dokumentację systemu Android dla LRUCache, która mówi: Za każdym razem, gdy uzyskuje się dostęp do wartości, jest ona przenoszona do nagłówka kolejki. Gdy wartość zostanie dodana do pełnej pamięci podręcznej, wartość na końcu tej kolejki zostanie wyeksmitowana i może się kwalifikować do zbierania śmieci. Przypuszczam, że jest to podwójnie połączona lista obsługiwana przez linkedhashmap, która jest używana przez pamięć podręczną. Aby sprawdzić to zachowanie, sprawdziłem kod źródłowy LruCache i sprawdziłem metodę get (K key) (). Ponadto wywołuje metodę get mapy, która pobiera wartość z podstawowej strategii i wywołuje metodę recordAccess.

public V get(Object key) { 
    LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key); 
    if (e == null) 
     return null; 
    e.recordAccess(this); 
    return e.value; 
} 

metoda recordAccess z kolei przesuwa dostępnego wejście na końcu listy w przypadku accessOrder jest ustawiony na true (dla mojego problemu załóżmy to jest), bo inaczej nic nie robi.

/** 
    * This method is invoked by the superclass whenever the value 
    * of a pre-existing entry is read by Map.get or modified by Map.set. 
    * If the enclosing Map is access-ordered, it moves the entry 
    * to the end of the list; otherwise, it does nothing. 
    */ 
    void recordAccess(HashMap<K,V> m) { 
     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
     if (lm.accessOrder) { 
      lm.modCount++; 
      remove(); 
      addBefore(lm.header); 
     } 
    } 

Brzmi to sprzecznie z powyższym stwierdzeniem, w którym mówi się, że element został przeniesiony na czoło kolejki. Zamiast tego jest przenoszony do ostatniego elementu listy (używając head.before). Na pewno czegoś tu brakuje, jakiejkolwiek pomocy?

Answer 1

Nie brakuje niczego, tylko czytasz dokumentację LruCache dla LinkedHashMap. LinkedHashMap ma własną dokumentację, w szczególności o numerze accessOrder. (To samo z Java docs).

[... kiedy accessOrder = true ...] kolejność iteracji jest kolejność, w jakiej jego wpisy zostały ostatniego dostępu, od najmniej do najbardziej niedawno obejrzano-niedawno (access-order)

Tak więc LinkedHashMap umieszcza ostatnio używane wpisy na końcu i jest udokumentowane.

Praktycznie LruCache opisuje w jaki sposób takie cache działa w teorii, ale LinkedHashMap pokazuje jak wdrożyć go bez dodawania oddzielnych iteratory do tyłu poruszające: umieszczając ostatnie elementy na końcu, trimming można używać już dostępne (forward-animowana) iterator aby skutecznie uzyskać dostęp do (i usunąć) starych elementów.

Chociaż tu i teraz nie mogłem powiedzieć, co było nie tak z removeEldestEntry. Być może nie istniało w przeszłości.

Answer 2

Z javadoc z LinkedHashMap:

Jeśli używany jest konstruktor trzy argumenty i accessOrder jest określona jako prawdziwej, iteracja będzie w porządku, że wpisy zostały dostęp. Na zamówienie dostępu wpływa wstaw, uzyskać i putAll operacji, ale nie przez operacje w widokach kolekcji.

Exactly the case, który ma LruCache.

public LruCache(int maxSize) { 
    if (maxSize <= 0) { 
     throw new IllegalArgumentException("maxSize <= 0"); 
    } 
    this.maxSize = maxSize; 
    this.map = new LinkedHashMap<K, V>(0, 0.75f, true); 
} 

Zobaczmy co recordAccess() robi:

void recordAccess(HashMap<K,V> m) { 
     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 
     if (lm.accessOrder) { // true, because `LruCache` instantiated this 
           // map with `accessOrder = true` 
      lm.modCount++; 
      remove(); // remove this `LinkedHashMapEntry` from the map 
      addBefore(lm.header); // adds this entry before the current header of 
            // the map, thus this entry becomes the header 
     } 
    } 

Zamiast to przeniósł się do ostatniego elementu listy (używając head.before).

Nie widzę, jak ważne jest Twoje oświadczenie.