LRU算法简略例子

2012-07-23

LRU算法简单例子转：http://blog.csdn.net/5iasp/article/details/4268090package com.aspboy.base.cache/

LRU算法简单例子

转：http://blog.csdn.net/5iasp/article/details/4268090

package com.aspboy.base.cache;

/*
?* Created on 2004-8-18
?*
?*“最近最少使用算法”（LRU算法），它是将最近一段时间内最少被访问过的行淘汰出局。
?*因此需要为每行设置一个计数器，LRU算法是把命中行的计数器清零，其他各行计数器加1。
?*当需要替换时淘汰行计数器计数值最大的数据行出局。
?*这是一种高效、科学的算法，其计数器清零过程可以把一些频繁调用后再不需要的数据淘汰出Cache，
?*提高Cache的利用率。
?*/

import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;

/**
?* @author 刘跃清
?*
?* 最近最少使用算法 Window - Preferences - Java - Code Style - Code Templates
?*/
public class LRU
{
??? protected HashMap lruCache = new HashMap(2);

??? //可操作的最大使用次数
??? protected int MAX_INTEGER_NUMBER=2147483647;

??? //缓存中保存的数大对象数目
??? protected int max_object_num=1000;

??? public LRU()
??? {
??? }
???
??? public LRU(int maxObjectNum)
??? {
??????? max_object_num=maxObjectNum;
??? }

??? /**
???? * 增加对象到缓存中
???? * @param key
???? * @param value
???? */
??? public Object put(Object key, Object value)
??? {
??????? CacheObject newValue = new CacheObject(value);
??????? if (lruCache.size()>=max_object_num)
??????? {
??????????? removeLease();
??????? }
???????
??????? return lruCache.put(key, newValue);
??? }

??? /**
???? * 使用key来获取对象
???? *
???? * @param key
???? * @return
???? */
??? public Object get(Object key)
??? {
??????? CacheObject object=(CacheObject)lruCache.get(key);
??????? if (object==null)
??????? {
??????????? return null;
??????? }

??????? //根据LRU算法原则，将命中的对象计算器0，将其他对象的计算值加1
??????? Set set=lruCache.keySet();
??????? Iterator iter=set.iterator();
??????? Object keyObject=null;
??????? CacheObject cacheObject=null;
??????? while(iter.hasNext())
??????? {
??????????? keyObject=iter.next();
??????????? cacheObject=(CacheObject) lruCache.get(keyObject);
??????????? cacheObject.setUsetimes(cacheObject.getUsetimes()+1);
??????? }
??????? object.setUsetimes(0);
???????
??return object!=null? object.getValue():null;
??? }

??? public boolean containsKey(Object key)
??? {
??????? return lruCache.containsKey(key);
??? }

??? public void clear()
??? {
??????? lruCache.clear();
??? }

??? public int size()
??? {
??????? return lruCache.size();
??? }

??? public boolean isEmpty()
??? {
??????? return lruCache.isEmpty();
??? }

??? public boolean containsValue(Object value)
??? {
??????? return lruCache.containsKey(value);
??? }

??? /**
???? * 移除使用最少的对象
???? */
??? public void removeLease()
??? {
??????? Object leaseUseObjectKey=null;
??????? int usetimes=0;

??? public Set keySet()
??? {
??????? return lruCache.keySet();
??? }
??? /**
???? * 移除使用最频繁的对象
???? */
??? public void removeMost()
??? {
??????? Object leaseUseObjectKey=null;
??????? int usetimes=MAX_INTEGER_NUMBER;

??????? Set set=lruCache.keySet();
??????? Iterator iter=set.iterator();
??????? while(iter.hasNext())
??????? {
??????????? Object keyObject=iter.next();
??????????? CacheObject object=(CacheObject) lruCache.get(keyObject);
??????????? if (object.getPushtime()>time)
??????????? {
??????????????? time=object.getPushtime();
??????????????? leaseUseObjectKey=keyObject;
??????????? }
??????? }
??????? lruCache.remove(leaseUseObjectKey);??????
??? }???
???
??? /**
???? * 删除某个键值及对应对象
???? * @param key
???? */
??? public void remove(Object key)
??? {
??????? lruCache.remove(key);
??? }
???
??? public static void main(String[] args)
??? {
??????? LRU lru = new LRU(4);
??????? lru.put("a","The A String");
??????? lru.put("b","The B String");
??????? lru.put("d","The D String");
??????? lru.put("c","The C String");
???????
??????? System.out.println(lru.toString());????
???????
??????? lru.get("a");
??????? lru.get("b");
??????? lru.get("d");
??????? lru.get("a");
??????? lru.get("b");
??????? lru.get("d");
??????? lru.put("e","The E String");
??????? lru.get("e");
??????? lru.get("e");
??????? lru.get("e");
??????? lru.get("e");
??????? System.out.println(lru.toString());
??? }

??? public String toString()
??? {
??????? StringBuffer strBf= new StringBuffer(10);
??????? Set set1=lruCache.keySet();
??????? Iterator iter1=set1.iterator();
??????? while(iter1.hasNext())
??????? {
??????????? Object key=iter1.next();
??????????? strBf.append(key+"=");
??????????? strBf.append(lruCache.get(key));
??????????? strBf.append("/n");
??????? }
??????? return strBf.toString();
??? }
???
?
}

package com.aspboy.base.cache;

/*
?* Created on 2004-9-7
?*
?* TODO To change the template for this generated file go to
?* Window - Preferences - Java - Code Style - Code Templates
?*/
/**

?*
?* TODO To change the template for this generated type comment go to
?* Window - Preferences - Java - Code Style - Code Templates
?*/
public class CacheObject
{
??? long pushtime = 0;

??? int usetimes = 0;

??? Object value = null;

??? CacheObject( Object value )
??? {
??????? pushtime = System.currentTimeMillis();
??????? usetimes = 0;
??????? this.value = value;
??? }
???
??? /**
???? * @return Returns the pushtime.
???? */
??? public final long getPushtime()
??? {
??????? return pushtime;
??? }
???
??? /**
???? * @return Returns the usetimes.
???? */
??? public final int getUsetimes()
??? {
??????? return usetimes;
??? }
??? /**
???? * @param usetimes The usetimes to set.
???? */
??? public final void setUsetimes(int usetimes)
??? {
??????? this.usetimes = usetimes;
??? }
??? /**
???? * @return Returns the value.
???? */
??? public final Object getValue()
??? {
??????? return value;
??? }
??? /**
???? * @param value The value to set.
???? */
??? public final void setValue(Object value)
??? {
??????? this.value = value;
??? }
???????
??? public String toString()
??? {
??????? StringBuffer strBf=new StringBuffer(10);
??????? strBf.append("value="+value+'/n');
??????? strBf.append("pushtime="+pushtime+'/n');
??????? strBf.append("usetimes="+usetimes+'/n');
??????? return strBf.toString();
??? }
}

热点排行

互联网

LRU算法简略例子