提到缓存，不得不提就是缓存算法(淘汰算法)，常见算法有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;   }  }

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;   }    }

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;   }    }

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;   }    }