ConcurrentModificationException beim Aktualisieren des gespeicherten Iterators (für die LRU-Cache-Implementierung)

Question

Ich versuche, meinen eigenen LRU-Cache zu implementieren. Ja, ich weiß, dass Java zu diesem Zweck einen LinkedHashMap bereitstellt, aber ich versuche, es mit grundlegenden Datenstrukturen zu implementieren.

Aus dem Lesen über dieses Thema, verstehe ich, dass ich eine HashMap für O (1) Lookup eines Schlüssels und eine verknüpfte Liste für die Verwaltung der "am wenigsten kürzlich verwendeten" Räumungsrichtlinie benötigt. Ich fand diese Referenzen, die alle eine Standardbibliothek hashmap verwenden, sondern ihre eigene verknüpfte Liste implementieren:

• "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)

der Hashtabelle soll, um direkt eine verknüpfte Liste Knoten speichern, wie I unten zeigen. Mein Cache sollte Integer-Schlüssel und String-Werte speichern.

jedoch in Java die LinkedList Sammlung deckt nicht seine inneren Knoten, also kann ich sie nicht in der HashMap speichern. Ich könnte stattdessen die HashMap speichern Indizes in die LinkedList, aber dann zu einem Artikel zu bekommen würde O (N) Zeit benötigen. Also habe ich versucht einen ListIterator zu speichern.

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 
    } 
} 

So führt dies zu drei Problemen:

Problem 1: Ich erhalte eine ConcurrentModificationException, wenn ich den LinkedList aktualisiere den Iterator, die ich in der HashMap speichern.

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) 

Problem 2. Wie kann ich den Wert abrufen, auf den der ListIterator zeigt? Es scheint, ich kann nur den nächsten() Wert abrufen.

Problem 3. Gibt es eine Möglichkeit, diesen LRU-Cache mithilfe der Java-Sammlungen LinkedList zu implementieren, oder muss ich wirklich meine eigene verknüpfte Liste implementieren?

Answer 1

ich mit Problem 3 zuerst beschäftigen werden:

Wie Sie in Ihrer Frage darauf hin, LinkedList (wie alle gut generische Sammlungen entworfen) verbirgt die Details der Implementierung, wie die Knoten die Links enthalten. In Ihrem Fall benötigen Sie Ihre Hash-Map, um direkt auf diese Links als Werte der Map zu verweisen. Anderenfalls (z. B. mit einer Indirektion durch eine dritte Klasse) würde der Zweck eines LRU-Caches zunichte gemacht, um einen sehr geringen Aufwand für den Wertzugriff zu ermöglichen. Dies ist jedoch mit Standard Java Collections nicht möglich - sie bieten keinen direkten Zugriff auf interne Strukturen.

Die logische Schlussfolgerung daraus ist, dass Sie ja Ihre eigene Methode zum Speichern der Reihenfolge implementieren müssen, in der Elemente im Cache verwendet wurden. Das muss keine doppelt verknüpfte Liste sein. Diese wurden traditionell für LRU-Caches verwendet, da die häufigste Operation darin besteht, einen Knoten an den Anfang der Liste zu verschieben, wenn auf ihn zugegriffen wird. Das ist eine unglaublich billige Operation in einer doppelt verketteten Liste, die nur vier Knoten erfordert, die ohne Speicherzuordnung oder frei neu verknüpft werden.

Problem 1 & 2:

Im Wesentlichen hier die Ursache ist, dass diese Sie Iteratoren zu verwenden als Cursor versuchen. Sie sind so konzipiert, dass sie erstellt werden, schrittweise durchlaufen werden, um eine Operation durchzuführen, und dann entsorgt werden. Selbst wenn Sie über die Probleme, die Sie haben, hinwegkommen, erwarte ich, dass es weitere Probleme geben wird. Sie setzen einen quadratischen Pflock in ein rundes Loch.

Also meine Schlussfolgerung ist, dass Sie Ihren eigenen Weg implementieren müssen, um Werte in einer Klasse zu halten, die die Reihenfolge des Zugriffs verfolgt. Es kann jedoch unglaublich einfach sein: Es sind nur drei Operationen erforderlich: Erstellen, Wert abrufen und aus dem Endstück entfernen. Sowohl create als auch get value müssen den Knoten an den Anfang der Liste verschieben. Kein Einfügen oder Löschen aus der Mitte der Liste. Kein Löschen des Kopfes. Keine Suche. Ganz ehrlich, tot einfach.

Hoffentlich wird Ihnen den Einstieg :-)

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) Dies ist nicht wirklich, was Iteratoren sind.

Mit Vertrag, wenn Sie die Liste ändern, ohne den Iterator - wie Sie hier tun

_list.addFirst(value);

dann ALL OPEN Iteratoren auf dieser Liste sollen ConcurrentModificationException werfen. Sie waren offen für eine Version der Liste, die nicht mehr existiert.

2) Eine LinkedList ist nicht genau eine verknüpfte Liste von Knoten. Es ist eine java.util.List, deren Backing-Implementierung eine doppelt verknüpfte Liste von Knoten ist. Dieser List-Vertrag ist der Grund, warum keine Referenzen auf die Backing-Implementierung verfügbar sind - Operationen wie "Diesen Knoten als Knoten entfernen und in den Kopf verschieben" sind also nicht gut.Diese Kapselung dient Ihrem eigenen Schutz (wie die Ausnahme für den gleichzeitigen Mod). Ihr Code kann sich auf die List-Semantik einer LinkedList (z. B. die Iterabilität) verlassen, ohne befürchten zu müssen, dass ein Joker zwei Würfel weghackt und brach den Vertrag.

3) Was Sie hier wirklich brauchen, ist KEIN LinkedList. Was Sie brauchen, ist ein Stack, mit dem Sie jeden beliebigen Eintrag zum Kopf bewegen und den Schwanz ablegen können. Sie implizieren, dass Sie eine schnelle Suchzeit zu einem beliebigen Eintrag und auch eine schnelle Entfernung und eine schnelle hinzufügen möchten, UND Sie möchten in der Lage sein, den Schwanz zu jedem Zeitpunkt zu finden, falls Sie ihn entfernen müssen.

Schnelle Suchzeit == Hash Etwas

Schnelle Hinzufügen/Entfernen von beliebigen Elementen == verlinkte Etwas

Schnelle des letzten Elements Adressierung == Somekinda Liste

4) Sie müssen Ihre eigene Verknüpfungsstruktur erstellen ... oder eine LinkedHashMap verwenden.

PS LinkedHashSet ist Betrug, es ist mit einer LinkedHashMap implementiert.

Answer 3

Eine andere Möglichkeit, diese Katze Haut würde eine sehr einfache Klasse zu implementieren, die die LinkedList erstreckt, läuft aber keine Änderungen an der Liste (zhinzufügen, entfernen usw.) innerhalb eines "synchronisierten" Blocks. Sie müssen Ihren HashMap-Pseudozeiger jedes Mal durch get() ausführen, aber es sollte gut funktionieren. z.B.

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

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

Wenn Sie Eclipse oder IntelliJ IDEA haben, dann sollten Sie in der Lage sein, die Methode Stubs Sie fast sofort brauchen, um automatisch zu generieren, und Sie können beurteilen, welche diejenigen gesperrt werden müssen.