http://www.blogjava.net/killme2008/archive/2008/01/14/149645.html
最简单的LRU算法实现,就是利用jdk的LinkedHashMap,覆写其中的removeEldestEntry(Map.Entry)方法即可,如下所示:
如果你去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现,缓存存储的位置附带一个计数器,当命中时将计数器加1,替换时就查找计数最小的位置并替换,结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景,显然,遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个,结合了访问时间戳,当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响),就移除最久没有被访问的项:
最简单的LRU算法实现,就是利用jdk的LinkedHashMap,覆写其中的removeEldestEntry(Map.Entry)方法即可,如下所示:
import java.util.ArrayList; import java.util.Collection; import java.util.LinkedHashMap; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; import java.util.Map; /** * 类说明:利用LinkedHashMap实现简单的缓存, 必须实现removeEldestEntry方法,具体参见JDK文档 * * * @param <K> * @param <V> */ public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap(int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>(super.entrySet()); } finally { lock.unlock(); } } }
如果你去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现,缓存存储的位置附带一个计数器,当命中时将计数器加1,替换时就查找计数最小的位置并替换,结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景,显然,遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个,结合了访问时间戳,当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响),就移除最久没有被访问的项:
package net.rubyeye.codelib.util.concurrency.cache; import java.io.Serializable; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Map; import java.util.Set; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantLock; import java.util.concurrent.locks.ReentrantReadWriteLock; /** * *类说明:当缓存数目不多时,才用缓存计数的传统LRU算法 * @param <K> * @param <V> */ public class LRUCache<K, V> implements Serializable { private static final int DEFAULT_CAPACITY = 100; protected Map<K, ValueEntry> map; private final ReadWriteLock lock = new ReentrantReadWriteLock(); private final Lock readLock = lock.readLock(); private final Lock writeLock = lock.writeLock(); private final volatile int maxCapacity; //保持可见性 public static int MINI_ACCESS = 5; public LRUCache() { this(DEFAULT_CAPACITY); } public LRUCache(int capacity) { if (capacity <= 0) throw new RuntimeException("缓存容量不得小于0"); this.maxCapacity = capacity; this.map = new HashMap<K, ValueEntry>(maxCapacity); } public boolean ContainsKey(K key) { try { readLock.lock(); return this.map.containsKey(key); } finally { readLock.unlock(); } } public V put(K key, V value) { try { writeLock.lock(); if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) { // System.out.println("开始"); Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet(); removeRencentlyLeastAccess(entries); } ValueEntry new_value = new ValueEntry(value); ValueEntry old_value = map.put(key, new_value); if (old_value != null) { new_value.count = old_value.count; return old_value.value; } else return null; } finally { writeLock.unlock(); } } /** * 移除最近最少访问 */ protected void removeRencentlyLeastAccess( Set<Map.Entry<K, ValueEntry>> entries) { // 最小使用次数 long least = 0; // 访问时间最早 long earliest = 0; K toBeRemovedByCount = null; K toBeRemovedByTime = null; Iterator<Map.Entry<K, ValueEntry>> it = entries.iterator(); if (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); earliest = valueEntry.getValue().lastAccess.get(); toBeRemovedByTime = valueEntry.getKey(); } while (it.hasNext()) { Map.Entry<K, ValueEntry> valueEntry = it.next(); if (valueEntry.getValue().count.get() < least) { least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); } if (valueEntry.getValue().lastAccess.get() < earliest) { earliest = valueEntry.getValue().count.get(); toBeRemovedByTime = valueEntry.getKey(); } } // System.out.println("remove:" + toBeRemoved); // 如果最少使用次数大于MINI_ACCESS,那么移除访问时间最早的项(也就是最久没有被访问的项) if (least > MINI_ACCESS) { map.remove(toBeRemovedByTime); } else { map.remove(toBeRemovedByCount); } } public V get(K key) { try { readLock.lock(); V value = null; ValueEntry valueEntry = map.get(key); if (valueEntry != null) { // 更新访问时间戳 valueEntry.updateLastAccess(); // 更新访问次数 valueEntry.count.incrementAndGet(); value = valueEntry.value; } return value; } finally { readLock.unlock(); } } public void clear() { try { writeLock.lock(); map.clear(); } finally { writeLock.unlock(); } } public int size() { try { readLock.lock(); return map.size(); } finally { readLock.unlock(); } } public long getCount(K key) { try { readLock.lock(); ValueEntry valueEntry = map.get(key); if (valueEntry != null) { return valueEntry.count.get(); } return 0; } finally { readLock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { readLock.lock(); Set<K> keys = map.keySet(); Map<K, V> tmp = new HashMap<K, V>(); for (K key : keys) { tmp.put(key, map.get(key).value); } return new ArrayList<Map.Entry<K, V>>(tmp.entrySet()); } finally { readLock.unlock(); } } class ValueEntry implements Serializable { private V value; private AtomicLong count; private AtomicLong lastAccess; public ValueEntry(V value) { this.value = value; this.count = new AtomicLong(0); lastAccess = new AtomicLong(System.nanoTime()); } public void updateLastAccess() { this.lastAccess.set(System.nanoTime()); } } }
发表评论
-
Consistent Hashing
2010-02-09 17:12 771import java.util.Collection; ... -
防止JAVA程序重复启动的一个另类解决办法
2009-03-31 20:29 1888http://www.iteye.com/topic/3773 ... -
MappedByteBuffer内存映射
2009-03-15 21:26 2109通过把一个套接字通道(SocketChannel)注册到一个选 ... -
如何知道方法的调用者
2009-03-11 20:35 777http://www.iteye.com/topic/1317 ... -
JAVA中操作数据库方式与设计模式的应用
2009-03-11 15:02 815http://www.iteye.com/topic/1981 ... -
java调用Oracle EXP备忘
2009-03-10 11:28 1514http://www.blogjava.net/BlueDav ... -
关于java中volatile字段的ordering
2009-03-08 22:00 707多个volatile操作之间是有序的,compiler和处理 ... -
Initialize-on-demand Holder Class
2009-03-02 15:01 882public class Singleton { ... -
Interceptor的实现
2009-03-01 21:26 773public interface Action { p ... -
Quartz CronTrigger最完整配置说明
2009-02-15 15:12 976CronTrigger配置格式: 格 ... -
ClassLoader介绍
2009-01-21 13:24 779JVM在运行时会产生三个ClassLoader,Bootstr ... -
消息的发送与回调
2009-01-06 22:03 784/** * 回调接口 * @author ... -
自己编写IOC
2009-01-05 21:59 1150<?xml version="1.0&qu ... -
四则运算的中缀转后缀
2008-12-11 11:41 1587import java.math.BigDecimal ... -
一个简单的多线程、断点下载Java程序
2008-12-10 20:49 1862//这个是任务Bean public cl ... -
生产者-消费者
2008-12-02 14:05 794package debug; import java.u ...
相关推荐
用Java写的一个Cache,内部实现了LRU算法~
Nodejs基于LRU算法实现的缓存处理操作示例.docx
采用LRU置换算法的缓存类,通过封装Dictionary和LinkedList来实现,方便大家使用,也希望大家给出改进意见
15 当Buffer Pool中的缓存页不够的时候,如何基于LRU算法淘汰部分缓存.pdf
一个LRU算法的实现.适合于计算机体系结构课程的实验
LRU算法是常用的缓存替代算法,文档中告诉我们如何实现LRU算法
Lru算法缓存解决图片OOM,一个比较好的解决方案
主要介绍了Nodejs基于LRU算法实现的缓存处理操作,结合具体实例形式分析了LRU算法的原理、功能以及nodejs使用LRU算法实现缓存处理操作的相关实现技巧,需要的朋友可以参考下
这里的LRUCache类维护了一个双向链表和一个哈希表,用于实现LRU算法。具体实现细节如下: - get方法:首先在哈希表中查找对应的键值对,如果不存在,则返回-1;如果存在,则将对应的节点从双向链表中删除,并将其...
链表(上):如何实现LRU缓存淘汰算法
缓存淘汰算法之LRU
参考:http://www.cnblogs.com/lzrabbit/p/3734850.htmlLRU缓存实现(Java)LRU Cache的LinkedHa
“Python—LRU缓存.zip”是一个压缩文件,其中包含了使用Python实现的最近最少使用(Least Recently Used, LRU)缓存算法的代码和相关文档。LRU缓存算法是一种常用的缓存淘汰策略,它根据数据项最近被使用的时间来...
行业-15 当Buffer Pool中的缓存页不够的时候,如何基于LRU算法淘汰部分缓存.rar
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap就是直接继承了LinkedHashMap,进行了极少的改动后就可以实现LRU...
它旨在成为一门简单、高效、安全和并发的编程语言,特别适用于构建高性能的服务器和分布式系统。以下是Go语言的一些主要特点和优势: 简洁性:Go语言的语法简单直观,易于学习和使用。它避免了复杂的语法特性,如...
基于springboot+vue开发的电商项目(使用到LRU算法缓存商品信息,热卖商品,模糊查询搜索框,运用到沙箱支付)
##LRU算法介绍 引自: Discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always ...