java - 如何实现最近使用的缓存

Question

实现最近使用的对象缓存的最佳方法是什么？

这是要求和限制...

• 对象存储为键/值对象/对象对，因此接口(interface)有点像 Hashtable get/put
• 调用“get”会将该对象标记为最近使用过的对象。
• 可以随时从缓存中清除最近最少使用的对象。
• 查找和清除必须很快(就像在 Hashtable 中一样快)
• 对象的数量可能很大，因此列表查找不够好。
• 实现必须使用 JavaME 进行，因此使用第三方代码或标准 Java 库中简洁的库类的范围很小。因此，我更多地寻找算法答案而不是现成解决方案的建议。

Answer 1

Java 集合提供 LinkedHashMap开箱即用，非常适合构建缓存。您可能在 Java ME 中没有这个，但您可以在此处获取源代码:

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

如果您不能只是复制粘贴它，查看它应该可以让您开始实现一个以包含在您的移动应用程序中。基本思想只是通过 map 元素包含一个链表。如果您在有人放置或获取时保持更新，您可以有效地跟踪访问顺序和使用顺序。

文档包含通过覆盖 removeEldestEntry(Map.Entry) 构建 MRU 缓存的说明方法。您真正需要做的就是创建一个扩展 LinkedHashMap 的类并覆盖该方法，如下所示:

private static final int MAX_ENTRIES = 100;

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

还有一个 constructor这使您可以指定是希望类按插入顺序还是按使用顺序存储内容，因此您的驱逐策略也有一点灵 active :

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

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