文档章节

简单的java缓存实现

温佐镜
 温佐镜
发布于 2013/12/29 19:43
字数 1651
阅读 13327
收藏 59

提到缓存,不得不提就是缓存算法(淘汰算法),常见算法有LRU、LFU和FIFO等算法,每种算法各有各的优势和缺点及适应环境。

1、LRU(Least Recently Used ,最近最少使用)
算法根据数据的最近访问记录来淘汰数据,其原理是如果数据最近被访问过,将来被访问的几概率相对比较高,最常见的实现是使用一个链表保存缓存数据,详细具体算法如下:
1. 新数据插入到链表头部;
2. 每当缓存数据命中,则将数据移到链表头部;
3. 当链表满的时候,将链表尾部的数据丢弃;


2、LFU(Least Frequently Used,最不经常使用)
算法根据数据的历史访问频率来淘汰数据,其原理是如果数据过去被访问次数越多,将来被访问的几概率相对比较高。LFU的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。
具体算法如下:
1. 新加入数据插入到队列尾部(因为引用计数为1);
2. 队列中的数据被访问后,引用计数增加,队列重新排序;
3. 当需要淘汰数据时,将已经排序的列表最后的数据块删除;


3、FIFO(First In First Out ,先进先出)
算法是根据先进先出原理来淘汰数据的,实现上是最简单的一种,具体算法如下:
1. 新访问的数据插入FIFO队列尾部,数据在FIFO队列中顺序移动;
2. 淘汰FIFO队列头部的数据;


评价一个缓存算法好坏的标准主要有两个,一是命中率要高,二是算法要容易实现。当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。LFU效率要优于LRU,且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录,一旦数据访问模式改变,LFU需要更长时间来适用新的访问模式,即:LFU存在历史数据影响将来数据的“缓存污染”效用。FIFO虽然实现很简单,但是命中率很低,实际上也很少使用这种算法。

基于现有jdk类库,我们可以很容易实现上面的缓存算法

首先定义缓存接口类


/**
 * 缓存接口
 * @author Wen
 *
 */
public interface Cache<K,V> {
	/**
	 * 返回当前缓存的大小
	 * 
	 * @return  
	 */
	int size();
	
	/**
	 * 返回默认存活时间
	 * 
	 * @return
	 */
	long getDefaultExpire();
	
	/**
	 * 向缓存添加value对象,其在缓存中生存时间为默认值
	 * 
	 * @param key
	 * @param value
	 */
	void put(K key ,V value) ;
	
	/**
	 * 向缓存添加value对象,并指定存活时间
	 * @param key
	 * @param value
	 * @param expire  过期时间
	 */
	void put(K key ,V value , long expire ) ;
	
	/**
	 * 查找缓存对象
	 * @param key
	 * @return
	 */
	V get(K key);
	
	/**
	 * 淘汰对象
	 * 
	 * @return  被删除对象大小
	 */
	int eliminate();
	
	/**
	 * 缓存是否已经满
	 * @return
	 */
	boolean isFull();

	/**
	 * 删除缓存对象
	 * 
	 * @param key
	 */
	void remove(K key);

	/**
	 * 清除所有缓存对象
	 */
	void clear();

	/**
	 * 返回缓存大小
	 * 
	 * @return  
	 */
	int getCacheSize();

	/**
	 * 缓存中是否为空
	 */
	boolean isEmpty();

}



基本实现抽象类



import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 默认实现
 */
public abstract class AbstractCacheMap<K,V> implements Cache<K,V> {

	class CacheObject<K2,V2> {
		CacheObject(K2 key, V2 value, long ttl) {
			this.key = key;
			this.cachedObject = value;
			this.ttl = ttl;
			this.lastAccess = System.currentTimeMillis();
		}

		final K2 key;
		final V2 cachedObject;
		long lastAccess;		// 最后访问时间
		long accessCount;		// 访问次数
		long ttl;				// 对象存活时间(time-to-live)

		boolean isExpired() {
			if (ttl == 0) {
				return false;
			}
			return lastAccess + ttl < System.currentTimeMillis();
		}
		V2 getObject() {
			lastAccess = System.currentTimeMillis();
			accessCount++;
			return cachedObject;
		}
    }

	protected Map<K,CacheObject<K,V>> cacheMap;

	private final ReentrantReadWriteLock cacheLock = new ReentrantReadWriteLock();
	private final Lock readLock = cacheLock.readLock();
	private final Lock writeLock = cacheLock.writeLock();



	protected int cacheSize;      // 缓存大小 , 0 -> 无限制
	
	protected  boolean existCustomExpire ; //是否设置默认过期时间
	
	public int getCacheSize() {
		return cacheSize;
	}

	protected long defaultExpire;     // 默认过期时间, 0 -> 永不过期
	
	public AbstractCacheMap(int cacheSize ,long defaultExpire){
		this.cacheSize  = cacheSize ;
		this.defaultExpire  = defaultExpire ;
	}

	
	public long getDefaultExpire() {
		return defaultExpire;
	}


	protected boolean isNeedClearExpiredObject(){
		return defaultExpire > 0 || existCustomExpire ;
	}

	
	public void put(K key, V value) {
		put(key, value, defaultExpire );
	}


	public void put(K key, V value, long expire) {
		writeLock.lock();

		try {
			CacheObject<K,V> co = new CacheObject<K,V>(key, value, expire);
			if (expire != 0) {
				existCustomExpire = true;
			}
			if (isFull()) {
				eliminate() ;
			}
			cacheMap.put(key, co);
		}
		finally {
			writeLock.unlock();
		}
	}



	/**
	 * {@inheritDoc}
	 */
	public V get(K key) {
		readLock.lock();

		try {
			CacheObject<K,V> co = cacheMap.get(key);
			if (co == null) {
				return null;
			}
			if (co.isExpired() == true) {
				cacheMap.remove(key);
				return null;
			}

			return co.getObject();
		}
		finally {
			readLock.unlock();
		}
	}
	
	public final int eliminate() {
		writeLock.lock();
		try {
			return eliminateCache();
		}
		finally {
			writeLock.unlock();
		}
	}
	
	/**
	 * 淘汰对象具体实现
	 * 
	 * @return
	 */
	protected abstract int eliminateCache(); 


	
	public boolean isFull() {
		if (cacheSize == 0) {//o -> 无限制
			return false;
		}
		return cacheMap.size() >= cacheSize;
	}

	
	public void remove(K key) {
		writeLock.lock();
		try {
			cacheMap.remove(key);
		}
		finally {
			writeLock.unlock();
		}
	}

	
	public void clear() {
		writeLock.lock();
		try {
			cacheMap.clear();
		}
		finally {
			writeLock.unlock();
		}
	}

	public int size() {
		return cacheMap.size();
	}

	
	public boolean isEmpty() {
		return size() == 0;
	}
}



LRU缓存实现类



import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LRU  实现
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class LRUCache<K, V> extends AbstractCacheMap<K, V> {

	public LRUCache(int cacheSize, long defaultExpire) {
		
		super(cacheSize , defaultExpire) ;

		//linkedHash已经实现LRU算法 是通过双向链表来实现,当某个位置被命中,通过调整链表的指向将该位置调整到头位置,新加入的内容直接放在链表头,如此一来,最近被命中的内容就向链表头移动,需要替换时,链表最后的位置就是最近最少使用的位置
		this.cacheMap = new LinkedHashMap<K, CacheObject<K, V>>( cacheSize +1 , 1f,true ) {

			@Override
			protected boolean removeEldestEntry(
					Map.Entry<K, CacheObject<K, V>> eldest) {

				return LRUCache.this.removeEldestEntry(eldest);
			}

		};
	}

	private boolean removeEldestEntry(Map.Entry<K, CacheObject<K, V>> eldest) {

		if (cacheSize == 0)
			return false;

		return size() > cacheSize;
	}

	/**
	 * 只需要实现清除过期对象就可以了,linkedHashMap已经实现LRU
	 */
	@Override
	protected int eliminateCache() {

		if(!isNeedClearExpiredObject()){ return 0 ;}
		
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
			}
		}
		
		return count;
	}

}



LFU实现类



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

//LFU实现
public class LFUCache<K,V> extends AbstractCacheMap<K, V> {
	

	public LFUCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new HashMap<K, CacheObject<K,V>>(cacheSize+1) ;
	}

	/**
	 * 实现删除过期对象 和 删除访问次数最少的对象 
	 * 
	 */
	@Override
	protected int eliminateCache() {
		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		int count  = 0 ;
		long minAccessCount = Long.MAX_VALUE  ;
		while(iterator.hasNext()){
			CacheObject<K, V> cacheObject = iterator.next();
			
			if(cacheObject.isExpired() ){
				iterator.remove(); 
				count++ ;
				continue ;
			}else{
				minAccessCount  = Math.min(cacheObject.accessCount , minAccessCount)  ;
			}
		}
		
		if(count > 0 ) return count ;
		
		if(minAccessCount != Long.MAX_VALUE ){
			
			iterator = cacheMap.values().iterator();
			
			while(iterator.hasNext()){
				CacheObject<K, V> cacheObject = iterator.next();
				
				cacheObject.accessCount  -=  minAccessCount ;
				
				if(cacheObject.accessCount <= 0 ){
					iterator.remove();
					count++ ;
				}
				
			}
			
		}
		
		return count;
	}

}



FIFO实现类



import java.util.Iterator;
import java.util.LinkedHashMap;
/**
 * FIFO实现
 * @author Wen
 *
 * @param <K>
 * @param <V>
 */
public class FIFOCache<K, V> extends AbstractCacheMap<K, V> {

	public FIFOCache(int cacheSize, long defaultExpire) {
		super(cacheSize, defaultExpire);
		cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
	}

	@Override
	protected int eliminateCache() {

		int count = 0;
		K firstKey = null;

		Iterator<CacheObject<K, V>> iterator = cacheMap.values().iterator();
		while (iterator.hasNext()) {
			CacheObject<K, V> cacheObject = iterator.next();

			if (cacheObject.isExpired()) {
				iterator.remove();
				count++;
			} else {
				if (firstKey == null)
					firstKey = cacheObject.key;
			}
		}

		if (firstKey != null && isFull()) {//删除过期对象还是满,继续删除链表第一个
			cacheMap.remove(firstKey);
		}

		return count;
	}

}




© 著作权归作者所有

共有 人打赏支持
温佐镜
粉丝 11
博文 32
码字总数 11554
作品 0
广州
程序员
加载中

评论(8)

De_Ja_Vu
De_Ja_Vu

引用来自“祥林会跟你远走高飞”的评论

这个代码就是jodd.cache包下面的
你说的对
a
anjieanzhi
请问博主如何构建defaultExpire这个参数呢?
温佐镜
温佐镜

引用来自“反正不管”的评论

FIFO实现类中,14行:
cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
这里使用LinkedHashMap是什么原因呢?
迭代遍历LinkedHashMap(内部维护一个双向链表)时,取得“键值对”的顺序是插入次序,或者是最近最少使用的次序,其中一个构造函数 LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) ,其中accessOrder=false就是按插入顺序访问,符合FIFO特性
反正不管
FIFO实现类中,14行:
cacheMap = new LinkedHashMap<K, CacheObject<K, V>>(cacheSize + 1);
这里使用LinkedHashMap是什么原因呢?
祥林会跟你远走高飞
祥林会跟你远走高飞
这个代码就是jodd.cache包下面的
yuweic
yuweic
新手,学习了,谢谢前辈的分享!!!
蓝杖奥利奥
蓝杖奥利奥
学习了,但是有个小问题,LinkedHashMap中的get操作并不是一个纯读操作,会导致双向链表的顺序改变,使用ReentrantReadWriteLock读写锁还是会有get时的线程安全问题,不知道博主有没有解决这个问题?
kidbei
kidbei
学习了
justlive1/oxygen

oxygen 轻量级Java框架 介绍 一个轻量级Java框架 oxygen-core 核心部分 基于cglib的aop实现 提供缓存管理和基于注解的缓存,内置LocalCache和Ehcache实现,可扩展 配置管理,支持${attrs.key...

justlive1
10/08
0
0
实际项目中是选用Map还是选用Redis作为缓存?为什么?

参考网页 https://segmentfault.com/q/1010000009106416 实际项目中是选用Map还是选用Redis作为缓存?为什么? 具体选择Map还是Redis作为缓存,要看具体的需求,具体的应用场景 本地缓存和分...

karma123
06/27
0
0
有关 SoftReference 的一些事实

Java 的 SoftReference 有很多年都没有被人惦记了。在 Javadoc 里, 它的描述是这样: ”虚拟机在抛出 OutOfMemoryError 之前会保证所有的软引用对象已被清除。此外,没有任何约束保证软引用将...

长源
2013/08/12
0
0
MUI调用原生自定义方法实现计算缓存与清空缓存

由于项目需要最近在做webapp开发用的是MUI框架,自己本来是做原生开发的,在开发的时候有一个需求是实现计算缓存和清除缓存的功能,原生java方法实现轻轻松松,网上代码一大把,不过是webap...

妳的姓氏我的名
09/29
0
0
从多核硬件架构,看Java内存模型

在了解Java内存模型之前,先来看一下多核硬件架构。 我们应该都知道,计算机在执行程序的时候,每条指令都是在CPU中执行的,而执行的时候,又免不了要和数据打交道。而计算机上面的数据,是存...

消失er
09/02
0
0

没有更多内容

加载失败,请刷新页面

加载更多

一切都靠大数据:滴滴已封禁4.3万人员、车辆

这段时间以来,滴滴出行相继出炉了各种整改措施,包括自身安全建设和外部社会共建,昨日就刚刚宣布正在筹备建立安全监督顾问委员会。 据媒体最新报道,9月30日,上海市交通委员会执法总队、上...

linuxCool
21分钟前
2
0
awk命令用法介绍

10月18日任务 9.6/9.7 awk 1.awk(上)(下) 1.awk 分段操作功能 指定分隔符,并把第一段打印出来,不会改动文件内容 将所有内容打印出来 awk 没有指定分隔符号,则会默认用空格或者空白字符...

hhpuppy
59分钟前
3
0
Spring Cloud Eureka Server高可用之:在线扩容

本文共 1591字,阅读大约需要 6分钟 ! 概述 业务微服务化以后,我们要求服务高可用,于是我们可以部署多个相同的服务实例,并引入负载均衡机制。而微服务注册中心作为微服务化系统的重要单元...

CodeSheep
今天
2
0
内网esxi主机上安装CoreOS虚拟机

CoreOS是一个为专门运行容器而设计的轻量级linux发行版,旨在通过轻量的系统架构和灵活的应用程序部署能力简化数据中心的维护成本和复杂度。它没有包管理工具,运行容器化应用以提供服务;默...

hiwill
今天
1
0
20181018 上课截图

![](https://oscimg.oschina.net/oscnet/49f66c08ab8c59a21a3b98889d961672f30.jpg) ![](https://oscimg.oschina.net/oscnet/a61bc2d618b403650dbd4bf68a671fabecb.jpg)......

小丑鱼00
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部