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

通过阅读本主题，我了解到我需要一个用于 O(1) 查找键的 HashMap 和一个用于管理“最近最少使用”逐出策略的链表。我发现这些引用都使用标准库 hashmap 但实现了自己的链表:

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

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

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

最佳答案

1) 这并不是迭代器的真正用途。

根据约定，如果您在不使用迭代器的情况下修改列表——就像您在此处所做的那样

_list.addFirst(value);

然后该列表上的所有打开的迭代器都应该抛出 ConcurrentModificationException。他们对不再存在的列表版本持开放态度。

2) LinkedList 不完全是节点的链表。它是一个 java.util.List，其支持实现是节点的双向链表。那个 List 契约是它不公开对支持实现的引用的原因——所以像“删除这个节点，作为一个节点，并将它移到头部”这样的操作是不好的。这种封装是为了您自己的保护(与并发 mod 异常相同)——它允许您的代码依赖于 LinkedList 的 List 语义(例如，可迭代性)，而不必担心两个立方体之外的一些 clown 正在破解它的内部结构并毁约。

3) 这里你真正需要的不是链表。您需要的是一个堆栈，它允许您将任意条目移动到头部并转储尾部。您是在暗示您想要快速查找任意条目以及快速删除和快速添加，并且您希望能够在任何时候找到尾部，以防您需要删除它。

快速寻道时间 == HashSomething

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

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

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

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

关于java - 更新存储迭代器时的ConcurrentModificationException(用于LRU缓存实现)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36379741/