您将如何在Java中实现LRU缓存？

Question

您将如何在Java中实现LRU缓存？

请不要说EHCache或OSCache等。为了这个问题的目的，假设我只想使用SDK（从实践中学习）来实现我自己的。鉴于缓存将在多线程环境中使用，您将使用哪些数据结构？我已经使用LinkedHashMap和Collections＃synchronizedMap实现了一个，但我很好奇任何新的并发集合是否会更好。

更新：当我发现这个金块时，我只是阅读Yegge的最新消息：

如果您需要持续时间访问并希望维护插入顺序，那么您不能比LinkedHashMap做得更好，这是一个真正精彩的数据结构。它可能更精彩的唯一方法是如果有并发版本。可惜。

在我使用上面提到的LinkedHashMap+ Collections#synchronizedMap实现之前，我的想法几乎完全相同。很高兴知道我不只是忽略了一些东西。

基于到目前为止的答案，对于高度并发的LRU来说，我最好的选择是使用一些相同的逻辑来扩展ConcurrentHashMapLinkedHashMap。

Answer 1

我喜欢很多这些建议，但现在我觉得我会坚持LinkedHashMap+&nbsp;Collections.synchronizedMap。如果我将来重新考虑这个，我可能会ConcurrentHashMap以同样的方式LinkedHashMap扩展HashMap。更新：根据要求，这是我当前实施的要点。private&nbsp;class&nbsp;LruCache<A,&nbsp;B>&nbsp;extends&nbsp;LinkedHashMap<A,&nbsp;B>&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;private&nbsp;final&nbsp;int&nbsp;maxEntries; &nbsp;&nbsp;&nbsp;&nbsp;public&nbsp;LruCache(final&nbsp;int&nbsp;maxEntries)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;super(maxEntries&nbsp;+&nbsp;1,&nbsp;1.0f,&nbsp;true); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;this.maxEntries&nbsp;=&nbsp;maxEntries; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;/** &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;Returns&nbsp;<tt>true</tt>&nbsp;if&nbsp;this&nbsp;<code>LruCache</code>&nbsp;has&nbsp;more&nbsp;entries&nbsp;than&nbsp;the&nbsp;maximum&nbsp;specified&nbsp;when&nbsp;it&nbsp;was &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;created. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;<p> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;This&nbsp;method&nbsp;<em>does&nbsp;not</em>&nbsp;modify&nbsp;the&nbsp;underlying&nbsp;<code>Map</code>;&nbsp;it&nbsp;relies&nbsp;on&nbsp;the&nbsp;implementation&nbsp;of &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;<code>LinkedHashMap</code>&nbsp;to&nbsp;do&nbsp;that,&nbsp;but&nbsp;that&nbsp;behavior&nbsp;is&nbsp;documented&nbsp;in&nbsp;the&nbsp;JavaDoc&nbsp;for &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;<code>LinkedHashMap</code>. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;</p> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;* &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@param&nbsp;eldest &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;the&nbsp;<code>Entry</code>&nbsp;in&nbsp;question;&nbsp;this&nbsp;implementation&nbsp;doesn't&nbsp;care&nbsp;what&nbsp;it&nbsp;is,&nbsp;since&nbsp;the &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;implementation&nbsp;is&nbsp;only&nbsp;dependent&nbsp;on&nbsp;the&nbsp;size&nbsp;of&nbsp;the&nbsp;cache &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@return&nbsp;<tt>true</tt>&nbsp;if&nbsp;the&nbsp;oldest &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*&nbsp;@see&nbsp;java.util.LinkedHashMap#removeEldestEntry(Map.Entry) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;*/ &nbsp;&nbsp;&nbsp;&nbsp;@Override &nbsp;&nbsp;&nbsp;&nbsp;protected&nbsp;boolean&nbsp;removeEldestEntry(final&nbsp;Map.Entry<A,&nbsp;B>&nbsp;eldest)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;super.size()&nbsp;>&nbsp;maxEntries; &nbsp;&nbsp;&nbsp;&nbsp;}}Map<String,&nbsp;String>&nbsp;example&nbsp;=&nbsp;Collections.synchronizedMap(new&nbsp;LruCache<String,&nbsp;String>(CACHE_SIZE));

Answer 2

如果我今天再次从头开始这样做，我会使用番石榴CacheBuilder。