并发模式更新存储迭代器时的异常（用于 LRU 缓存实现）

我正在尝试实现自己的 LRU 缓存。是的，我知道Java为此目的提供了一个LinkedHashMap，但我正在尝试使用基本数据结构来实现它。

通过阅读有关此主题的信息，我了解到我需要一个用于O（1）的HashMap查找密钥和一个链接列表，用于管理“最近最少使用”的驱逐策略。我发现这些引用都使用标准库哈希映射，但实现了自己的链表：

• "LRU缓存和快速定位对象通常使用哪些数据结构？（stackoverflow.com）
• "实现 LRU 缓存的最佳方法是什么？（quora.com）
• "在C++中实现 LRU 缓存“（uml.edu）
• "LRU Cache （Java）“ （programcreek.com）

哈希表应该直接存储一个链接列表Node，如下所示。我的缓存应该存储整数键和字符串值。

但是，在Java中，LinkedList集合不会公开其内部节点，因此我无法将它们存储在HashMap中。相反，我可以将HashMap存储索引放入LinkedList中，但是要获得一个项目将需要O（N）时间。所以我尝试存储一个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
    }
}

因此，这导致了三个问题：

问题 1：当我使用存储在 HashMap 中的迭代器更新 LinkedList 时，我得到了一个 ConcurrentModificationException。

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)

问题 2.如何检索 ListIterator 指向的值？似乎我只能检索 next（） 值。

问题 3.有没有办法使用Java集合LinkedList实现这个LRU缓存，或者我真的必须实现我自己的链表吗？