如何实现最近使用的缓存

Question

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

以下是要求和限制......

• 对象存储为键/值对象/对象对,因此接口有点像Hashtable get/put
• 对"get"的调用会将该对象标记为最近使用的对象.
• 在任何时候,可以从缓存中清除最近最少使用的对象.
• 查找和清除必须快速(如在快速哈希表中)
• 对象的数量可能很大,因此列表查找不够好.
• 必须使用JavaME进行实现,因此使用标准Java库中的第三方代码或整齐的库类几乎没有空间.出于这个原因,我正在寻找更多的算法答案而不是现成解决方案的建议.

Answer 1

Java Collections提供了开箱即用的LinkedHashMap,非常适合构建缓存.你可能在Java ME中没有这个,但你可以在这里获取源代码:

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

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

文档包含通过覆盖removeEldestEntry(Map.Entry)方法构建MRU Cache的说明.你真正需要做的就是创建一个扩展LinkedHashMap和覆盖方法的类,如下所示:

private static final int MAX_ENTRIES = 100;

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

还有一个构造函数,允许您指定是否希望类通过插入或使用按顺序存储内容,因此您对驱逐策略也有一点灵活性:

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

对于use-order 传递true,对于插入顺序传递false.

Answer 2

由于锁定要求,很难构造ConcurrentLinkedHashMap.带锁的LinkedHashMap很简单,但并不总是高效.并发版本将尝试通过锁定拆分或理想地使CAS操作使锁定非常便宜来减少锁定量.如果CAS操作变得昂贵,那么类似的桶拆分可能会有所帮助.由于LRU需要对每个访问操作进行写操作,并使用双向链表,因此使用纯CAS操作实现这一点非常棘手.我试过了,但我需要继续成熟我的算法.如果您搜索ConcurrentLinkedHashMap,您将看到我的项目页面...

如果Java ME不支持CAS操作,我希望它是真的,那么就可以进行基本同步.鉴于我在服务器端只看到高线程数的性能问题,这对于LHM来说可能已经足够了.所以+1上面的答案.