14

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

以下是要求和限制...

  • 对象存储为键/值对象/对象对，因此接口有点像 Hashtable get/put
  • 调用“get”会将该对象标记为最近使用的对象。
  • 在任何时候，最近最少使用的对象都可以从缓存中清除。
  • 查找和清除必须快速（如在 Hashtable 中快速）
  • 对象的数量可能很大，因此列表查找不够好。
  • 必须使用 JavaME 进行实现，因此使用第三方代码或标准 Java 库中整洁的库类的余地很小。出于这个原因，我更多地寻找算法答案，而不是现成的解决方案的建议。
4

4 回答 4

24

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

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

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

removeEldestEntry(Map.Entry)文档包含通过覆盖该方法来构建 MRU 缓存的说明。您真正需要做的就是创建一个扩展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)

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

于 2009-02-24T22:31:10.167 回答
7

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

如果 Java ME 不支持 CAS 操作（我希望这是真的），那么您可以做的就是基本同步。这对于 LHM 来说可能已经足够好了，因为我只在服务器端看到了高线程数的性能问题。所以对上面的答案+1。

于 2009-02-25T01:10:15.433 回答
2

为什么要实施已经实施的东西？使用Ehcache。

但是，如果第三方库完全不可能，我猜您正在寻求实现一个看起来像这样的数据结构：

  • 基本上是一个 HashMap（HashMap<Object, Object>如果你愿意，可以扩展）
  • Map 中的每个值都指向排序列表中的一个对象，基于哪个对象最常用。
  • 最近使用的对象被添加到列表的头部 -O(1)
  • 清除最近最少使用的意味着截断列表的末尾 -O(1)
  • 仍然为您提供地图查找，但仍然首先保留最近使用的项目......
于 2009-02-24T22:19:05.890 回答
0

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

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

于 2009-02-24T22:58:22.830 回答