请不要说的EHCache或OSCache的等假设为这个问题的目的，我想实现自己只使用SDK（边做边学）。 由于缓存将在多线程环境中使用，你会用哪些数据结构？ 我已经实现并采用一个LinkedHashMap的和集合＃synchronizedMap ，但我很好奇，如果任何新的并发集合的效果会更好的候选人。
更新：我只是通过阅读Yegge最新当我发现这个金块：
如果你需要不断地访问，并希望保持插入顺序，你不能这样做比LinkedHashMap中，一个真正精彩的数据结构更好。 它可能是更美妙的唯一方法是，如果有一个并发版本。 可惜。
我想几乎同样的事情之前，我同去LinkedHashMap + Collections#synchronizedMap我上面提到的实现。 很高兴知道我已经不只是忽略了什么。
根据到目前为止的答案，这听起来像一个高度并行LRU我最好的选择将延长ConcurrentHashMap的使用一些相同的逻辑的LinkedHashMap使用。
我喜欢很多的这些建议，但现在我想我会坚持使用LinkedHashMap + Collections.synchronizedMap 。 如果我重温这在将来，我可能会在延长工作ConcurrentHashMap以同样的方式LinkedHashMap延伸HashMap 。
更新：
按要求，这是我目前执行的要点。
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));
或使用该Apache的共享数据结构：
https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/map/LRUMap.html
如果我再次从头今天这样做，我会用番石榴的CacheBuilder 。
这是第二轮。
第一轮是什么，我想出了然后我重读在我脑海中的域更根深蒂固了一下意见。
因此，这里是一个单元测试，显示它基于一些其它版本中工作最简单的版本。
首先，非并发版本：
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也只是实现了一个FIFO缓存（见FIFO和removeEldestEntry下面的注释）。
下面是证明它可以作为一个LRU缓存测试：
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 ();
}
}
你可以看到为什么我第一次覆盖非并发版本。 上述尝试创造一些条纹，以减少锁争用。 所以我们把它散列键，然后查找该散列找到实际的缓存。 这使得这取决于如何传播你的钥匙散列算法是极限尺寸更建议/粗略估计了相当数量的误差范围内。
下面是测试表明并发版本可能工作。 :)（下火的考验将是真正的出路）。
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 ();
}
}
这是最后的帖子..第一次发帖我删除，因为它是一个LFU不是LRU缓存。
我以为我会这样给别的去了。 我试图努力想出了使用标准的JDK W / O太多的实现LRU缓存的最简单的版本。
以下是我想出了。 我第一次尝试有点一场灾难，因为我实现了一个LFU，而不是和LRU，然后我加入FIFO，并把它LRU支持...然后我意识到它正在成为一个怪物。 然后，我开始跟我的好友约翰·谁是几乎没有兴趣，然后我在深深的长度描述我是如何实现的LFU，LRU和FIFO以及你如何能够用一个简单的ENUM ARG打开它，然后我意识到我真正想要的是一个简单的LRU。 所以，忽略了我先前的帖子，让我知道，如果你想看到的LRU / LFU / FIFO缓存是通过切换一个枚举......不是吗？ 确定..在这里，他去了。
可能最简单的LRU只使用JDK。 我实现了两个并行版本和非并发版本。
我创建了一个通用的接口（它是如此的简约失踪可能一些功能，你会喜欢，但它适合我的使用情况，但让如果你想看到的功能XYZ让我知道......我活到编写代码。） 。
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是什么。 我用这个测试。 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 ();
}
}
该queue.removeFirstOccurrence是一个潜在的昂贵的操作，如果你有一个大的缓存。 人们可以采取链表作为一个例子，并添加一个反向查找散列映射从元件到节点以使删除操作快得多和更一致。 我开始过，但后来意识到我并不需要它。 但是...也许...
当放被调用时，关键被添加到队列中。 当得到的是所谓的，关键被删除并重新添加到队列的顶部。
如果你的缓存较小，建筑的产品贵那么这应该是一个很好的缓存。 如果你的缓存是真正的大，那么线性搜索可能是一个瓶颈，特别是如果你没有缓存的热点领域。 越强烈的热点，更快的线性搜索的热点项目始终处于线性搜索的顶部。 反正...什么是需要这种走得更快是另外写LinkedList的有有到节点查找用于删除反向元素的删除操作，然后除去将大约尽可能快地去除哈希映射的关键。
如果您有低于1000项的高速缓存，这应该迎刃而解。
下面是一个简单的测试，显示在行动的业务。
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 ();
}
}
最后LRU缓存是单线程的，请不要把它包在一个同步的东西....
这里是一个并行版本一刀。
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和使用锁的（我可以侥幸同步，但...）。
我还没有受到攻击测试，但它似乎是一个简单的LRU缓存，你需要一个简单的LRU地图可能制定出使用用例的80％。
我欢迎任何意见，除了你为什么不使用库，b或c。 我并不总是使用图书馆的原因是因为我并不总是希望每一场战争文件为80MB，而我写的库，所以我倾向于让库插件能够足够好的解决方案到位，有人可能堵塞-in另一个缓存提供商，如果他们喜欢。 :)我从来不知道什么时候有人可能需要番石榴或ehcache的或别的东西，我不想将它们包括，但如果我做缓存插件能，我也不会排除。
依赖的减少有自己的奖励。 我爱得到关于如何使这个更简单或更快的或两者的一些反馈。
此外，如果任何人准备的知道去....
好吧..我知道你在想什么？他为什么不只是使用来自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;
}
};
这个测试失败，上面的代码...
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一个快速和肮脏的FIFO缓存。
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 ();
}
}
FIFO的速度快。 没有摸索。 你可以在前面的LRU前面的FIFO以及将处理最炙手可热的条目相当不错。 一个更好的LRU将会需要节点功能，反转要素。
反正......现在，我写了一些代码，让我去通过其他的答案，看看我错过了......我第一次扫描他们。
LinkedHashMap是O（1），但需要同步化。 不需要有推倒重来。
2个选择增加并发：
1.创建多个LinkedHashMap ，和散列成它们：例如： LinkedHashMap[4], index 0, 1, 2, 3 。 上的键做key%4 （或binary OR上[key, 3]来接做哪些地图的卖出/获得/除去。
2.您可以通过延伸做一个“几乎” LRU ConcurrentHashMap ，和具有连接的哈希映射像中的每个在其内部的区域的结构。 锁定会比发生更精细LinkedHashMap是同步的。 上的put或putIfAbsent列表的上头部仅一个锁和尾部（每个区域）是必要的。 在删除或得到整个区域需要被锁定。 我很好奇，如果某种原子链表可能有助于在这里 - 大概如此的名单之首。 也许更多。
该结构将不会保持总的秩序，但只有每个区域的顺序。 只要条目的数量比区域的数量要大得多，这是大多数缓存不够好。 每个地区将必须有它自己的条目数量，这将被使用，而不是为驱逐触发全球计数。 区域在默认数量ConcurrentHashMap是16，这是今天很多对于大多数服务器。
将在中度并发更容易编写和更快。
会写，但规模以非常高的并发性更好的更困难。 这将是慢的正常访问（就像ConcurrentHashMap是慢HashMap里没有并发）
有两种开源实现。
Apache Solr实现具有ConcurrentLRUCache： https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html
有一个ConcurrentLinkedHashMap一个开源项目： http://code.google.com/p/concurrentlinkedhashmap/
我会考虑使用java.util.concurrent.PriorityBlockingQueue中 ，通过在每个元素“numberOfUses”计数器确定的优先。 我会非常，非常小心，让我所有的同步正确的，因为“numberOfUses”反意味着元素不能是一成不变的。
元素对象将是在缓存中的对象的包装：
class CacheElement {
private final Object obj;
private int numberOfUsers = 0;
CacheElement(Object obj) {
this.obj = obj;
}
... etc.
}
希望这可以帮助 。
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);
}
}
LRU缓存可以使用的ConcurrentLinkedQueue并且其可以在多线程场景中使用以及一个的ConcurrentHashMap来实现。 队列的头是元素一直在队列中时间最长。 队列的尾部是该元素已经在队列中的时间最短。 当一个元素在地图存在，我们可以从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);
}
}
这里是我实施LRU。 我已经使用PriorityQueue的，基本上可以作为FIFO，而不是线程安全的。 二手比较基于网页的时间创作并根据执行中的页数最近最少使用时间的排序。
页面加入缓存：2
页面加入缓存：1
页面加入缓存：0
页：2已经exisit在缓存中。 最后访问时间更新
页面错误，PAGE：1，替换为PAGE：8
页面加入缓存：8
页：2已经exisit在缓存中。 最后访问时间更新
页面错误，PAGE：0，替换为PAGE：4
页面加入缓存：4
LRUCache页面
-------------
页面名称：8，PageCreationTime：1365957019974
页面名称：2，PageCreationTime：1365957020074
页面名称：4，PageCreationTime：1365957020174
在此处输入代码
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;
}
}
这是我最好的测试，没有任何synchronized块并发执行LRU Cache实现：
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);
}
}
这是LRU缓存我使用，它封装LinkedHashMap中和处理并发用一个简单的同步锁守卫多汁的斑点。 据“摩的”元素，它们被用来让他们再次成为“最新鲜”的元素，因此，它实际上是LRU。 我也有具有最小的寿命，这也可以认为是允许的“最大空闲时间”，那么你最多驱逐的我要素的要求。
不过，我同意汉克的结论和接受的答案-如果我再次从今天开始这一点，我会找番石榴的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();
}
}
}
那么对于一个高速缓存，您通常需要通过代理对象找了一些数据块，（一个URL，字符串....）所以接口明智的你会想要一个地图。 但踢出来的东西你想状结构的队列。 我在内部将保持两个数据结构，优先级，队列和一个HashMap。 继承人应该是能够做到在O（1）时间一切的实现。
这里有一个I类刮起了相当快：
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;
}
}
}
下面是它如何工作的。 密钥存储在与列表中的前历史最悠久的键链表（新键去背），所以当你需要“退出”的东西，你只是弹出它关闭了队列的前面，然后用钥匙删除从地图的值。 当一个项目得到引用您从地图抢而ValueHolder，然后使用queuelocation变量从队列中删除当前位置的键，然后把它放在队列的后面（它现在最近使用）。 添加的东西是大同小异的。
这里我敢肯定，那里有一吨的错误，并且我还没有实现任何同步。 但这个类提供添加到缓存中，O（1）去除老项目的O（1）和O（1）的缓存项检索。 即使是微不足道的同步（同步只是每个公共方法）仍然有小锁争用，由于运行时间。 如果任何人有任何聪明的同步技巧我会非常有兴趣。 另外，我敢肯定有，你可以实现使用MAXSIZE变量相对于地图上的一些额外的优化。
看一看ConcurrentSkipListMap 。 它应该给你的log（n）的时间进行测试，如果它已经包含在缓存中移除元素，以及恒定的时间重新添加。
你只需要一些柜台等，并包装元素，迫使LRU顺序进行排序，并确保最近的东西时被丢弃缓存已满。
这里是我的短执行，请批评或改善它！
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);
}
}
这是我自己实现了这个问题
simplelrucache提供线程安全的，很简单的，非分布式缓存LRU与TTL支持。 它提供了两种实现方式：
你可以在这里找到它： http://code.google.com/p/simplelrucache/
我在寻找使用Java代码更好的LRU缓存。 是否有可能为你使用分享你的Java LRU缓存代码LinkedHashMap和Collections#synchronizedMap ？ 目前我使用LRUMap implements Map和代码工作正常，但我越来越ArrayIndexOutofBoundException使用500级的用户在以下方法上的负载测试。 该方法移动最近对象到队列的前面。
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) ，并put(Object key, Object value)方法调用上面moveToFront方法。
想评论添加到由汉克给出的答案，但一些如何我无法 - 请把它当作评论
LinkedHashMap的维护访问顺序以及基于在其构造函数传递的参数它保持双内衬列表维持秩序（见LinkedHashMap.Entry）
@Pacerier它是正确的，LinkedHashMap中保持相同的顺序而如果重复元素被再次添加，但就是只有在插入顺序模式的情况下。
这是我在LinkedHashMap.Entry对象的Java文档找到
/**
* 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);
}
}
这种方法需要移动最近访问的元素结束列表的照顾。 因此，所有的所有的LinkedHashMap是实现LRUCache最佳的数据结构。
另一种思考和使用Java的LinkedHashMap的集合，甚至一个简单的实现。
LinkedHashMap的提供方法removeEldestEntry并且其可以在示例中提到的方式被覆盖。 默认情况下，实现这个集合的结构是假的。 如果它的真实，这种结构的尺寸超越了比大或以上元素的初始容量将被删除。
我们可以在我的情况下帮您做生意一帮您做生意和页面内容为整数，pagecontent我一直页码值的字符串。
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 "); } }
上面的代码执行的结果如下：
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
继@sanjanab概念（但修正后），我做也提供允许如果需要做一些与删除的项目消费者我对LRUCache的版本。
public class LRUCache<K, V> {
private ConcurrentHashMap<K, V> map;
private final Consumer<V> onRemove;
private ConcurrentLinkedQueue<K> queue;
private final int size;
public LRUCache(int size, Consumer<V> onRemove) {
this.size = size;
this.onRemove = onRemove;
this.map = new ConcurrentHashMap<>(size);
this.queue = new ConcurrentLinkedQueue<>();
}
public V get(K key) {
//Recently accessed, hence move it to the tail
if (queue.remove(key)) {
queue.add(key);
return map.get(key);
}
return null;
}
public void put(K key, V value) {
//ConcurrentHashMap doesn't allow null key or values
if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");
V existing = map.get(key);
if (existing != null) {
queue.remove(key);
onRemove.accept(existing);
}
if (map.size() >= size) {
K lruKey = queue.poll();
if (lruKey != null) {
V removed = map.remove(lruKey);
onRemove.accept(removed);
}
}
queue.add(key);
map.put(key, value);
}
}
Android提供了一个的实现LRU缓存 。 该代码是干净和简单。
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://img.manongdao.com/sparkler-677774__340.jpg', '推荐 在下西门庆 的文章《你将如何在Java中实现一个LRU缓存？你将如何在Java中实现一个LRU缓存？(How would》','https://www.manongdao.com/article-809816.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}