更新存储的迭代器时出现ConcurrentModificationException异常（用于LRU缓存实现）

Question

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

从阅读有关此主题的资料中，我了解到需要一个HashMap来进行O(1)键查找和一个链表来管理“最近最少使用”驱逐策略。我找到了这些参考资料，它们都使用标准库哈希映射表，但实现了自己的链表：

中译英：

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

哈希表应直接存储如下所示的链表节点。我的缓存应存储整数键和字符串值。

然而，在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缓存，还是我真的必须实现自己的链接列表？

- stackoverflowuser2010

---

是的，你不可能让它工作。如果你想重新发明这个轮子，你将不得不手动重新实现其中至少一个数据结构。 - Louis Wasserman

Answer 1

1) 迭代器不是用来做这个的。

按照契约，如果你在不使用迭代器的情况下修改列表——就像你在这里所做的一样：

_list.addFirst(value);

那么该列表上所有打开的迭代器都应该抛出ConcurrentModificationException。它们已经打开到了一个不再存在的列表版本。

2) LinkedList不完全是一个节点的链表。它是一个java.util.List，其后备实现是一个双向节点链表。该List协议是为什么它不公开对后备实现的引用——所以“删除此节点，并将其作为节点移动到头部”等操作是无效的。这种封装是为了您自己的保护（与并发修改异常相同）——它允许您的代码依赖于LinkedList的List语义（例如可迭代性），而不必担心两个立方体之外的某个小丑正在攻击其内部并破坏协议。

3) 在这里，你真正需要的不是LinkedList。你需要的是一个栈，它允许你将任意条目移动到头部并倾倒尾部。你暗示想要快速查找任意条目、快速删除和快速添加，而且你想随时找到尾巴，以防需要删除它。

快速查找时间==HashSomething

快速添加/删除任意元素==LinkedSomething

快速寻址最后一个元素==SomekindaList

4) 您将需要构建自己的链接结构……或使用LinkedHashMap。

PS：LinkedHashSet是作弊行为，它是使用LinkedHashMap实现的。

- Matthew Mark Miller

---

谢谢。讲解得很好。 - stackoverflowuser2010

Answer 2

我先处理问题3：

正如您在问题中所指出的，LinkedList（像所有设计良好的泛型集合一样）隐藏了实现细节，例如包含链接的节点。在您的情况下，您需要哈希映射直接引用这些链接作为映射的值。否则（例如通过第三个类间接引用）将会破坏LRU缓存的目的，以允许对值访问的开销非常低。但是，这在标准Java集合中是不可能的 - 它们不应该提供对内部结构的直接访问。

因此，这个逻辑的结论是，是的，您需要自己实现一种存储缓存中使用的项目顺序的方法。那不一定是双向链表。那些传统上被用于LRU缓存，因为最常见的操作是在访问节点时将其移动到列表顶部。在双向链表中，这是一个非常便宜的操作，只需要重新链接四个节点，而无需分配或释放任何内存。

问题1和2：

基本上，根本原因在于您试图将迭代器用作游标。它们被设计为创建、通过执行某些操作并且然后处理掉。即使您克服了遇到的问题，我预计在这些问题之后还会有进一步的问题。您正在把一个方形钉子放入圆孔中。

因此，我的结论是您需要实现自己的方式来保存类中的值，以跟踪访问顺序。但是，它可以非常简单：只需要三个操作：创建、获取值和从尾部删除。创建和获取值都必须将节点移动到列表的开头。不要在列表中间插入或删除。不要删除头。不要搜索。老实说，非常简单。

希望这能帮助您入门 :-)

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
}

- sprinter

---

谢谢。现在明白了。 - stackoverflowuser2010

Answer 3

另一种解决这个问题的方法是实现一个非常简单的类，该类扩展了LinkedList，但在“同步”块内运行对列表的任何修改（例如添加、删除等）。您需要每次通过get()运行HashMap伪指针，但它应该可以正常工作。例如：

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

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

如果您使用Eclipse或IntelliJ IDEA，那么您应该能够几乎立即自动生成所需的方法存根，并且您可以评估哪些需要被锁定。

- Kieron Alsmith