简单LRU算法实现缓存-update2

update1:第二个实现，读操作不必要采用独占锁，缓存显然是读多于写，读的时候一开始用独占锁是考虑到要递增计数和更新时间戳要加锁，不过这两个变量都是采用原子变量，因此也不必采用独占锁，修改为读写锁。 update2:一个错误，老是写错关键字啊， LRUCache的 maxCapacity应该声明为volatile，而不是transient。       最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示： import  java.util.ArrayList; import  java.util.Collection; import  java.util.LinkedHashMap; import  java.util.concurrent.locks.Lock; import  java.util.concurrent.locks.ReentrantLock; import  java.util.Map; /**  * 类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档  *   *  @author  dennis  *   *  @param  <K>  *  @param  <V>   */ public   class  LRULinkedHashMap < K, V >   extends  LinkedHashMap < K, V >  {      private   final   int  maxCapacity;      private   static   final   float  DEFAULT_LOAD_FACTOR  =   0.75f ;      private   final  Lock lock  =   new  ReentrantLock();      public  LRULinkedHashMap( int  maxCapacity) {          super (maxCapacity, DEFAULT_LOAD_FACTOR,  true );          this .maxCapacity  =  maxCapacity;     }     @Override      protected   boolean  removeEldestEntry(java.util.Map.Entry < K, V >  eldest) {          return  size()  >  maxCapacity;     }     @Override      public   boolean  containsKey(Object key) {          try  {             lock.lock();              return   super .containsKey(key);         }  finally  {             lock.unlock();         }     }          @Override      public  V get(Object key) {          try  {             lock.lock();              return   super .get(key);         }  finally  {             lock.unlock();         }     }     @Override      public  V put(K key, V value) {          try  {             lock.lock();              return   super .put(key, value);         }  finally  {             lock.unlock();         }     }      public   int  size() {          try  {             lock.lock();              return   super .size();         }  finally  {             lock.unlock();         }     }      public   void  clear() {          try  {             lock.lock();              super .clear();         }  finally  {             lock.unlock();         }     }      public  Collection < Map.Entry < K, V >>  getAll() {          try  {             lock.lock();              return   new  ArrayList < Map.Entry < K, V >> ( super .entrySet());         }  finally  {             lock.unlock();         }     } }     如果你去看LinkedHashMap的源码可知，LRU算法是通过双向链表来实现，当某个位置被命中，通过调整链表的指向将该位置调整到头位置，新加入的内容直接放在链表头，如此一来，最近被命中的内容就向链表头移动，需要替换时，链表最后的位置就是最近最少使用的位置。     LRU算法还可以通过计数来实现，缓存存储的位置附带一个计数器，当命中时将计数器加1，替换时就查找计数最小的位置并替换，结合访问时间戳来实现。这种算法比较适合缓存数据量较小的场景，显然，遍历查找计数最小位置的时间复杂度为O(n)。我实现了一个，结合了访问时间戳，当最小计数大于MINI_ACESS时(这个参数的调整对命中率有较大影响），就移除最久没有被访问的项： package  net.rubyeye.codelib.util.concurrency.cache; import  java.io.Serializable; import  java.util.ArrayList; import  java.util.Collection; import  java.util.HashMap; import  java.util.Iterator; import  java.util.Map; import  java.util.Set; import  java.util.concurrent.atomic.AtomicInteger; import  java.util.concurrent.atomic.AtomicLong; import  java.util.concurrent.locks.Lock; import  java.util.concurrent.locks.ReadWriteLock; import  java.util.concurrent.locks.ReentrantLock; import  java.util.concurrent.locks.ReentrantReadWriteLock; /**  *   *  @author  dennis 类说明：当缓存数目不多时，才用缓存计数的传统LRU算法  *  @param  <K>  *  @param  <V>   */ public   class  LRUCache < K, V >   implements  Serializable {      private   static   final   int  DEFAULT_CAPACITY  =   100 ;      protected  Map < K, ValueEntry >  map;      private   final  ReadWriteLock lock  =   new  ReentrantReadWriteLock();      private   final  Lock readLock  =  lock.readLock();      private   final  Lock writeLock  =  lock.writeLock();      private   final volatile int  maxCapacity;  //保持可见性      public   static   int  MINI_ACCESS  =   5 ;      public  LRUCache() {          this (DEFAULT_CAPACITY);     }      public  LRUCache( int  capacity) {          if  (capacity  <=   0 )              throw   new  RuntimeException( " 缓存容量不得小于0 " );          this .maxCapacity  =  capacity;          this .map  =   new  HashMap < K, ValueEntry > (maxCapacity);     }      public   boolean  ContainsKey(K key) {          try  {             readLock.lock();              return   this .map.containsKey(key);         }  finally  {             readLock.unlock();         }     }      public  V put(K key, V value) {          try  {             writeLock.lock();              if  ((map.size()  >  maxCapacity  -   1 )  &&   ! map.containsKey(key)) {                  //  System.out.println("开始");                 Set < Map.Entry < K, ValueEntry >>  entries  =   this .map.entrySet();                 removeRencentlyLeastAccess(entries);             }             ValueEntry new_value  =   new  ValueEntry(value);             ValueEntry old_value  =  map.put(key, new_value);              if  (old_value  !=   null ) {                 new_value.count  =  old_value.count;                  return  old_value.value;             }  else                  return   null ;         }  finally  {             writeLock.unlock();         }     }      /**      * 移除最近最少访问       */      protected   void  removeRencentlyLeastAccess(             Set < Map.Entry < K, ValueEntry >>  entries) {          //  最小使用次数          long  least  =   0 ;          //  访问时间最早          long  earliest  =   0 ;         K toBeRemovedByCount  =   null ;         K toBeRemovedByTime  =   null ;         Iterator < Map.Entry < K, ValueEntry >>  it  =  entries.iterator();          if  (it.hasNext()) {             Map.Entry < K, ValueEntry >  valueEntry  =  it.next();             least  =  valueEntry.getValue().count.get();             toBeRemovedByCount  =  valueEntry.getKey();             earliest  =  valueEntry.getValue().lastAccess.get();             toBeRemovedByTime  =  valueEntry.getKey();         }          while  (it.hasNext()) {             Map.Entry < K, ValueEntry >  valueEntry  =  it.next();              if  (valueEntry.getValue().count.get()  <  least) {                 least  =  valueEntry.getValue().count.get();                 toBeRemovedByCount  =  valueEntry.getKey();             }              if  (valueEntry.getValue().lastAccess.get()  <  earliest) {                 earliest  =  valueEntry.getValue().count.get();                 toBeRemovedByTime  =  valueEntry.getKey();             }         }          //  System.out.println("remove:" + toBeRemoved);          //  如果最少使用次数大于MINI_ACCESS，那么移除访问时间最早的项(也就是最久没有被访问的项）          if  (least  >  MINI_ACCESS) {             map.remove(toBeRemovedByTime);         }  else  {             map.remove(toBeRemovedByCount);         }     }      public  V get(K key) {          try  {             readLock.lock();             V value  =   null ;             ValueEntry valueEntry  =  map.get(key);              if  (valueEntry  !=   null ) {                  //  更新访问时间戳                 valueEntry.updateLastAccess();                  //  更新访问次数                 valueEntry.count.incrementAndGet();                 value  =  valueEntry.value;             }              return  value;         }  finally  {             readLock.unlock();         }     }      public   void  clear() {          try  {             writeLock.lock();             map.clear();         }  finally  {             writeLock.unlock();         }     }      public   int  size() {          try  {             readLock.lock();              return  map.size();         }  finally  {             readLock.unlock();         }     }      public   long  getCount(K key) {          try  {             readLock.lock();             ValueEntry valueEntry  =  map.get(key);              if  (valueEntry  !=   null ) {                  return  valueEntry.count.get();             }              return   0 ;         }  finally  {             readLock.unlock();         }     }      public  Collection < Map.Entry < K, V >>  getAll() {          try  {             readLock.lock();             Set < K >  keys  =  map.keySet();             Map < K, V >  tmp  =   new  HashMap < K, V > ();              for  (K key : keys) {                 tmp.put(key, map.get(key).value);             }              return   new  ArrayList < Map.Entry < K, V >> (tmp.entrySet());         }  finally  {             readLock.unlock();         }     }      class  ValueEntry  implements  Serializable {          private  V value;          private  AtomicLong count;          private  AtomicLong lastAccess;          public  ValueEntry(V value) {              this .value  =  value;              this .count  =   new  AtomicLong( 0 );             lastAccess  =   new  AtomicLong(System.nanoTime());         }          public   void  updateLastAccess() {              this .lastAccess.set(System.nanoTime());         }     } } 文章转自庄周梦蝶  ，原文发布时间2007-09-29