ConcurrentModificationException durante l'aggiornamento di Iterator memorizzato (per l'implementazione della cache LRU)

Question

Sto tentando di implementare la mia cache LRU. Sì, so che Java fornisce uno LinkedHashMap per questo scopo, ma sto cercando di implementarlo utilizzando le strutture di dati di base.

Dalla lettura di questo argomento, comprendo che ho bisogno di una HashMap per O (1) ricerca di una chiave e di un elenco collegato per la gestione della politica di sfratto "meno recente". Ho trovato questi riferimenti che utilizzano tutti un hashmap libreria standard, ma attuare le proprie lista collegata:

• "What data structures are commonly used for LRU caches and quickly locating objects?" (stackoverflow.com)
• "What is the best way to Implement a LRU Cache?" (quora.com)
• "Implement a LRU Cache in C++" (uml.edu)
• "LRU Cache (Java)" (programcreek.com)

La tabella hash dovrebbe memorizzare direttamente un elenco nodo legato come mostro qui di seguito. La mia cache dovrebbe memorizzare chiavi Integer e valori String.

Tuttavia, in Java collezione LinkedList non espone i suoi nodi interni, quindi non li può memorizzare all'interno del HashMap. Potrei invece avere gli indici del negozio HashMap in LinkedList, ma poi arrivare a un elemento richiederebbe O (N) tempo. Così ho provato a memorizzare un ListIterator.

import java.util.Map; 
import java.util.HashMap; 
import java.util.List; 
import java.util.LinkedList; 
import java.util.ListIterator; 

public class LRUCache { 

    private static final int DEFAULT_MAX_CAPACITY = 10; 

    protected Map<Integer, ListIterator> _map = new HashMap<Integer, ListIterator>(); 
    protected LinkedList<String> _list = new LinkedList<String>(); 

    protected int _size = 0; 
    protected int _maxCapacity = 0; 

    public LRUCache(int maxCapacity) { 
     _maxCapacity = maxCapacity; 
    } 

    // Put the key, value pair into the LRU cache. 
    // The value is placed at the head of the linked list. 
    public void put(int key, String value) { 

     // Check to see if the key is already in the cache. 
     ListIterator iter = _map.get(key); 

     if (iter != null) { 
      // Key already exists, so remove it from the list. 
      iter.remove(); // Problem 1: ConcurrentModificationException! 
     } 

     // Add the new value to the front of the list. 
     _list.addFirst(value); 
     _map.put(key, _list.listIterator(0)); 

     _size++; 

     // Check if we have exceeded the capacity. 
     if (_size > _maxCapacity) { 
      // Remove the least recently used item from the tail of the list. 
      _list.removeLast(); 
     } 
    } 

    // Get the value associated with the key. 
    // Move value to the head of the linked list. 
    public String get(int key) { 

     String result = null; 
     ListIterator iter = _map.get(key); 

     if (iter != null) { 

      //result = iter 
      // Problem 2: HOW DO I GET THE STRING FROM THE ITERATOR? 

     } 

     return result; 
    } 

    public static void main(String argv[]) throws Exception { 
     LRUCache lruCache = new LRUCache(10); 

     lruCache.put(10, "This"); 
     lruCache.put(20, "is"); 
     lruCache.put(30, "a"); 
     lruCache.put(40, "test"); 
     lruCache.put(30, "some"); // Causes ConcurrentModificationException 
    } 
} 

Quindi questo porta a tre problemi:

Problema 1: sto ottenendo un ConcurrentModificationException quando aggiorno il LinkedList utilizzando l'iteratore che posso conservare nel HashMap.

Exception in thread "main" java.util.ConcurrentModificationException 
    at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:953) 
    at java.util.LinkedList$ListItr.remove(LinkedList.java:919) 
    at LRUCache.put(LRUCache.java:31) 
    at LRUCache.main(LRUCache.java:71) 

Problema 2. Come posso recuperare il valore indicato da ListIterator? Sembra che io possa solo recuperare il valore next().

Problema 3. Esiste un modo per implementare questa cache LRU utilizzando la raccolta LinkedList Java o devo implementare la mia lista concatenata?

Answer 1

mi occuperò con il problema 3 prima:

Come fai notare nella sua interrogazione, LinkedList (come tutti ben progettato collezioni generici) nasconde i dettagli di attuazione, come i nodi che contengono i link. Nel tuo caso hai bisogno della tua mappa hash per fare riferimento a questi collegamenti direttamente come i valori della mappa. Fare altrimenti (ad esempio avendo indiretto attraverso una terza classe) avrebbe vanificato lo scopo di una cache di LRU per consentire un sovraccarico molto basso sull'accesso ai valori. Ma questo non è possibile con le Collezioni Java standard: non forniscono (e non dovrebbero) fornire un accesso diretto alle strutture interne.

Quindi la conclusione logica di questo è che, sì, è necessario implementare il proprio modo di memorizzare l'ordine in cui sono stati utilizzati gli elementi nella cache. Questo non deve essere un elenco doppio linkato. Quelli sono stati tradizionalmente usati per le cache LRU perché l'operazione più comune è quella di spostare un nodo in cima alla lista quando vi si accede. Questa è un'operazione incredibilmente economica in una lista a doppio collegamento che richiede solo quattro nodi per essere ricollegato senza allocazione di memoria o libera.

Problema 1 & 2:

Essenzialmente la causa principale qui è che questo si sta tentando di utilizzare iteratori come un cursore. Sono progettati per essere creati, fatti passare per eseguire alcune operazioni e quindi eliminati. Anche se supererai i problemi che ti attendo, ci saranno ulteriori problemi dietro di loro. Stai mettendo un piolo quadrato in un buco rotondo.

Quindi la mia conclusione è che è necessario implementare il proprio modo di contenere i valori in una classe che tiene traccia dell'ordine di accesso. Tuttavia può essere incredibilmente semplice: sono necessarie solo tre operazioni: creare, ottenere valore e rimuovere dalla coda. Entrambi creano e ottengono valore devono spostare il nodo in testa alla lista. Nessun inserimento o cancellazione dal centro della lista. No cancellando la testa. Nessuna ricerca Onestamente morto semplice.

Speriamo che questo vi permetterà di cominciare :-)

public class <K,V> LRU_Map implements Map<K,V> { 
    private class Node { 
     private final V value; 
     private Node previous = null; 
     private Node next = null; 

     public Node(V value) { 
      this.value = value; 
      touch(); 
      if (tail == null) 
       tail = this; 
     } 

     public V getValue() { 
      touch(); 
      return value; 
     } 

     private void touch() { 
      if (head != this) { 
       unlink(); 
       moveToHead(); 
      } 
     } 

     private void unlink() { 
      if (tail == this) 
       tail = prev; 
      if (prev != null) 
       prev.next = next; 
      if (next != null) 
       next.prev = prev; 
     } 

     private void moveToHead() { 
      prev = null; 
      next = head; 
      head = this; 
     } 

     public void remove() { 
      assert this == tail; 
      assert this != head; 
      assert next == null; 
      if (prev != null) 
       prev.next = null; 
      tail = prev; 
     } 
    } 

    private final Map<K,Node> map = new HashMap<>(); 
    private Node head = null; 
    private Node tail = null; 

    public void put(K key, V value) { 
     if (map.size() >= MAX_SIZE) { 
      assert tail != null; 
      tail.remove(); 
     } 
     map.put(key, new Node(value)); 
    } 

    public V get(K key) { 
     if (map.containsKey(key)) 
      return map.get(key).getValue(); 
     else 
      return null; 
    } 

    // and so on for other Map methods 
} 

Answer 2

1) Questo non è proprio ciò che gli Iterator servono.

Per contratto, se si modifica la lista senza usare l'iteratore - come si fa qui

_list.addFirst(value);

poi iteratori tutti aperti in tale elenco devono gettare ConcurrentModificationException. Erano aperti a una versione dell'elenco che non esiste più.

2) A LinkedList non è, esattamente, un elenco collegato di nodi. È un java.util.List, la cui implementazione di supporto è una lista di nodi doppiamente collegata. Quel contratto List è il motivo per cui non espone i riferimenti all'implementazione del backing - quindi operazioni come "rimuovi questo nodo, come nodo e spostalo in testa" non vanno bene.Questo incapsulamento è per la tua stessa protezione (come l'eccezione mod simultanea) - consente al tuo codice di fare affidamento sulla semantica di List di una LinkedList (iterabilità, per esempio) senza preoccuparsi che alcuni jolly a due cubetti di distanza stiano tagliando le sue interiora e ha rotto il contratto.

3) Quello di cui hai veramente bisogno qui NON è una lista collegata. Quello di cui hai bisogno è una pila che ti permetta di spostare qualsiasi voce arbitraria sulla testa e scaricare la coda. Stai insinuando che vuoi un tempo di ricerca veloce per una voce arbitraria e anche una rimozione rapida e una rapida aggiunta, E vuoi essere in grado di trovare la coda in qualsiasi momento nel caso in cui sia necessario rimuoverla.

veloce tempo di ricerca == Hash Qualcosa

veloce aggiungere/rimuovere elementi arbitrari == Linked Qualcosa

rapido indirizzamento del elemento finale == Somekinda Lista

4) Avrai bisogno di costruire la tua propria struttura di collegamento ... o usare una LinkedHashMap.

PS LinkedHashSet sta barando, è implementato utilizzando una LinkedHashMap.

Answer 3

Un altro modo per scuoiare questo gatto sarebbe quello di implementare una semplice classe che estende la LinkedList, ma corre eventuali modifiche all'elenco (ad esempioaggiungi, rimuovi, ecc.) all'interno di un blocco "sincronizzato". Avrai bisogno di eseguire lo pseudo-puntatore HashMap attraverso get() ogni volta, ma dovrebbe funzionare bene. per esempio.

... 
private Object lock = new Object(); //semaphore 

//override LinkedList's implementations... 
@Override 
public <T> remove(int index) { synchronized(lock) { return super.remove(index); } } 
... 

Se si dispone di Eclipse o IntelliJ IDEA, allora si dovrebbe essere in grado di generare automaticamente gli stub metodo che avete bisogno quasi istantaneamente, e si può valutare quali hanno bisogno di essere bloccato.