本文轉自?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) {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 ) {@Overrideprotected 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*/@Overrideprotected 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) ;}/*** 實現刪除過期對象 和 刪除訪問次數最少的對象 * */@Overrideprotected 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);}@Overrideprotected 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;}}

?

轉載于:https://www.cnblogs.com/kofxxf/p/4343575.html

總結

以上是生活随笔為你收集整理的【转】简单的java缓存实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。