java - MRU缓存实现

Question

我不明白这是 LRU 缓存实现:

// LRU cache -----------------------------------------------------------------
private static final Map cacheLRU = Collections.synchronizedMap(new LinkedHashMap(MAX, 0.75f, 
        true/*true for access-order, false for insertion-order.*/) {
    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {
        return size() > MAX;
    };
});

static void cacheLRUTest(){
    cacheLRU.put ("1", "one");                           // 1
    cacheLRU.put ("2", "two");                           // 2 1
    cacheLRU.put ("3", "three");                         // 3 2 1
    cacheLRU.put ("4", "four");                          // 4 3 2
       if (cacheLRU.get("2") == null) throw new Error();    // 2 4 3
       cacheLRU.put ("5", "five");                          // 5 2 4
       cacheLRU.put ("4", "second four");                   // 4 5 2
       // Verify cache content.
       if (cacheLRU.size() != 3)              throw new Error();
       if (!cacheLRU.get("4").equals("second four")) throw new Error();
       if (!cacheLRU.get("5").equals("five"))        throw new Error();
       if (!cacheLRU.get("2").equals("two"))         throw new Error();

}

如何使用 LinkedHashMap 实现 MRU 缓存算法？

更新:

http://javalandscape.blogspot.com/2009/01/cachingcaching-algorithms-and-caching.html

正如我所理解的:LRU - 如果缓存已满，我需要删除 lru 项目，MRU - ... mru 项目

Answer 1

好的，我很抱歉 - 我什至不知道 MRU 是一个有效的散列方案，所以很抱歉我对这个问题的原始评论。

无论如何，使用 LinkedHashMap 实现一个所需要做的就是将项目存储在 map 中，当该数量超过某个限制时，丢弃最新的。您可以轻松做到这一点，因为 LinkedHashMap 包含访问顺序的记录。所以你需要做两件事:

使用允许您指定排序模式和请求访问顺序的构造函数创建 LinkedHashMap(因为您希望排序反射(reflect)访问以及添加)。

在插入时，当大小达到限制时，通过键上的迭代器找到列表中的第一个键，并将其删除。