缓存算法也叫作淘汰算法，主要是为了当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");
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("1");
CacheManager.getCache("2");
CacheManager.getCache("3");
CacheManager.getCache("3");
CacheManager.getCache("4");
CacheManager.getCache("4");
CacheManager.getCache("6");
CacheManager.getCache("5");
CacheManager.getCache("5");
CacheManager.getCache("6");
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);
}
/**
* 往往刚刚新建的被访问机会是最少的
* @param 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
相关推荐
对于Java实现，通常会抽象出一个通用的缓存接口，包含put、get、evict（淘汰）等方法，然后针对每种策略实现具体的缓存类。在设计时，需注意线程安全问题，特别是在多线程环境中，可能需要使用`synchronized`关键字...
本项目实现了一个模拟器，用于演示和比较四种不同的页面置换算法：FIFO（先进先出）、LFU（最不常用）、LRU（最近最少使用）以及OPT（最佳页面置换）。界面使用Microsoft Foundation Class (MFC)库来创建，使得用户...
本篇文章将详细介绍三种常见的缓存替换策略：LRU（Least Recently Used）、LFU（Least Frequently Used）和FIFO（First In First Out），并探讨它们在C++中的实现。 首先，LRU缓存策略基于“最近最少使用的”原则。...
FIFO算法的实现相对简单，通常使用队列数据结构来维护缓存中的数据项。每当有新的请求，如果缓存已满，就删除队列头部（即最早添加的元素），然后将新元素添加到队列尾部。这种策略并不考虑数据的访问频率，可能导致...
本项目专注于通过图形化方式模拟三种常见的页面替换算法：FIFO（先进先出）、LRU（最近最少使用）和LFU（最不经常使用）。这些算法是虚拟内存系统中解决缓存冲突的关键策略，用于决定何时以及如何将数据从主存移入或...
本篇文章将深入探讨Java中的缓存实现，包括基础概念、常见缓存库以及如何在实际项目中应用。 1. **缓存基础** - 缓存的基本原理是基于局部性原理，即最近使用的数据很可能在未来还会被再次使用。 - 缓存分为内存...
ShiftOne Object Cache提供了一种基础的Java对象缓存机制，实现包括FIFO、LRU和LFU在内的多种缓存策略，允许开发者调整最大元素数量和生存时间。 WhirlyCache是一个内存对象缓存，强调速度和可配置性，旨在通过缓存...
在这个主题下，我们将探讨Java缓存的基本概念、常用框架以及实现策略。 首先，让我们了解什么是缓存。缓存是一种存储技术，它允许我们在短时间内快速访问之前已经计算或检索过的信息，避免了重复计算或从慢速存储...
常见的策略有三种：先进先出策略FIFO、最少使用策略LFU、最近最少使用策略LRU。 那么，如何用链表来实现LRU缓存淘汰策略呢？链表是一种稍微复杂一点的数据结构，相比数组，它并不需要一块连续的内存空间来存储，...
4. **缓存策略**：包括LRU（Least Recently Used，最近最少使用）、LFU（Least Frequently Used，最不经常使用）和FIFO（First In First Out，先进先出）等，用于决定何时从缓存中移除元素。 三、Ehcache配置 ...
4. **缓存策略**：Ehcache提供了多种缓存策略，如LRU（Least Recently Used，最近最少使用）、LFU（Least Frequently Used，最不经常使用）和FIFO（First In First Out，先进先出）。这些策略决定了当缓存达到其最大...
对于CPU缓存这样的高速缓存，LRU（最近最少使用）或LFU（最少频繁使用）等算法可能会提供更好的性能，因为它们考虑了数据访问的局部性和频率。因此，在后续的开发中，可以考虑引入更复杂但效率更高的缓存替换策略，...
常见的策略有三种：先进先出策略 FIFO（First In，First Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）。LRU 缓存淘汰算法是通过链表来实现的。链表是一种稍微...
2. 使用缓存策略：如LRU、LFU（最不经常使用）或FIFO（先进先出）来管理缓存项。 3. 设置合理的过期时间：避免缓存数据长时间无效，同时要考虑数据更新的实时性。 4. 考虑并发和线程安全：在多线程环境中，确保缓存...
Java缓存技术是提高应用程序性能的关键所在，尤其是在处理大量数据时。Javaeye创始人分享的这份“java缓存技术深入剖析”旨在帮助开发者更好地理解和应用缓存机制。以下是对该主题的详细阐述： 一、缓存的基本概念 ...
本项目提供的是一款基于Java实现的缓存系统，据描述显示，它已经在实际的公司环境中得到了良好的应用，能够承受高达10万级别的并发访问，这表明其在高负载场景下仍能保持稳定性和效率。 首先，我们要理解什么是缓存...
缓存的使用策略包括 LRU（Least Recently Used）最近最少使用、LFU（Least Frequently Used）最不经常使用和 FIFO（First In First Out）先进先出等。这些策略用于决定何时清除缓存中的数据，以保持有效的空间利用率...
常见的缓存淘汰算法有LFU、LRU、ARC、FIFO、MRU等。 1. 最不经常使用算法（LFU）：LFU缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法，最低访问数的条目首先被移除。这个方法并不经常使用，...