继承LinkedHashMap实现简单的LRU算法

当我们写的项目或应用有了一定流量后，查询数据库就会特别频繁，此时我们可以考虑使用Java自带的HashMap或者ConcurrentHashMap，但是这样实现的缓存机制会有个问题：内存会无限制的增长，所以HashMap很快也被淘汰了

我们在查询redis的时候，希望可以本地缓存放一些热点数据，使用HashMap显然无法满足这种需求

HashMap也不是就完全没用了，在一些场景下作为缓存，当不需要淘汰机制的时候，比如利用反射，如果每次都用反射去搜索Method、Field，性能会很低，此时如果用HashMap缓存起来，性能将提高很多

常见的三种淘汰算法：FIFO、LRU、LFU

LRU的背景

LRU：least-recently-used最近最少使用算法，是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据。

LRU原理

用一个特殊的栈来保存当前正在使用的各个页面的页面号，当一个新的进程访问某个页面时，将该页面号压入栈顶，如果栈中的内存不够，就把栈底的页面号移除，这样栈顶始终都是最新被访问的页面编号，而栈底则是最近最久未被访问的页面号

实现

我们可以通过继承LinkedHashMap，重写removeEldestEntry方法

/**
 * 重写LinkedHashMap的removeEldestEntry方法
 * 在Put的时候判断如果为true就会删除最老的
 * @param eldest
 * @return
 */
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
    return size() > max;
}

在LinkedHashMap中维护了一个entry链表（用来存放key和value的对象），在每一次get或者put的时候都会把插入的新entry，或者查询到的老entry放在链表表尾。

Considerations

直接使用LinkedHashMap实现并不是线程安全的，要做到线程安全，就需要加上synchronized修饰符

具体实现代码

/**
 * 三种常见的淘汰算法：FIFO、LRU、LFU
 * LRUMap
 * 每次访问数据都会将其放在我们的队尾，如果需要淘汰数据，就只需要淘汰队首即可。
 * 如果有个数据在1个小时的前59分钟访问了1万次(可见这是个热点数据),
 * 再后一分钟没有访问这个数据，但是有其他的数据访问，就导致了我们这个热点数据被淘汰。
 */
public class LRUMap extends LinkedHashMap {
    private final int max;
    private Object lock;

    /**
     * 在LinkedHashMap中维护了一个entry（用来存放key和value的对象）链表，在每一次get或者put的时候
     * 都会把插入的新entry，或者查询到的老entry放在链表的表尾
     *
     * 在构造方法中设置的大小特意为max*1.4
     *
     * 在下面的removeEldestEntry方法中只需要size() > max就淘汰，这样我们这个map就永远也走不到
     * 扩容的逻辑了
     *
     * 通过重写LinkedHashMap中的几个简单的方法实现LRUMap
     * @param max
     * @param lock
     */
    public LRUMap(int max, Object lock) {
        // 不用扩容
        super((int) (max * 1.4f), 0.75f, true);
        this.max = max;
        this.lock = lock;
    }

    /**
     * 重写LinkedHashMap的removeEldestEntry方法
     * 在Put的时候判断如果为true就会删除最老的
     * @param eldest
     * @return
     */
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > max;
    }

    // 当其他线程试图访问被synchronized修饰的代码块时会被阻塞，只有当前拿到锁的进程可以访问代码块
    public Object getValue(Object key) {
        synchronized (lock) {
            return get(key);
        }
    }

    public void putValue(Object key, Object value) {
        synchronized (lock) {
            put(key, value);
        }
    }

    public boolean removeValue(Object key) {
        synchronized (lock) {
            Object remove = remove(key);
            return remove != null;
        }
    }

    public boolean removeAll() {
        synchronized (lock) {
            clear();
            return true;
        }
    }
}