首页 / 缓存 / 【转】简单的java缓存实现
【转】简单的java缓存实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【转】简单的java缓存实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7453字，纯文字阅读大概需要11分钟。
内容图文
本文转自 http://my.oschina.net/u/866190/blog/188712
提到缓存，不得不提就是缓存算法(淘汰算法)，常见算法有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) {
returnfalse;
}
return lastAccess + ttl < System.currentTimeMillis();
}
V2 getObject() {
lastAccess = System.currentTimeMillis();
accessCount++;
return cachedObject;
}
}
protected Map<K,CacheObject<K,V>> cacheMap;
privatefinal ReentrantReadWriteLock cacheLock = new ReentrantReadWriteLock();
privatefinal Lock readLock = cacheLock.readLock();
privatefinal Lock writeLock = cacheLock.writeLock();
protectedint cacheSize; // 缓存大小 , 0 -> 无限制protectedboolean existCustomExpire ; //是否设置默认过期时间publicint getCacheSize() {
return cacheSize;
}
protectedlong defaultExpire; // 默认过期时间, 0 -> 永不过期public AbstractCacheMap(int cacheSize ,long defaultExpire){
this.cacheSize = cacheSize ;
this.defaultExpire = defaultExpire ;
}
publiclong getDefaultExpire() {
return defaultExpire;
}
protectedboolean isNeedClearExpiredObject(){
return defaultExpire > 0 || existCustomExpire ;
}
publicvoid put(K key, V value) {
put(key, value, defaultExpire );
}
publicvoid 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) {
returnnull;
}
if (co.isExpired() == true) {
cacheMap.remove(key);
returnnull;
}
return co.getObject();
}
finally {
readLock.unlock();
}
}
publicfinalint eliminate() {
writeLock.lock();
try {
return eliminateCache();
}
finally {
writeLock.unlock();
}
}
/**
* 淘汰对象具体实现
*
* @return*/protectedabstractint eliminateCache();
publicboolean isFull() {
if (cacheSize == 0) {//o -> 无限制returnfalse;
}
return cacheMap.size() >= cacheSize;
}
publicvoid remove(K key) {
writeLock.lock();
try {
cacheMap.remove(key);
}
finally {
writeLock.unlock();
}
}
publicvoid clear() {
writeLock.lock();
try {
cacheMap.clear();
}
finally {
writeLock.unlock();
}
}
publicint size() {
return cacheMap.size();
}
publicboolean 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
protectedboolean removeEldestEntry(
Map.Entry<K, CacheObject<K, V>> eldest) {
return LRUCache.this.removeEldestEntry(eldest);
}
};
}
privateboolean removeEldestEntry(Map.Entry<K, CacheObject<K, V>> eldest) {
if (cacheSize == 0)
returnfalse;
return size() > cacheSize;
}
/**
* 只需要实现清除过期对象就可以了,linkedHashMap已经实现LRU
*/
@Override
protectedint 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
protectedint 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
protectedint 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;
}
}
原文：http://www.cnblogs.com/kofxxf/p/4343575.html
内容总结
以上是互联网集市为您收集整理的【转】简单的java缓存实现全部内容，希望文章能够帮你解决【转】简单的java缓存实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】