简单的java缓存实现(LRU,LFU,FIFO)-白红宇

简单的java缓存实现(LRU,LFU,FIFO)

阅读量：6008 次

发布时间：2019-06-20

本文共 7610 字，大约阅读时间需要 25 分钟。

简单的java缓存实现(LRU,LFU,FIFO) 博客分类： java

缓存算法也叫作淘汰算法，主要是为了当JVM空间不足时，用来清理掉缓存的。那么要清理的话，我们先清理掉哪些缓存呢？按照正常人的思维，当然是接下来一段时间内不大可能用到的缓存啦！根据这个思路，我们需要做出一定的判断，判断的方法通常有3个，即LFU、LRU、FIFO。

还有个问题，什么时候进行清理？when?

我觉得一般可以设置一个阈值，标记最小剩余空间，是在插入时候检查JVM剩余空间。或者还有一种方法，就是定时进行清理。

另外，怎么样评判淘汰算法的优劣？

主要是缓存命中率大小，其次是实现难度。

1、LRU(Least Recently Used ，最近最少使用)

算法根据数据的最近访问记录来淘汰数据，其原理是如果数据最近被访问过，将来被访问的几概率相对比较高，最常见的实现是使用一个链表保存缓存数据，详细具体算法如下：

1. 新数据插入到链表头部；

2. 每当缓存数据命中，则将数据移到链表头部；

3. 当链表满的时候，将链表尾部的数据丢弃。

我对于LRU算法的理解是，队列实际上是按照访问的时间循序进行排序，近期访问在队头，长期未访问在队尾，每次清空都是删除队尾的数据。当使用热点数据时，本方法特别好。

[java] view plain copy

<pre name="code" class="java">/**

* 项目名称：

* 文件说明：创建一个缓存管理器刘晨曦

* 主要特点：

* 版本号：1.0

* 创建时间：2013-12-3

**/

package NBOffer;

import games.MathTools;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.Date;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.SortedMap;

import java.util.TreeMap;

public class CacheManager {

static SortedMap<String,Cache> cacheMap=new TreeMap<String,Cache>();

static final int MAX_CACHE_NUM=5;//最大五个缓存

private static class ValueComparator implements Comparator<Map.Entry<String,Cache>>

{

public int compare(Map.Entry<String,Cache> m,Map.Entry<String,Cache> n)

{

return (int) (n.getValue().tagDate.getTime()-m.getValue().tagDate.getTime());

}

public static Cache getCache(String id)

{

if(cacheMap.get(id)==null)

{

Object val=getFromDB(id);

cacheMap.put(id, new Cache(id,val));

}

Cache res=cacheMap.get(id);

try {

Thread.sleep(100);

} catch (InterruptedException e) {

e.printStackTrace();

}

res.tagDate=new Date();

return cacheMap.get(id);

}

public static void putCache(Cache cache)

{

cacheMap.put(cache.id, cache);

}

public static Object getFromDB(String id)

{

System.out.println("缓慢地从内存中读取id="+id+"对应的数据。。。");

return new String("value"+id);

}

public static void refreshCaches()

{

System.out.println("刷新缓存。。。");

List<Map.Entry<String,Cache>> list=new ArrayList();

list.addAll(cacheMap.entrySet());

ValueComparator comparator=new ValueComparator();

Collections.sort(list,comparator);

for(Iterator<Map.Entry<String,Cache>> itea=list.iterator();itea.hasNext();)

{

System.out.println(itea.next());

}

for(int i=MAX_CACHE_NUM;i<list.size();i++)

{

String id=(String) list.get(i).getKey();

Object val=getFromDB(id);

cacheMap.put(id, new Cache(id,val));

}

public static void main(String[] args) throws InterruptedException {

Cache cache1=new Cache("1","value1");

Cache cache2=new Cache("2","value2");

Cache cache3=new Cache("3","value2");

Cache cache4=new Cache("4","value2");

Cache cache5=new Cache("5","value2");

Cache cache6=new Cache("6","value2");

Cache cache7=new Cache("7","value2");

CacheManager.putCache(cache1);

CacheManager.putCache(cache2);

CacheManager.putCache(cache3);

CacheManager.putCache(cache4);

CacheManager.putCache(cache5);

CacheManager.putCache(cache6);

CacheManager.putCache(cache7);

CacheManager.getCache("5");

CacheManager.getCache("6");

refreshCaches();

Thread refreshTD=new Thread()

{

public void run()

{

while(true)

{

refreshCaches();

try {

Thread.sleep(1000);//每一秒刷新一次

} catch (InterruptedException e) {

e.printStackTrace();

}

};

// refreshTD.start();

}

class Cache

{

String id;//相当于主键

Object val;

Date tagDate;//标记日期，标定什么时候使用的

public Cache(String id,Object val)

{

this.id=id;

this.val=val;

this.tagDate=new Date();

}

public void setValue(Object val)

{

this.val=val;

this.tagDate=new Date();

}

public void showInfo()

{

System.out.println("Cache的ID是: "+id+" Cache的值是: "+val);

}

public void setTagDate(Date dt)

{

this.tagDate=dt;

}

2、LFU(Least Frequently Used，最不经常使用)

算法根据数据的历史访问频率来淘汰数据，其原理是如果数据过去被访问次数越多，将来被访问的几概率相对比较高。LFU的每个数据块都有一个引用计数，所有数据块按照引用计数排序，具有相同引用计数的数据块则按照时间排序。

具体算法如下：

1. 新加入数据插入到队列尾部（因为引用计数为1）；

2. 队列中的数据被访问后，引用计数增加，队列重新排序；

3. 当需要淘汰数据时，将已经排序的列表最后的数据块删除；

我对于LFU算法的理解是，队列实际上是按照访问的频率循序进行排序，访问频率较高访问在队头，较低在队尾，每次清空都是删除队尾的数据。对于偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题，本方法特别好。代码如下：

[java] view plain copy

/**

* 项目名称：

* 文件说明：创建一个缓存管理器刘晨曦

* 主要特点：

* 版本号：1.0

* 创建时间：2013-12-3

**/

package NBOffer;

import games.MathTools;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.Date;

import java.util.Iterator;

import java.util.List;

import java.util.Map;

import java.util.Set;

import java.util.SortedMap;

import java.util.TreeMap;

public class CacheManager {

static SortedMap<String,Cache> cacheMap=new TreeMap<String,Cache>();

static final int MAX_CACHE_NUM=5;//最大五个缓存

private static class ValueComparator implements Comparator<Map.Entry<String,Cache>>

{

public int compare(Map.Entry<String,Cache> m,Map.Entry<String,Cache> n)

{

return n.getValue().usedcount-m.getValue().usedcount;

}

public static Cache getCache(String id)

{

if(cacheMap.get(id)==null)

{

Object val=getFromDB(id);

cacheMap.put(id, new Cache(id,val));

}

Cache res=cacheMap.get(id);

try {

Thread.sleep(100);

} catch (InterruptedException e) {

e.printStackTrace();

}

res.addCount();

return cacheMap.get(id);

}

public static void putCache(Cache cache)

{

cacheMap.put(cache.id, cache);

}

public static Object getFromDB(String id)

{

System.out.println("缓慢地从内存中读取id="+id+"对应的数据。。。");

return new String("value"+id);

}

public static void refreshCaches()

{

System.out.println("刷新缓存。。。");

List<Map.Entry<String,Cache>> list=new ArrayList();

list.addAll(cacheMap.entrySet());

ValueComparator comparator=new ValueComparator();

Collections.sort(list,comparator);

for(int i=MAX_CACHE_NUM;i<list.size();i++)

{

String id=(String) list.get(i).getKey();

Object val=getFromDB(id);

cacheMap.put(id, new Cache(id,val));

}

public static void main(String[] args) throws InterruptedException {

Cache cache1=new Cache("1","value1");

Cache cache2=new Cache("2","value2");

Cache cache3=new Cache("3","value2");

Cache cache4=new Cache("4","value2");

Cache cache5=new Cache("5","value2");

Cache cache6=new Cache("6","value2");

Cache cache7=new Cache("7","value2");

CacheManager.putCache(cache1);

CacheManager.putCache(cache2);

CacheManager.putCache(cache3);

CacheManager.putCache(cache4);

CacheManager.putCache(cache5);

CacheManager.putCache(cache6);

CacheManager.putCache(cache7);

CacheManager.getCache("1");

CacheManager.getCache("2");

CacheManager.getCache("3");

CacheManager.getCache("4");

CacheManager.getCache("6");

CacheManager.getCache("5");

CacheManager.getCache("6");

refreshCaches();

Thread refreshTD=new Thread()

{

public void run()

{

while(true)

{

refreshCaches();

try {

Thread.sleep(1000);//每一秒刷新一次

} catch (InterruptedException e) {

e.printStackTrace();

}

};

refreshTD.start();

}

class Cache

{

String id;//相当于主键

Object val;

Date startdt;//标记新建时间

int usedcount=0;//标记使用次数

public Cache(String id,Object val)

{

this.id=id;

this.val=val;

this.startdt=new Date();

usedcount++;

}

public void setValue(Object val)

{

this.val=val;

}

public void addCount()

{

usedcount++;

}

public void showInfo()

{

System.out.println("Cache的ID是: "+id+" Cache的值是: "+val);

}

/**

* 往往刚刚新建的被访问机会是最少的

* o

* @return

public int compareTo(Object o) {

if(o instanceof Cache)

{

Cache c=(Cache) o;

if(this.usedcount>c.usedcount)

return 1;

else

return -1;

}

return 0;

}

3、FIFO(First In First Out ，先进先出)

算法是根据先进先出原理来淘汰数据的，实现上是最简单的一种,具体算法如下：

1. 新访问的数据插入FIFO队列尾部，数据在FIFO队列中顺序移动；

2. 淘汰FIFO队列头部的数据；

FIFO虽然实现很简单，但是命中率很低，实际上也很少使用这种算法。

实现方法可以和LRU想类似，只不过进行排序的时间指的不是最后使用时间，而是创建时间，这里就不花篇幅赘述。

http://blog.csdn.net/u011680348/article/details/47656401

转载于:https://my.oschina.net/xiaominmin/blog/1597232

你可能感兴趣的文章

文件系统、服务、防火墙、SELINUX——安全四大金刚

查看>>

RabbitMQ如何保证队列里的消息99.99%被消费？

查看>>

Lync Server 2010的部署系列_第五章准备 Active Directory 域服务

Python strip lstrip rstrip使用方法

String、StringBuffer和StringBuilder的区别

解决OracleDBConsoleorcl不能启动