lru 转贴

简单LRU算法实现缓存

博客分类： java
算法JavaAccessJDK
    最简单的LRU算法实现，就是利用jdk的LinkedHashMap，覆写其中的removeEldestEntry(Map.Entry)方法即可，如下所示：
java 代码

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时，就移除最久没有被访问的项：
java 代码

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.ReentrantLock; 
 
/**
* 
* @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 Lock lock = new ReentrantLock(); 
 
    private final transient int maxCapacity; 
 
    private static int MINI_ACCESS = 10; 
 
    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 { 
            lock.lock(); 
            return this.map.containsKey(key); 
        } finally { 
            lock.unlock(); 
        } 
    } 
 
    public V put(K key, V value) { 
        try { 
            lock.lock(); 
            if ((map.size() > maxCapacity - 1) && !map.containsKey(key)) { 
                // System.out.println("开始"); 
                Set<Map.Entry<K, ValueEntry>> entries = this.map.entrySet(); 
                removeRencentlyLeastAccess(entries); 
            } 
            ValueEntry valueEntry = map.put(key, new ValueEntry(value)); 
            if (valueEntry != null) 
                return valueEntry.value; 
            else 
                return null; 
        } finally { 
            lock.unlock(); 
        } 
    } 
 
    /**
     * 移除最近最少访问
     */ 
    protected void removeRencentlyLeastAccess( 
            Set<Map.Entry<K, ValueEntry>> entries) { 
        // 最小使用次数 
        int 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 { 
            lock.lock(); 
            V value = null; 
            ValueEntry valueEntry = map.get(key); 
            if (valueEntry != null) { 
                // 更新访问时间戳 
                valueEntry.updateLastAccess(); 
                // 更新访问次数 
                valueEntry.count.incrementAndGet(); 
                value = valueEntry.value; 
            } 
            return value; 
        } finally { 
            lock.unlock(); 
        } 
    } 
 
    public void clear() { 
        try { 
            lock.lock(); 
            map.clear(); 
        } finally { 
            lock.unlock(); 
        } 
    } 
 
    public int size() { 
        try { 
            lock.lock(); 
            return map.size(); 
        } finally { 
            lock.unlock(); 
        } 
    } 
 
    public Collection<Map.Entry<K, V>> getAll() { 
        try { 
            lock.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 { 
            lock.unlock(); 
        } 
    } 
 
    class ValueEntry implements Serializable { 
        private V value; 
 
        private AtomicInteger count; 
 
        private AtomicLong lastAccess; 
 
        public ValueEntry(V value) { 
            this.value = value; 
            this.count = new AtomicInteger(0); 
            lastAccess = new AtomicLong(System.nanoTime()); 
        } 
         
        public void updateLastAccess() { 
            this.lastAccess.set(System.nanoTime()); 
        } 
 
    } 
}