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

How to implement a most-recently-used cache

提问by izb

What would be the best way to implement a most-recently-used cache of objects?

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

Here are the requirements and restrictions...

以下是要求和限制...

• Objects are stored as key/value Object/Object pairs, so the interface would be a bit like Hashtable get/put
• A call to 'get' would mark that object as the most recently used.
• At any time, the least recently used object can be purged from the cache.
• Lookups and purges must be fast (As in Hashtable fast)
• The number of Objects may be large, so list lookups are not good enough.
• The implementation must be made using JavaME, so there is little scope for using third-party code or neat library classes from the standard Java libraries.For this reason I'm looking more for algorithmic answers rather than recommendations of off-the-peg solutions.

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

回答by Todd Gamblin

Java Collections provide LinkedHashMapout of the box, which is well-suited to building caches. You probably don't have this in Java ME, but you can grab the source code here:

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

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

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

If you can't just copy-paste it, looking at it should get you started implementing one for inclusion in your mobile app. The basic idea is just to include a linked list through the map elements. If you keep this updated whenever someone does put or get, you can efficiently track access order and use order.

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

The docs contain instructions for building an MRU Cache by overriding the removeEldestEntry(Map.Entry)method. All you really have to do is make a class that extends LinkedHashMapand override the method like so:

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

private static final int MAX_ENTRIES = 100;

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

There's also a constructorthat lets you specify whether you want the class to store things in order by insertion or by use, so you've got a little flexibility for your eviction policy, too:

还有一个构造函数可让您指定是希望类按插入还是按使用顺序存储内容，因此您的驱逐策略也有一点灵活性：

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

Pass truefor use-order and falsefor insertion order.

为使用顺序传递真，为插入顺序传递假。

回答by Ben Manes

A ConcurrentLinkedHashMap is difficult to construct, due to the locking requirements. A LinkedHashMap with a lock is straightforward, but not always performant. A concurrent version would attempt to reduce the amount of locking, either by lock splitting or ideally making CAS operations to make locking very cheap. If the CAS operations ever do become expensive, then similarly bucket splitting can be helpful. As an LRU requires writes for every access operation, and uses a doubly-linked list, this is very tricky to implement with pure CAS operations. I've attempted it, but I need to continue to mature my algorithm. If you search for ConcurrentLinkedHashMap, you'll see my project page...

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

If Java ME doesn't support CAS operations, which I'd expect to be true, then basic synchronization is all you can do. This is probably good enough with a LHM, given that I've only seen performance problems at high thread count on the server-side. So +1 to the answers above.

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

回答by Yuval Adam

Why implement something already implemented? Use Ehcache.

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

However, if third-party libraries are totally out of the question, I guess you are looking to implement a data structure which looks something like this:

但是，如果完全不可能使用第三方库，我猜您正在寻找实现如下所示的数据结构：

• Basically is a HashMap (extends HashMap<Object, Object>if you will)
• Each value in the Map points to an object in a sorted list, based on which is most used.
• Objects recently used are added to the head of the list - O(1)
• Purging least-recently used means truncating the end of the list - O(1)
• Still gives you Map lookups, but still keeps recently-used items first...

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

回答by Julien Chastang

Another approach may be to take a look at section 5.6 in Java Concurrency in Practiceby Brian Goetz: "Building an efficient, scalable result cache". Take a look at the Memoizer, although you may have to customize it for your purposes.

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

As an aside, what I cannot figure out is why Java does not have a ConcurrentLinkedHashMap out of the box. This data structure would be very helpful for building a cache.

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