使用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}

这表明重新插入的内容影响了顺序。有人知道任何解释吗？

- Lei Chen

---

WeakHashMap并不像你想的那样工作。它与LRU缓存不是同一种东西。请参考此链接获取更多信息：https://dev59.com/wW035IYBdhLWcg3wSN-r - Jeffrey

@Jeffrey：它确实做到了我想要的功能。它提供了一种数据结构，允许存储缓存值，而无需担心如果它们在代码中没有被引用，则清除它们。这是一种垃圾回收的方式来实现LRU缓存。如果您没有清除旧值的要求（为了刷新问题，这就是我所说的“特定目的”），那么它正好通过允许Java在有必要时释放它们来满足这个问题。 - Jack

@Jack 我在实践编码时正在实现这个。我认为，如果我使用 weakHashMap 来保存临时对象并让 GC 处理一切，那么使用 LRU 是一个更好的方法。谢谢。 - Lei Chen

如何实现LRU版本：https://dev59.com/dGAg5IYBdhLWcg3wSpTD#34206517 - Ciro Santilli OurBigBook.com

@Jack 垃圾回收并不等同于最近最少使用的缓存驱逐策略。 - user207421

Answer 1

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

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

如果您想了解更详细的LRU实现，请查看此链接http://www.programcreek.com/2013/03/leetcode-lru-cache-java/

- 1736964698

---

该链接并未使用带有LinkedHashMap的解决方案。 - seeker

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 }

- Jeffrey

---

最后一行的2去哪了？ - Mateen Ulhaq

LRUCache 只有容量为 2 的元素。由于 2 是最近最少使用的元素，当我们添加 3 时，它被推出了缓存。 - Jeffrey

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

- Emilio Zhao

---

“固定缓存”是什么意思？在这个上下文中有哪些缓存？ - piepi

Answer 4

技术上，LinkedHashMap有以下构造函数。它可以帮助我们设置访问顺序是否为True/False。如果为false，则将保留插入顺序。

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

(#Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode)

以下是LRU Cache的简单实现---

  class LRUCache {

     private LinkedHashMap<Integer, Integer> linkHashMap;

     public LRUCache(int capacity) {
        linkHashMap = new LinkedHashMap<Integer, Integer>(capacity, 0.75F, true) {
          @Override
          protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
             return size() > capacity;
          }
       };
     }

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

     public int get(int key) {
       return linkHashMap.getOrDefault(key, -1);
     }

 } 

- Numery

Answer 5

我使用了以下代码并且它能正常工作！！！我将窗口大小设置为4，但是可以取任何值。

对于插入顺序：
1：检查键是否存在。

2：如果是，则删除它（使用lhm.remove(key)）。

3：添加新的键值对。

对于访问顺序：

无需删除键，只需使用put和get语句即可自动完成所有操作。

这段代码是用于访问顺序的。

"最初的回答"

import java.util.LinkedHashMap;

public class LRUCacheDemo {

 public static void main(String args[]){

  LinkedHashMap<String,String> lhm = new LinkedHashMap<String,String>(4,0.75f,true) {

     @Override
     protected boolean removeEldestEntry(Map.Entry<String,String> eldest) {
         return size() > 4;
     }
 };
 lhm.put("test", "test");
 lhm.put("test1", "test1");
 lhm.put("1", "abc");
 lhm.put("test2", "test2");
 lhm.put("1", "abc");
 lhm.put("test3", "test3");
 lhm.put("test4", "test4");
 lhm.put("test3", "test3");
 lhm.put("1", "abc");
 lhm.put("test1", "test1");

 System.out.println(lhm);
}
}

- Shrey Suri

Answer 6

I also implement LRU cache with little change in code. I have tested and it works perfectly as concept of LRU cache.

package com.first.misc;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCachDemo {
 public static void main(String aa[]){
     LRUCache<String, String> lruCache = new LRUCache<>(3);
     lruCache.cacheable("test", "test");
     lruCache.cacheable("test1", "test1");
     lruCache.cacheable("test2", "test2");
     lruCache.cacheable("test3", "test3");
     lruCache.cacheable("test4", "test4");
     lruCache.cacheable("test", "test");


     System.out.println(lruCache.toString());
 }
}

class LRUCache<K, T>{
    private Map<K,T> cache;
    private int windowSize;

    public LRUCache( final int windowSize) {
        this.windowSize = windowSize;
        this.cache = new LinkedHashMap<K, T>(){

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

    }


    // put data in cache
    public void cacheable(K key, T data){
        // check key is exist of not if exist than remove and again add to make it recently used
        // remove element if window size is exhaust
        if(cache.containsKey(key)){
            cache.remove(key);
        }

        cache.put(key,data);

    }

    // evict functioanlity

    @Override
    public String toString() {
        return "LRUCache{" +
                "cache=" + cache.toString() +
                ", windowSize=" + windowSize +
                '}';
    }
}

- Rajeev Rathor