如何实现最最近使用的高速缓存 [英] How to implement a most-recently-used cache

问题描述

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

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

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

Here are the requirements and restrictions...

• 在对象存储为键/值对象/对象对，所以该接口将是一个有点像哈希表获取/放
• 系统调用'得到'将标志着作为最近使用的对象。
• 在任何时间，最近最少使用的对象可以被从高速缓存中清除。
• 查找并清除一定要快（如哈希表快）
• 的对象数量可能很大，所以列表查找不够好。
• 的实施必须使用JavaME的制作，所以很少有余地使用第三方code或整齐的库类从标准Ja​​va库。出于这个原因我期待更多对算法的答案，而不是场外的PEG解决方案的建议。

• 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.

推荐答案

Java集合提供的 LinkedHashMap的开箱即用，这是非常适合于构建缓存。你可能没有这个在Java ME的，但你可以在这里抓源头code：

Java Collections provide LinkedHashMap out 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:

<一个href="http://kickjava.com/src/java/util/LinkedHashMap.java.htm"><$c$c>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.

该文档包含了通过重写<一个建设一个MRU缓存的说明href="http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#removeEldestEntry%28java.util.Map.Entry%29"><$c$c>removeEldestEntry(Map.Entry)方法。你真正需要做的是使一个类，扩展的LinkedHashMap 和覆盖的方法，像这样：

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 LinkedHashMap and override the method like so:

private static final int MAX_ENTRIES = 100;

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

还有一个<一个href="http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html#LinkedHashMap%28int,%20float,%20boolean%29">constructor这使您可以指定是否要在类通过插入或通过使用存储的东西才能，让你有一点灵活性，为您的驱逐政策，也：

There's also a constructor that 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 true for use-order and false for insertion order.

这篇关于如何实现最最近使用的高速缓存的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！