如何实现最近使用的缓存

algorithm caching java java-me mru

2022-09-03 17:47:03

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

以下是要求和限制...

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

答案 1

Java Collections提供开箱即用的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 传递到广告订单。

答案 2

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

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