最近看到一个LRU的讨论，挺赶兴趣的，看了一些文章。自己也手动实现了一个，关键是选择合适的数据结构，然后对这个数据结构进行CRUD。

Java里面实现LRU缓存通常有两种选择，一种是使用LinkedHashMap，一种是自己设计数据结构，使用链表+HashMap

LRU释义

LRU 是 Least Recently Used 的简写，字面意思则是最近最少使用。
通常用于缓存的淘汰策略实现。

实现

LRU 存储是基于双向链表实现的。head 代表双向链表的表头，tail 代表尾部

实现要求

首先预先设置 LRU 的容量，如果存储满了，可以通过 O(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 O(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。

实现细节

save(key,value)

• 当Cache未满时，新的数据项只需插到双链表头部即可。时间复杂度为$O(1)$.
• 当Cache已满时，将新的数据项插到双链表头部，并删除双链表的尾结点即可。时间复杂度为$O(1)$.

get(key)

每次数据项被查询到时，都将此数据项移动到链表头部

代码

基于LinkedHashMap可以作为底层存储。

//类说明：利用LinkedHashMap实现简单的缓存， 必须实现removeEldestEntry方法，具体参见JDK文档 
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(Map.Entry<K, V> eldest) {
        return super.removeEldestEntry(eldest);
    }//第一种实现removeEldestEntry

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxCapacity;
    }//第二种实现removeEldestEntry

    @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();
        }
    }

    @Override
    public int size() {
        try {
            lock.lock();
            return super.size();
        }finally {
            lock.unlock();
        }
    }

    @Override
    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();
        }
    }
}

（完）