Java LRUCache，为什么我们需要另一个集合

Question

我正在阅读这篇文章来了解 Java 中的 LRUCache - Java LRU cache using LinkedList

这篇文章中有一个解决方案:

public class LRUCache {

    private Map<Integer, Integer> blocks = new HashMap<Integer, Integer>();
    private LinkedList<Integer> bru = new LinkedList<Integer>();
    private int capacity;
    private int length;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.length = 0;
    }

    public int get(int key) {
        Integer value = blocks.get(key);
        if (value != null) {
            bru.remove(value);
            bru.addFirst(value);
            return value;
        }
        return -1;
    }

    public void set(int key, int value) {
        if (blocks.containsKey(key)) {
            bru.remove(blocks.get(key));
            blocks.put(key, value);
        } else {
            if (length >= capacity) {
                blocks.remove(bru.removeLast());
                length--;
            }

            length++;
            blocks.put(key, value);
        }
        bru.addFirst(value);
    }
}

在此程序中，blocks 映射是保存所需值的实际映射。那么为什么我们需要另一个集合 bru LinkedList 呢？

Answer 1

Map<Integer, Integer> blocks是保存所需值的实际值，

同时LinkedList<Integer> bru用于存储最近访问值。