如何实现最近使用的缓存
实现最近使用的对象缓存的最佳方法是什么？
以下是要求和限制……
- 对象存储为键/值对象/对象对，因此接口有点像Hashtable get / put
- 对“get”的调用会将该对象标记为最近使用的对象。
- 在任何时候，可以从缓存中清除最近最少使用的对象。
- 查找和清除必须快速（如在Hashtable中快）
- 对象的数量可能很大，因此列表查找不够好。
- 必须使用JavaME进行实现，因此几乎没有空间使用标准Java库中的第三方代码或整齐的库类。 出于这个原因，我正在寻找更多的算法答案而不是现成解决方案的建议。
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 。
由于锁定要求，很难构造ConcurrentLinkedHashMap。 带锁的LinkedHashMap很简单，但并不总是高效。 并发版本将尝试通过锁定拆分或理想地使CAS操作使锁定非常便宜来减少锁定量。 如果CAS操作变得昂贵，那么类似的桶拆分可能会有所帮助。 由于LRU需要对每个访问操作进行写操作，并使用双向链表，因此使用纯CAS操作实现这一点非常棘手。 我试过了，但我需要继续成熟我的算法。 如果您搜索ConcurrentLinkedHashMap，您将看到我的项目页面…
如果Java ME不支持CAS操作，我希望它是真的，那么就可以进行基本同步。 考虑到我在服务器端的高线程数上只看到了性能问题，这对于LHM来说可能已经足够了。 所以+1上面的答案。
为什么实施已经实施的东西 使用Ehcache 。
但是 ，如果第三方库完全不可能，我猜你想要实现一个如下所示的数据结构：
- 基本上是一个HashMap（如果你愿意
HashMap扩展HashMap） - Map中的每个值都指向排序列表中的对象，该列表最常用。
- 最近使用的对象被添加到列表的头部 –
O(1) - 清除最近最少使用意味着截断列表的末尾 –
O(1) - 仍然为您提供地图查找，但仍然保留最近使用的项目…
另一种方法可能是看看Brian Goetz在Java Concurrency in Practice中的5.6节：“构建一个高效，可扩展的结果缓存”。 请看一下Memoizer，尽管您可能需要根据自己的需要对其进行自定义。
另外，我无法弄清楚为什么Java没有开箱即用的ConcurrentLinkedHashMap。 此数据结构对于构建缓存非常有用。