使用LinkedHashMap实现LRU缓存

Question

我试图使用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}

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

Answer 1

正如Jeffrey指出的那样,您正在使用accessOrder.创建LinkedHashMap时,第三个参数指定顺序的更改方式.

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

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

Answer 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 }

Answer 3

这是我在 AccessOrder 中使用 LinkedHashMap 的实现。它将最新访问的元素移到前面，这只会产生 O(1) 开销，因为底层元素组织在双向链表中，同时也由哈希函数索引。所以 get/put/top_newest_one 操作的成本都是 O(1)。

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int maxSize;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.maxSize = capacity;
    }

    //return -1 if miss
    public int get(int key) {
        Integer v = super.get(key);
        return v == null ? -1 : v;
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return this.size() > maxSize; //must override it if used in a fixed cache
    }
}