个人觉得LinkedHashMap 存在的意义就是为了实现 LRU 算法。

public class LinkedHashMap
     
       extends HashMap
      
           implements Map
       
        {    public LinkedHashMap(int initialCapacity,                         float loadFactor,                         boolean accessOrder) {        super(initialCapacity, loadFactor);        this.accessOrder = accessOrder;    }    ....
       
      
     

1、LinkedHashMap 的 <K,V>用HashMap存储。

2、LinkedHashMap 的Key 用双向链表维护。

　　当用get 和 set 方法的时候，内部维护key的双向链表的结构顺序会变动。

3、accessOrder：false 基于插入顺序  true  基于访问顺序（get一个元素后，这个元素被加到最后，使用了LRU  最近最少被使用的调度算法）。

4、removeEldestEntry方法，考虑清楚是否要重载。如果最大容量固定，则需要重载，否则表现为自适应。

protected boolean removeEldestEntry(Map.Entry
     
       eldest) {        return false;    }
     

 

 

最简单的LRU算法实现

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 
     
       * @param 
      
        */public class LRULinkedHashMap
       
         extends LinkedHashMap
        
          {    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
         
           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
          
           
            > getAll() { try { lock.lock(); return new ArrayList
            
             
              >(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 
     
       * @param 
      
        */public class LRUCache
       
         implements Serializable {    private static final int DEFAULT_CAPACITY = 100;    protected Map
        
          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
         
          (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
          
           
            > 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
            
             
              > entries) { // 最小使用次数 long least = 0; // 访问时间最早 long earliest = 0; K toBeRemovedByCount = null; K toBeRemovedByTime = null; Iterator
              
               
                > it = entries.iterator(); if (it.hasNext()) { Map.Entry
                
                  valueEntry = it.next(); least = valueEntry.getValue().count.get(); toBeRemovedByCount = valueEntry.getKey(); earliest = valueEntry.getValue().lastAccess.get(); toBeRemovedByTime = valueEntry.getKey(); } while (it.hasNext()) { Map.Entry
                 
                   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
                  
                   
                    > getAll() { try { readLock.lock(); Set
                    
                      keys = map.keySet(); Map
                     
                       tmp = new HashMap
                      
                       (); for (K key : keys) { tmp.put(key, map.get(key).value); } return new ArrayList
                       
                        
                         >(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()); } }}
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

 

参考：