如何实现最近使用过的缓存（MRU cache）

Question

如何实现一个最近使用的对象缓存，才是最好的方法？

以下是需求和限制条件：

• 对象以键/值 Object/Object 对形式存储，因此接口类似于 Hashtable 的 get/put。
• 调用“get”将标记该对象为最近使用的对象。
• 在任何时候，可以从缓存中清除最近未使用的对象。
• 查找和清除必须快速（就像 Hashtable 快速一样）。
• 对象数量可能很大，因此列表查找不足够快。
• 必须使用 JavaME 实现，因此几乎没有使用第三方代码或来自标准 Java 库的精简库类的余地。因此，我更注重算法解决方案，而不是现成解决方案的建议。

- izb

Answer 1

Java集合框架提供了LinkedHashMap，非常适合构建缓存。在Java ME中可能没有这个功能，但你可以在这里获取源代码：

http://kickjava.com/src/java/util/LinkedHashMap.java.htm

如果您无法直接复制-粘贴它，查看它应该可以帮助您开始实现一个用于移动应用程序的包含列表的链表。基本思想就是通过地图元素包括一个链接列表。如果您在每次进行"put"或"get"操作时更新列表，您就可以有效地跟踪访问顺序和使用顺序。

文档中包含了通过重写 removeEldestEntry(Map.Entry) 方法来构建MRU缓存的说明。您所要做的就是创建一个扩展了 LinkedHashMap 类并重写方法的类，如下所示:

private static final int MAX_ENTRIES = 100;

protected boolean removeEldestEntry(Map.Entry eldest) {
   return size() > MAX_ENTRIES;
}

还有一个constructor，它允许您指定类是按插入顺序还是按使用顺序存储内容，因此您在淘汰策略方面具有一些灵活性：

public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder)

传递true以使用顺序，传递false以使用插入顺序。

- tgamblin

---

得分了！（我正要发布同样的内容。） - Michael Myers

这看起来非常适合我一直想要实现的东西 - 谢谢！ - matt b

MRU为假，LRU为真。 - AlphaBetaGamma

SUN专有/机密 - Glenn Maynard

所描述的解决方案将是一个LRU缓存而不是MRU。 - LukasMac

Answer 2

ConcurrentLinkedHashMap由于锁定要求而难以构建。带锁的LinkedHashMap很简单，但不总是高效的。并发版本会尝试通过锁分离或理想情况下进行CAS操作来减少锁定量，使锁定变得非常便宜。如果CAS操作变得昂贵，那么类似的桶分离也会有所帮助。由于LRU需要对每个访问操作进行写入并使用双向链表，因此使用纯CAS操作实现非常棘手。我已经尝试过了，但我需要继续完善我的算法。如果您搜索ConcurrentLinkedHashMap，您将看到我的项目页面...

如果Java ME不支持CAS操作（我认为这是真的），那么基本同步就是您能做的全部。考虑到我只在服务器端的高线程计数时看到性能问题，因此这可能足够了使用LHM。所以上面的答案+1。

- Ben Manes

---

Ben: 为什么Java Collections API或Google Collections中没有ConcurrentLinkedHashMap？com.google.common.collect.CustomConcurrentHashMap.Builder有用吗？另外，你的项目很棒。请编辑你的回答并添加链接。 - Julien Chastang

Julien: CCHM非常新，不够灵活，并且似乎是他们的ReferenceMap在JBoss的Java-7 CRHM反应下的重写。它似乎主要是一个定制的CHM。我们有一个使用案例，其中锁定正在消耗系统资源，因此我只是尝试了锁分离并尝试使用CAS。 - Ben Manes

Answer 3

为什么要实现已经实现的东西呢？使用Ehcache。 然而，如果第三方库完全不可行，我想您正在寻求实现类似于以下数据结构的内容：

• 基本上是一个HashMap（如果愿意，可以扩展HashMap<Object，Object>）
• 映射中的每个值都指向排序列表中的一个对象，该列表基于最常用的对象。
• 最近使用的对象添加到列表头 - O(1)
• 清除最近未使用的对象意味着截断列表末尾 - O(1)
• 仍然提供Map查找，但仍将最近使用的项目放在首位...

- Yuval A

---

由于我之前的观点... 这个必须在移动手机上使用JavaME运行。 - izb

该算法的问题在于，虽然您可以快速在哈希映射表中查找值，但仍需要再次查找并将其移动到列表头部。 - izb

尽管在写这个的时候，我突然意识到哈希映射中的值对象可以是一个列表节点对象，可以移动到列表头部，而不是实际的值对象本身。耶 :) - izb

Answer 4

另一种方法可能是查看Brian Goetz的Java Concurrency in Practice第5.6节：“构建高效，可扩展的结果缓存”。看看Memoizer，尽管您可能需要根据自己的目的进行定制。

顺便说一下，我无法弄清楚的是为什么Java没有开箱即用的ConcurrentLinkedHashMap。这个数据结构对于构建缓存非常有帮助。

- Julien Chastang