使用LinkedHashMap实现LRU缓存

insert java linkedhashmap lru

2022-09-01 10:51:39

我试图使用LinkedHashMap实现LRU缓存。在LinkedHashMap（http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html）的文档中，它说：

请注意，如果将键重新插入到地图中，广告订单不受影响。

但是当我做以下推杆时

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private int size;

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 1);
        cache.put(3, 3);

        System.out.println(cache);
    }

    private LRUCache(int size) {
        super(size, 0.75f, true);
        this.size = size;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > size;
    }

    public static <K, V> LRUCache<K, V> newInstance(int size) {
        return new LRUCache<K, V>(size);
    }

}

输出为

{1=1, 3=3}

这表明重新插入的确实影响了订单。有人知道任何解释吗？

答案 1

正如 Jeffrey 所指出的，您正在使用 accessOrder。创建 LinkedHashMap 时，第三个参数指定如何更改顺序。

"true for access-order, false for insertion-order"

有关 LRU 的更详细实现，可以查看此 http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

答案 2

但您使用的不是广告订单，而是访问顺序。

迭代顺序是上次访问其条目的顺序，从最近访问到最近访问（访问顺序）

...

调用 put 或 get 方法会导致访问相应的条目

因此，这是您修改缓存时缓存的状态：

    LRUCache<Integer, Integer> cache = LRUCache.newInstance(2);
    cache.put(1, 1); // { 1=1 }
    cache.put(2, 2); // { 1=1, 2=2 }
    cache.put(1, 1); // { 2=2, 1=1 }
    cache.put(3, 3); // { 1=1, 3=3 }