- 浏览: 923464 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
hw7777777:
非常感谢作者提供这么好的工具,在使用的过程中遇到一些问题?1、 ...
基于java nio的memcached客户端——xmemcached -
SINCE1978:
多久过去了时间能抹平一切
无路用的人 -
fangruanyjq:
[img][/img]引用
用osworkflow写一个请假例子(提供代码下载) -
thinkingmysky:
楼主,你确定,java memached client能处理并 ...
memcached java client性能测试的几点疑问和说明 -
hellostory:
aaa5131421 写道07年2月hibernate已经出来 ...
dozer与BeanUtils
最简单的LRU算法实现,就是利用jdk的LinkedHashMap,覆写其中的removeEldestEntry(Map.Entry)方法即可,如下所示:
如果你去看LinkedHashMap的源码可知,LRU算法是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入 的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置。
LRU算法还可以通过计数来实现,缓存存储的位置附带一个计数器,当命中时将计数器加1,替换时就查找计数最小的位置并替换,结合访问时间戳来实现。这种 算法比较适合缓存数据量较小的场景,显然,遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个,结合了访问时间戳,当最小计数大于 MINI_ACESS时,就移除最久没有被访问的项:
java 代码
- 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文档
- *
- * @author dennis
- *
- * @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时,就移除最久没有被访问的项:
java 代码
- 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.ReentrantLock;
- /**
- *
- * @author dennis
- * 类说明:当缓存数目不多时,才用缓存计数的传统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 Lock lock = new ReentrantLock();
- private final transient int maxCapacity;
- private static int MINI_ACCESS = 10;
- 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 {
- lock.lock();
- return this.map.containsKey(key);
- } finally {
- lock.unlock();
- }
- }
- public V put(K key, V value) {
- try {
- lock.lock();
- if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) {
- // System.out.println("开始");
- Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet();
- removeRencentlyLeastAccess(entries);
- }
- ValueEntry valueEntry = map.put(key, new ValueEntry(value));
- if (valueEntry != null)
- return valueEntry.value;
- else
- return null;
- } finally {
- lock.unlock();
- }
- }
- /**
- * 移除最近最少访问
- */
- protected void removeRencentlyLeastAccess(
- Set<Map.Entry<K, ValueEntry>> entries) {
- // 最小使用次数
- int 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 {
- lock.lock();
- V value = null;
- ValueEntry valueEntry = map.get(key);
- if (valueEntry != null) {
- // 更新访问时间戳
- valueEntry.updateLastAccess();
- // 更新访问次数
- valueEntry.count.incrementAndGet();
- value = valueEntry.value;
- }
- return value;
- } finally {
- lock.unlock();
- }
- }
- public void clear() {
- try {
- lock.lock();
- map.clear();
- } finally {
- lock.unlock();
- }
- }
- public int size() {
- try {
- lock.lock();
- return map.size();
- } finally {
- lock.unlock();
- }
- }
- public Collection<Map.Entry<K, V>> getAll() {
- try {
- lock.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 {
- lock.unlock();
- }
- }
- class ValueEntry implements Serializable {
- private V value;
- private AtomicInteger count;
- private AtomicLong lastAccess;
- public ValueEntry(V value) {
- this.value = value;
- this.count = new AtomicInteger(0);
- lastAccess = new AtomicLong(System.nanoTime());
- }
- public void updateLastAccess() {
- this.lastAccess.set(System.nanoTime());
- }
- }
- }
发表评论
-
memcached分布测试报告(一致性哈希情况下的散列函数选择)
2009-03-10 16:30 8412一、背景资料 memcached本身是集中式的缓存系统 ... -
xmemcached 0.60 优化过程
2009-03-06 14:37 3378充分利用jprofile等 ... -
Xmemcached vs Spymemcached 3th(linux下测试结果和多节点下表现)
2009-03-07 10:43 4735翠花,上图,首先是容器类和自定义对象的get、set在不同并发 ... -
xmemcached发布1.0-BETA版
2009-03-09 15:32 3972xmemcached 发布1.0-beta ,从0.6 ... -
山寨nio框架yanf4j发布0.50-alpha
2009-02-04 19:28 4119俺的山寨nio框架yanf4j发布0.50-alpha版本,下 ... -
yanf4j引入了客户端非阻塞API
2009-02-19 00:15 2950yanf4j 发布一个0.50-beta2 版本,这个版本最 ... -
基于java nio的memcached客户端——xmemcached
2009-03-03 16:31 72891、xmemcached是什么? xmemcached是基于 ... -
使用yanf4j写个简单聊天室
2008-11-26 11:36 5358yanf4j 简介,请看这里 ... -
Java字符串的最大长度
2009-01-15 01:37 7517在cpp中为了可移植性,s ... -
yanf4j-0.41 beta发布
2009-01-20 14:01 1803项目名称:yanf4j (yet another nio fr ... -
再谈Selector的wakeup方法
2009-02-01 11:15 2997过去推荐过两篇blog《Java NIO类库Selector机 ... -
Yet another nio framework for java
2008-10-11 14:25 1954项目名称:Yanf4j(Yet another nio fra ... -
阻塞队列的性能对比
2008-09-08 10:06 5686阻塞队列的性能对 ... -
java package的设计原则
2008-09-06 00:15 2075典型的J2EE项目,package的设计有成熟的套路可 ... -
线程池池
2008-09-01 19:39 1953这个题目比较怪,听俺道来。俺一直在负责公司游戏服 ... -
第一个MapReduce任务
2008-08-23 11:10 2737前两天在公司内网上搭了个2个节点hadoop集群, ... -
从HDFS看分布式文件系统的设计需求
2008-08-15 22:39 8037分布式文件系统的 ... -
HDFS用户指南(翻译)
2008-08-14 20:27 2093HDFS用户指南 原文地址:http:/ ... -
Ehcache配置的overflowToDisk属性
2008-08-06 23:18 10752Ehcache的overflowToDisk属性用来配 ... -
工作的几个tip
2008-07-07 20:47 28211、如果用java6的ScriptEngineManager ...
相关推荐
用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...
基于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 ...
Android提供了LRUCache类,可以方便的使用它来实现LRU算法的缓存。Java提供了LinkedHashMap,可以用该类很方便的实现LRU算法,Java的LRULinkedHashMap是直接继承了LinkedHashMap,进行了极少的改动后可以实现LRU...