你将如何在Java中实现一个LRUcaching？

请不要说EHCache或OSCache等。为了这个问题的目的，假设我想使用SDK来实现我自己的（边干边学）。 鉴于caching将在multithreading环境中使用，您将使用哪种数据结构？ 我已经实现了一个使用LinkedHashMap和Collections＃synchronizedMap ，但我很好奇，如果任何新的并发集合将是更好的候选人。

更新：当我发现这块金块时，我正在阅读Yegge的最新消息 ：

如果你需要恒定的访问时间并且想维护插入顺序，那么你不能比LinkedHashMap做得更好，这是一个非常棒的数据结构。 如果有一个并发版本，唯一可能更好的方法是。 可惜。

在我使用上面提到的LinkedHashMap + Collections#synchronizedMap实现之前，我正在考虑几乎完全一样的事情。 很高兴知道我不只是忽略了一些东西。

根据目前的答案，这听起来像是我最好的select，高度并发的LRU将使用LinkedHashMap使用的一些相同的逻辑来扩展ConcurrentHashMap 。

Answer 1

我喜欢这些build议，但现在我想坚持LinkedHashMap + Collections.synchronizedMap 。 如果将来我会重新讨论这个问题，那么我可能会使用LinkedHashMap扩展HashMap方式来扩展ConcurrentHashMap 。

更新：

根据要求，这是我目前实施的要点。

 private class LruCache<A, B> extends LinkedHashMap<A, B> { private final int maxEntries; public LruCache(final int maxEntries) { super(maxEntries + 1, 1.0f, true); this.maxEntries = maxEntries; } /** * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was * created. * * <p> * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for * <code>LinkedHashMap</code>. * </p> * * @param eldest * the <code>Entry</code> in question; this implementation doesn't care what it is, since the * implementation is only dependent on the size of the cache * @return <tt>true</tt> if the oldest * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry) */ @Override protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) { return super.size() > maxEntries; } } Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE)); 

Answer 2

或者使用这个Apache Commons数据结构：

https://commons.apache.org/proper/commons-collections//javadocs/api-3.2.1/org/apache/commons/collections/LRUMap.html

Answer 3

如果我今天从头开始，我会使用番石榴的CacheBuilder 。

Answer 4

这是第二轮。

第一轮是我想到的，然后我重读了这个域名的意见，让我头脑里更加根深蒂固。

所以这里是最简单的版本，用unit testing来显示它是基于其他版本的。

首先是非并发版本：

 import java.util.LinkedHashMap; import java.util.Map; public class LruSimpleCache<K, V> implements LruCache <K, V>{ Map<K, V> map = new LinkedHashMap ( ); public LruSimpleCache (final int limit) { map = new LinkedHashMap <K, V> (16, 0.75f, true) { @Override protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) { return super.size() > limit; } }; } @Override public void put ( K key, V value ) { map.put ( key, value ); } @Override public V get ( K key ) { return map.get(key); } //For testing only @Override public V getSilent ( K key ) { V value = map.get ( key ); if (value!=null) { map.remove ( key ); map.put(key, value); } return value; } @Override public void remove ( K key ) { map.remove ( key ); } @Override public int size () { return map.size (); } public String toString() { return map.toString (); } } 

真正的国旗将跟踪获取和放置的访问。 请参阅JavaDocs。 不带真标志的removeEdelstEntry只能实现一个FIFOcaching（参见下面关于FIFO和removeEldestEntry的注释）。

以下是certificate其作为LRUcaching的testing：

 public class LruSimpleTest { @Test public void test () { LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); cache.put ( 4, 4 ); cache.put ( 5, 5 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); if ( !ok ) die (); } 

现在的并发版本…

包org.boon.cache;

 import java.util.LinkedHashMap; import java.util.Map; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> { final CacheMap<K, V>[] cacheRegions; private static class CacheMap<K, V> extends LinkedHashMap<K, V> { private final ReadWriteLock readWriteLock; private final int limit; CacheMap ( final int limit, boolean fair ) { super ( 16, 0.75f, true ); this.limit = limit; readWriteLock = new ReentrantReadWriteLock ( fair ); } protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) { return super.size () > limit; } @Override public V put ( K key, V value ) { readWriteLock.writeLock ().lock (); V old; try { old = super.put ( key, value ); } finally { readWriteLock.writeLock ().unlock (); } return old; } @Override public V get ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.get ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } @Override public V remove ( Object key ) { readWriteLock.writeLock ().lock (); V value; try { value = super.remove ( key ); } finally { readWriteLock.writeLock ().unlock (); } return value; } public V getSilent ( K key ) { readWriteLock.writeLock ().lock (); V value; try { value = this.get ( key ); if ( value != null ) { this.remove ( key ); this.put ( key, value ); } } finally { readWriteLock.writeLock ().unlock (); } return value; } public int size () { readWriteLock.readLock ().lock (); int size = -1; try { size = super.size (); } finally { readWriteLock.readLock ().unlock (); } return size; } public String toString () { readWriteLock.readLock ().lock (); String str; try { str = super.toString (); } finally { readWriteLock.readLock ().unlock (); } return str; } } public LruSimpleConcurrentCache ( final int limit, boolean fair ) { int cores = Runtime.getRuntime ().availableProcessors (); int stripeSize = cores < 2 ? 4 : cores * 2; cacheRegions = new CacheMap[ stripeSize ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) { cacheRegions = new CacheMap[ concurrency ]; for ( int index = 0; index < cacheRegions.length; index++ ) { cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair ); } } private int stripeIndex ( K key ) { int hashCode = key.hashCode () * 31; return hashCode % ( cacheRegions.length ); } private CacheMap<K, V> map ( K key ) { return cacheRegions[ stripeIndex ( key ) ]; } @Override public void put ( K key, V value ) { map ( key ).put ( key, value ); } @Override public V get ( K key ) { return map ( key ).get ( key ); } //For testing only @Override public V getSilent ( K key ) { return map ( key ).getSilent ( key ); } @Override public void remove ( K key ) { map ( key ).remove ( key ); } @Override public int size () { int size = 0; for ( CacheMap<K, V> cache : cacheRegions ) { size += cache.size (); } return size; } public String toString () { StringBuilder builder = new StringBuilder (); for ( CacheMap<K, V> cache : cacheRegions ) { builder.append ( cache.toString () ).append ( '\n' ); } return builder.toString (); } } 

你可以看到为什么我先覆盖非并发版本。 以上尝试创build一些条纹来减less锁争用。 所以我们把密钥哈希，然后查找哈希来find实际的caching。 这使得极限大小更多的是在相当大的误差范围内的build议/粗略猜测，具体取决于你的密钥散列algorithm的散布程度。

这里是testing显示并发版本可能工作。 :)（testing下的火将是真正的方式）。

 public class SimpleConcurrentLRUCache { @Test public void test () { LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); cache.put ( 4, 4 ); cache.put ( 5, 5 ); puts (cache); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); cache.put ( 8, 8 ); cache.put ( 9, 9 ); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); puts (cache); if ( !ok ) die (); } @Test public void test2 () { LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); for (int index =0 ; index < 5_000; index++) { cache.get(0); cache.get ( 1 ); cache.put ( 2, index ); cache.put ( 3, index ); cache.put(index, index); } boolean ok = cache.getSilent ( 0 ) == 0 || die (); ok |= cache.getSilent ( 1 ) == 1 || die (); ok |= cache.getSilent ( 2 ) != null || die (); ok |= cache.getSilent ( 3 ) != null || die (); ok |= cache.size () < 600 || die(); if ( !ok ) die (); } } 

这是最后一个post..我删除的第一篇文章，因为它是一个LFU而不是一个LRUcaching。

我想我会再去这个。 我试图用标准的JDK来实现最简单的LRUcaching版本。

这是我想出来的。 我的第一次尝试是在执行一个LFU而不是LRU的同时，我又加了一个FIFO，然后我join了FIFO和LRU支持，然后我意识到它变成了一个怪物。 然后我开始和我刚刚感兴趣的朋友约翰谈话，然后深入介绍我是如何实现一个LFU，LRU和FIFO的，以及如何用一个简单的ENUM arg来切换它，然后我意识到我真正想要的是一个简单的LRU。 因此，忽略从我以前的post，让我知道，如果你想看到一个LRU / LFU / FIFOcaching可切换通过枚举…不？ 好吧，在这里他走了。

使用JDK的最简单的LRU。 我实现了并发版本和非并发版本。

我创build了一个通用接口（这是极简主义，所以很可能会缺less一些你想要的function，但是它适用于我的用例，但是如果你希望看到functionXYZ让我知道…我活着写代码）。 。

 public interface LruCache<KEY, VALUE> { void put ( KEY key, VALUE value ); VALUE get ( KEY key ); VALUE getSilent ( KEY key ); void remove ( KEY key ); int size (); } 

你可能想知道getSilent是什么。 我用这个进行testing。 getSilent不会更改某个项目的LRU分数。

首先是非并发的…

 import java.util.Deque; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> { Map<KEY, VALUE> map = new HashMap<> (); Deque<KEY> queue = new LinkedList<> (); final int limit; public LruCacheNormal ( int limit ) { this.limit = limit; } public void put ( KEY key, VALUE value ) { VALUE oldValue = map.put ( key, value ); /*If there was already an object under this key, then remove it before adding to queue Frequently used keys will be at the top so the search could be fast. */ if ( oldValue != null ) { queue.removeFirstOccurrence ( key ); } queue.addFirst ( key ); if ( map.size () > limit ) { final KEY removedKey = queue.removeLast (); map.remove ( removedKey ); } } public VALUE get ( KEY key ) { /* Frequently used keys will be at the top so the search could be fast.*/ queue.removeFirstOccurrence ( key ); queue.addFirst ( key ); return map.get ( key ); } public VALUE getSilent ( KEY key ) { return map.get ( key ); } public void remove ( KEY key ) { /* Frequently used keys will be at the top so the search could be fast.*/ queue.removeFirstOccurrence ( key ); map.remove ( key ); } public int size () { return map.size (); } public String toString() { return map.toString (); } } 

如果您有一个大的caching， queue.removeFirstOccurrence是一个潜在的昂贵的操作。 可以以LinkedList为例，并添加一个从元素到节点的反向查找哈希映射，使删除操作更快速，更一致。 我也开始了，但后来意识到我不需要它。 但是…也许…

put被调用时，密钥被添加到队列中。 get被调用时，键被移除并重新添加到队列顶部。

如果你的caching很小，build设一个项目是昂贵的，那么这应该是一个很好的caching。 如果你的caching真的很大，那么线性search可能是一个瓶颈，特别是如果你没有caching的热点地区。 热点越激烈，线性search越快，因为热点项目总是处于线性search的顶部。 无论如何…这需要更快的是写另一个链接列表有一个删除操作，具有逆向元素的节点查找删除，然后删除将一样快，从一个哈希映射中删除一个键。

如果你有一个caching在1000个项目下，这应该工作得很好。

这是一个简单的testing，以显示其操作的行动。

 public class LruCacheTest { @Test public void test () { LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 ); cache.put ( 0, 0 ); cache.put ( 1, 1 ); cache.put ( 2, 2 ); cache.put ( 3, 3 ); boolean ok = cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 0 ) == 0 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); cache.put ( 4, 4 ); cache.put ( 5, 5 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 0 ) == null || die (); ok |= cache.getSilent ( 1 ) == null || die (); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == 4 || die (); ok |= cache.getSilent ( 5 ) == 5 || die (); if ( !ok ) die (); } } 

最后一个LRUcaching是单线程的，请不要将它包装在一个同步的东西….

这是一个并发版本的刺戳。

 import java.util.Deque; import java.util.LinkedList; import java.util.Map; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.locks.ReentrantLock; public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> { private final ReentrantLock lock = new ReentrantLock (); private final Map<KEY, VALUE> map = new ConcurrentHashMap<> (); private final Deque<KEY> queue = new LinkedList<> (); private final int limit; public ConcurrentLruCache ( int limit ) { this.limit = limit; } @Override public void put ( KEY key, VALUE value ) { VALUE oldValue = map.put ( key, value ); if ( oldValue != null ) { removeThenAddKey ( key ); } else { addKey ( key ); } if (map.size () > limit) { map.remove ( removeLast() ); } } @Override public VALUE get ( KEY key ) { removeThenAddKey ( key ); return map.get ( key ); } private void addKey(KEY key) { lock.lock (); try { queue.addFirst ( key ); } finally { lock.unlock (); } } private KEY removeLast( ) { lock.lock (); try { final KEY removedKey = queue.removeLast (); return removedKey; } finally { lock.unlock (); } } private void removeThenAddKey(KEY key) { lock.lock (); try { queue.removeFirstOccurrence ( key ); queue.addFirst ( key ); } finally { lock.unlock (); } } private void removeFirstOccurrence(KEY key) { lock.lock (); try { queue.removeFirstOccurrence ( key ); } finally { lock.unlock (); } } @Override public VALUE getSilent ( KEY key ) { return map.get ( key ); } @Override public void remove ( KEY key ) { removeFirstOccurrence ( key ); map.remove ( key ); } @Override public int size () { return map.size (); } public String toString () { return map.toString (); } } 

主要区别是使用ConcurrentHashMap而不是HashMap，并且使用Lock（我可以使用synchronized，但是…）。

我还没有经过testing，但似乎是一个简单的LRUcaching，在80％的需要一个简单的LRU映射的用例中可能会出现这种情况。

我欢迎反馈，除了为什么不使用库a，b或c。 我不总是使用库的原因是因为我并不总是希望每个war文件都是80MB，所以我编写库，所以我倾向于使libs可以插入足够好的解决scheme，并且有人可以插入在另一个caching提供者，如果他们喜欢。 :)我永远不知道什么时候有人可能需要番石榴或ehcache或其他我不想包括他们，但如果我做caching插件，我不会排除他们。

减less依赖关系有其自身的好处。 我喜欢得到一些关于如何使这个更简单或者更快的反馈。

另外，如果有人知道准备去….

好吧..我知道你在想什么……为什么他不使用LinkedHashMap中的removeEldest入口，以及我应该，但是……但..但是..这将是一个FIFO不是一个LRU，我们是试图实现一个LRU。

  Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () { @Override protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) { return this.size () > limit; } }; 

以上代码的testing失败…

  cache.get ( 2 ); cache.get ( 3 ); cache.put ( 6, 6 ); cache.put ( 7, 7 ); ok |= cache.size () == 4 || die ( "size" + cache.size () ); ok |= cache.getSilent ( 2 ) == 2 || die (); ok |= cache.getSilent ( 3 ) == 3 || die (); ok |= cache.getSilent ( 4 ) == null || die (); ok |= cache.getSilent ( 5 ) == null || die (); 

所以这里是一个使用removeEldestEntry的快速而脏的FIFOcaching。

 import java.util.*; public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> { final int limit; Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () { @Override protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) { return this.size () > limit; } }; public LruCacheNormal ( int limit ) { this.limit = limit; } public void put ( KEY key, VALUE value ) { map.put ( key, value ); } public VALUE get ( KEY key ) { return map.get ( key ); } public VALUE getSilent ( KEY key ) { return map.get ( key ); } public void remove ( KEY key ) { map.remove ( key ); } public int size () { return map.size (); } public String toString() { return map.toString (); } } 

FIFOs速度很快。 没有四处搜寻。 你可以在一个LRU前面放一个FIFO，这样可以很好地处理大多数热门的项目。 一个更好的LRU将需要与Node特性相反的元素。

无论如何…现在我写了一些代码，让我通过其他答案，看看我错过了什么…我第一次扫描他们。

Answer 5

LinkedHashMap是O（1），但需要同步。 没有必要在那里重新发明轮子。

增加并发的2个选项：

1.创build多个LinkedHashMap ，并对其进行散列：例如： LinkedHashMap[4], index 0, 1, 2, 3 。 在键的key%4 （或[key, 3]上的binary OR ）来select要执行put / get / remove的映射。

2.你可以通过扩展ConcurrentHashMap来完成一个'几乎'的LRU，并且在其内部的每个区域都有一个类似结构的链接哈希映射。 locking会比同步的LinkedHashMap更精细地发生。 在put或putIfAbsent只需要在列表的putIfAbsent一个锁（每个区域）。 在一个删除或得到整个地区需要被locking。 我很好奇，如果primefaces链表可能有帮助 – 可能是这样的名单的头。 也许更多。

结构不会保持总的顺序，但只有每个区域的顺序。 只要条目的数量远远大于区域的数量，这对于大多数caching来说已经足够好了。 每个地区将不得不有自己的入场点数，这将被用于驱逐触发器的全球计数。 ConcurrentHashMap默认的区域数量是16，这对今天的大多数服务器来说都是很多的。

1. 在适度并发的情况下写起来会更容易，速度更快。

2. 编写起来会比较困难，但是在非常高的并发性上要好得多。 正常访问会慢（就像ConcurrentHashMap比没有并发的HashMap慢）

Answer 6

有两个开源实现。

Apache Solr具有ConcurrentLRUCache： https ： //lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

ConcurrentLinkedHashMap有一个开源项目： http : //code.google.com/p/concurrentlinkedhashmap/

Answer 7

我会考虑使用java.util.concurrent.PriorityBlockingQueue ，优先级由每个元素中的“numberOfUses”计数器决定。 我会非常非常小心地让所有同步都正确，因为“numberOfUses”计数器意味着该元素不能是不可变的。

元素对象将是caching中的对象的包装：

 class CacheElement { private final Object obj; private int numberOfUsers = 0; CacheElement(Object obj) { this.obj = obj; } ... etc. } 

Answer 8

LRUcaching可以使用ConcurrentLinkedQueue和一个可以在multithreading场景中使用的ConcurrentHashMap来实现。 队列头是最长时间在队列中的元素。 队列的尾部是已经在队列上的元素的最短时间。 当Map中存在一个元素时，我们可以将它从LinkedQueue中移除并将其插入尾部。

 import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedQueue; public class LRUCache<K,V> { private ConcurrentHashMap<K,V> map; private ConcurrentLinkedQueue<K> queue; private final int size; public LRUCache(int size) { this.size = size; map = new ConcurrentHashMap<K,V>(size); queue = new ConcurrentLinkedQueue<K>(); } public V get(K key) { //Recently accessed, hence move it to the tail queue.remove(key); queue.add(key); return map.get(key); } public void put(K key, V value) { //ConcurrentHashMap doesn't allow null key or values if(key == null || value == null) throw new NullPointerException(); if(map.containsKey(key) { queue.remove(key); } if(queue.size() >= size) { K lruKey = queue.poll(); if(lruKey != null) { map.remove(lruKey); } } queue.add(key); map.put(key,value); } } 

Answer 9

希望这可以帮助 。

 import java.util.*; public class Lru { public static <K,V> Map<K,V> lruCache(final int maxSize) { return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) { private static final long serialVersionUID = -3588047435434569014L; @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return size() > maxSize; } }; } public static void main(String[] args ) { Map<Object, Object> lru = Lru.lruCache(2); lru.put("1", "1"); lru.put("2", "2"); lru.put("3", "3"); System.out.println(lru); } } 

Answer 10

这是我的LRU的实现。 我已经使用PriorityQueue，基本上作为FIFO而不是线程安全。 使用基于页面时间创build的比较器，并基于最近最less使用时间执行页面的sorting。

考虑的页面：2，1，0，2，8，2，4

添加到caching中的页面是：2
添加到caching中的页面是：1
添加到caching中的页面是：0
页面：2已经存在于caching中。 上次访问时间已更新
页面错误，页面：1，更换页面：8
添加到caching中的页面是：8
页面：2已经存在于caching中。 上次访问时间已更新
页面错误，页面：0，换成页面：4
添加到caching中的页面是：4

OUTPUT

LRUCache页面
————-
PageName：8，PageCreationTime：1365957019974
PageName：2，PageCreationTime：1365957020074
PageName：4，PageCreationTime：1365957020174

在此处input代码

 import java.util.Comparator; import java.util.Iterator; import java.util.PriorityQueue; public class LRUForCache { private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator()); public static void main(String[] args) throws InterruptedException { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4"); System.out.println("----------------------------------------------\n"); LRUForCache cache = new LRUForCache(); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("1")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("0")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("8")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("2")); Thread.sleep(100); cache.addPageToQueue(new LRUPage("4")); Thread.sleep(100); System.out.println("\nLRUCache Pages"); System.out.println("-------------"); cache.displayPriorityQueue(); } public synchronized void addPageToQueue(LRUPage page){ boolean pageExists = false; if(priorityQueue.size() == 3){ Iterator<LRUPage> iterator = priorityQueue.iterator(); while(iterator.hasNext()){ LRUPage next = iterator.next(); if(next.getPageName().equals(page.getPageName())){ /* wanted to just change the time, so that no need to poll and add again. but elements ordering does not happen, it happens only at the time of adding to the queue In case somebody finds it, plz let me know. */ //next.setPageCreationTime(page.getPageCreationTime()); priorityQueue.remove(next); System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated"); pageExists = true; break; } } if(!pageExists){ // enable it for printing the queue elemnts //System.out.println(priorityQueue); LRUPage poll = priorityQueue.poll(); System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName()); } } if(!pageExists){ System.out.println("Page added into cache is : " + page.getPageName()); } priorityQueue.add(page); } public void displayPriorityQueue(){ Iterator<LRUPage> iterator = priorityQueue.iterator(); while(iterator.hasNext()){ LRUPage next = iterator.next(); System.out.println(next); } } } class LRUPage{ private String pageName; private long pageCreationTime; public LRUPage(String pagename){ this.pageName = pagename; this.pageCreationTime = System.currentTimeMillis(); } public String getPageName() { return pageName; } public long getPageCreationTime() { return pageCreationTime; } public void setPageCreationTime(long pageCreationTime) { this.pageCreationTime = pageCreationTime; } @Override public boolean equals(Object obj) { LRUPage page = (LRUPage)obj; if(pageCreationTime == page.pageCreationTime){ return true; } return false; } @Override public int hashCode() { return (int) (31 * pageCreationTime); } @Override public String toString() { return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime; } } class LRUPageComparator implements Comparator<LRUPage>{ @Override public int compare(LRUPage o1, LRUPage o2) { if(o1.getPageCreationTime() > o2.getPageCreationTime()){ return 1; } if(o1.getPageCreationTime() < o2.getPageCreationTime()){ return -1; } return 0; } } 

Answer 11

这里是我testing的最好的执行并发LRUcaching实现没有任何同步块：

 public class ConcurrentLRUCache<Key, Value> { private final int maxSize; private ConcurrentHashMap<Key, Value> map; private ConcurrentLinkedQueue<Key> queue; public ConcurrentLRUCache(final int maxSize) { this.maxSize = maxSize; map = new ConcurrentHashMap<Key, Value>(maxSize); queue = new ConcurrentLinkedQueue<Key>(); } /** * @param key - may not be null! * @param value - may not be null! */ public void put(final Key key, final Value value) { if (map.containsKey(key)) { queue.remove(key); // remove the key from the FIFO queue } while (queue.size() >= maxSize) { Key oldestKey = queue.poll(); if (null != oldestKey) { map.remove(oldestKey); } } queue.add(key); map.put(key, value); } /** * @param key - may not be null! * @return the value associated to the given key or null */ public Value get(final Key key) { return map.get(key); } 

}

Answer 12

This is the LRU cache I use, which encapsulates a LinkedHashMap and handles concurrency with a simple synchronize lock guarding the juicy spots. It "touches" elements as they are used so that they become the "freshest" element again, so that it is actually LRU. I also had the requirement of my elements having a minimum lifespan, which you can also think of as "maximum idle time" permitted, then you're up for eviction.

However, I agree with Hank's conclusion and accepted answer — if I were starting this again today, I'd check out Guava's CacheBuilder .

 import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; public class MaxIdleLRUCache<KK, VV> { final static private int IDEAL_MAX_CACHE_ENTRIES = 128; public interface DeadElementCallback<KK, VV> { public void notify(KK key, VV element); } private Object lock = new Object(); private long minAge; private HashMap<KK, Item<VV>> cache; public MaxIdleLRUCache(long minAgeMilliseconds) { this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES); } public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) { this(minAgeMilliseconds, idealMaxCacheEntries, null); } public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) { this.minAge = minAgeMilliseconds; this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) { private static final long serialVersionUID = 1L; // This method is called just after a new entry has been added public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) { // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size. long age = System.currentTimeMillis() - eldest.getValue().birth; if (age > MaxIdleLRUCache.this.minAge) { if ( callback != null ) { callback.notify(eldest.getKey(), eldest.getValue().payload); } return true; // remove it } return false; // don't remove this element } }; } public void put(KK key, VV value) { synchronized ( lock ) { // System.out.println("put->"+key+","+value); cache.put(key, new Item<VV>(value)); } } public VV get(KK key) { synchronized ( lock ) { // System.out.println("get->"+key); Item<VV> item = getItem(key); return item == null ? null : item.payload; } } public VV remove(String key) { synchronized ( lock ) { // System.out.println("remove->"+key); Item<VV> item = cache.remove(key); if ( item != null ) { return item.payload; } else { return null; } } } public int size() { synchronized ( lock ) { return cache.size(); } } private Item<VV> getItem(KK key) { Item<VV> item = cache.get(key); if (item == null) { return null; } item.touch(); // idle the item to reset the timeout threshold return item; } private static class Item<T> { long birth; T payload; Item(T payload) { this.birth = System.currentTimeMillis(); this.payload = payload; } public void touch() { this.birth = System.currentTimeMillis(); } } } 

Answer 13

Well for a cache you will generally be looking up some piece of data via a proxy object, (a URL, String….) so interface-wise you are going to want a map. but to kick things out you want a queue like structure. Internally I would maintain two data structures, a Priority-Queue and a HashMap. heres an implementation that should be able to do everything in O(1) time.

Here's a class I whipped up pretty quick:

 import java.util.HashMap; import java.util.Map; public class LRUCache<K, V> { int maxSize; int currentSize = 0; Map<K, ValueHolder<K, V>> map; LinkedList<K> queue; public LRUCache(int maxSize) { this.maxSize = maxSize; map = new HashMap<K, ValueHolder<K, V>>(); queue = new LinkedList<K>(); } private void freeSpace() { K k = queue.remove(); map.remove(k); currentSize--; } public void put(K key, V val) { while(currentSize >= maxSize) { freeSpace(); } if(map.containsKey(key)) {//just heat up that item get(key); return; } ListNode<K> ln = queue.add(key); ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln); map.put(key, rv); currentSize++; } public V get(K key) { ValueHolder<K, V> rv = map.get(key); if(rv == null) return null; queue.remove(rv.queueLocation); rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue return rv.value; } } class ListNode<K> { ListNode<K> prev; ListNode<K> next; K value; public ListNode(K v) { value = v; prev = null; next = null; } } class ValueHolder<K,V> { V value; ListNode<K> queueLocation; public ValueHolder(V value, ListNode<K> ql) { this.value = value; this.queueLocation = ql; } } class LinkedList<K> { ListNode<K> head = null; ListNode<K> tail = null; public ListNode<K> add(K v) { if(head == null) { assert(tail == null); head = tail = new ListNode<K>(v); } else { tail.next = new ListNode<K>(v); tail.next.prev = tail; tail = tail.next; if(tail.prev == null) { tail.prev = head; head.next = tail; } } return tail; } public K remove() { if(head == null) return null; K val = head.value; if(head.next == null) { head = null; tail = null; } else { head = head.next; head.prev = null; } return val; } public void remove(ListNode<K> ln) { ListNode<K> prev = ln.prev; ListNode<K> next = ln.next; if(prev == null) { head = next; } else { prev.next = next; } if(next == null) { tail = prev; } else { next.prev = prev; } } } 

这是如何工作的。 Keys are stored in a linked list with the oldest keys in the front of the list (new keys go to the back) so when you need to 'eject' something you just pop it off the front of the queue and then use the key to remove the value from the map. When an item gets referenced you grab the ValueHolder from the map and then use the queuelocation variable to remove the key from its current location in the queue and then put it at the back of the queue (its now the most recently used). Adding things is pretty much the same.

I'm sure theres a ton of errors here and I haven't implemented any synchronization. but this class will provide O(1) adding to the cache, O(1) removal of old items, and O(1) retrieval of cache items. Even a trivial synchronization (just synchronize every public method) would still have little lock contention due to the run time. If anyone has any clever synchronization tricks I would be very interested. Also, I'm sure there are some additional optimizations that you could implement using the maxsize variable with respect to the map.

Answer 14

Have a look at ConcurrentSkipListMap . It should give you log(n) time for testing and removing an element if it is already contained in the cache, and constant time for re-adding it.

You'd just need some counter etc and wrapper element to force ordering of the LRU order and ensure recent stuff is discarded when the cache is full.

Answer 15

Here is my short implementation, please criticize or improve it!

 package util.collection; import java.util.concurrent.ConcurrentHashMap; import java.util.concurrent.ConcurrentLinkedQueue; /** * Limited size concurrent cache map implementation.<br/> * LRU: Least Recently Used.<br/> * If you add a new key-value pair to this cache after the maximum size has been exceeded, * the oldest key-value pair will be removed before adding. */ public class ConcurrentLRUCache<Key, Value> { private final int maxSize; private int currentSize = 0; private ConcurrentHashMap<Key, Value> map; private ConcurrentLinkedQueue<Key> queue; public ConcurrentLRUCache(final int maxSize) { this.maxSize = maxSize; map = new ConcurrentHashMap<Key, Value>(maxSize); queue = new ConcurrentLinkedQueue<Key>(); } private synchronized void freeSpace() { Key key = queue.poll(); if (null != key) { map.remove(key); currentSize = map.size(); } } public void put(Key key, Value val) { if (map.containsKey(key)) {// just heat up that item put(key, val); return; } while (currentSize >= maxSize) { freeSpace(); } synchronized(this) { queue.add(key); map.put(key, val); currentSize++; } } public Value get(Key key) { return map.get(key); } } 

Answer 16

Here's my own implementation to this problem

simplelrucache provides threadsafe, very simple, non-distributed LRU caching with TTL support. It provides two implementations:

• Concurrent based on ConcurrentLinkedHashMap
• Synchronized based on LinkedHashMap

You can find it here: http://code.google.com/p/simplelrucache/

Answer 17

I'm looking for a better LRU cache using Java code. Is it possible for you to share your Java LRU cache code using LinkedHashMap and Collections#synchronizedMap ? Currently I'm using LRUMap implements Map and the code works fine, but I'm getting ArrayIndexOutofBoundException on load testing using 500 users on the below method. The method moves the recent object to front of the queue.

 private void moveToFront(int index) { if (listHead != index) { int thisNext = nextElement[index]; int thisPrev = prevElement[index]; nextElement[thisPrev] = thisNext; if (thisNext >= 0) { prevElement[thisNext] = thisPrev; } else { listTail = thisPrev; } //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1 // prev[0 old head] = new head right ; next[new head] = old head prevElement[index] = -1; nextElement[index] = listHead; prevElement[listHead] = index; listHead = index; } } 

get(Object key) and put(Object key, Object value) method calls the above moveToFront method.

Answer 18

Wanted to add comment to the answer given by Hank but some how I am not able to – please treat it as comment

LinkedHashMap maintains access order as well based on parameter passed in its constructor It keeps doubly lined list to maintain order (See LinkedHashMap.Entry)

@Pacerier it is correct that LinkedHashMap keeps same order while iteration if element is added again but that is only in case of insertion order mode.

this is what I found in java docs of LinkedHashMap.Entry object

  /** * This method is invoked by the superclass whenever the value * of a pre-existing entry is read by Map.get or modified by Map.set. * If the enclosing Map is access-ordered, it moves the entry * to the end of the list; otherwise, it does nothing. */ void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; if (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } } 

this method takes care of moving recently accessed element to end of the list. So all in all LinkedHashMap is best data structure for implementing LRUCache.

Answer 19

Another thought and even a simple implementation using LinkedHashMap collection of Java.

LinkedHashMap provided method removeEldestEntry and which can be overridden in the way mentioned in example. By default implementation of this collection structure is false. If its true and size of this structure goes beyond the initial capacity than eldest or older elements will be removed.

We can have a pageno and page content in my case pageno is integer and pagecontent i have kept page number values string.

 import java.util.LinkedHashMap; import java.util.Map; /** * @author Deepak Singhvi * */ public class LRUCacheUsingLinkedHashMap { private static int CACHE_SIZE = 3; public static void main(String[] args) { System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99"); System.out.println("----------------------------------------------\n"); // accessOrder is true, so whenever any page gets changed or accessed, // its order will change in the map, LinkedHashMap<Integer,String> lruCache = new LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) { private static final long serialVersionUID = 1L; protected boolean removeEldestEntry(Map.Entry<Integer,String> eldest) { return size() > CACHE_SIZE; } }; lruCache.put(2, "2"); lruCache.put(1, "1"); lruCache.put(0, "0"); System.out.println(lruCache + " , After first 3 pages in cache"); lruCache.put(2, "2"); System.out.println(lruCache + " , Page 2 became the latest page in the cache"); lruCache.put(8, "8"); System.out.println(lruCache + " , Adding page 8, which removes eldest element 2 "); lruCache.put(2, "2"); System.out.println(lruCache+ " , Page 2 became the latest page in the cache"); lruCache.put(4, "4"); System.out.println(lruCache+ " , Adding page 4, which removes eldest element 1 "); lruCache.put(99, "99"); System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 "); } } 

Result of above code execution is as follows:

  Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99 -------------------------------------------------- {2=2, 1=1, 0=0} , After first 3 pages in cache {2=2, 1=1, 0=0} , Page 2 became the latest page in the cache {1=1, 0=0, 8=8} , Adding page 8, which removes eldest element 2 {0=0, 8=8, 2=2} , Page 2 became the latest page in the cache {8=8, 2=2, 4=4} , Adding page 4, which removes eldest element 1 {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 

Answer 20

Android offers an implementation of an LRU Cache . The code is clean and straightforward.