JAVA Map实现LRU原理

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”

Java中的LinkedHashMap已经实现了90%的LRU算法。
1、需要理解HashMap的实现包括Hash数组和双向节点链表，HashMap的搜索包括Hash定位和遍历比较两个过程，不同的子节点要求HashCode和equal都不同才算不同。

HashMap的Hash数组和节点链表

2、（错误理解）LRU实现过程如下图示，每次访问提升被访问的节点到所在链表的首位，搜索中，Hash是免不了的，但是遍历过程可以化简：

LRU原理

3、LRU最近最少算法，在本地缓存用的比较多，自带更新和销毁，缓存没有再找其他重方法查询，因此可以叫做一级缓存或者热缓存。缓存的node个数是有限的。
LinkedHashMap重写了迭代器、contain()方法，利用双向链表快速访问；

只需要实现淘汰策略的linkedHashMap就是一个很不错的LRU实现了。

image.png

public class LruMap extends LinkedHashMap {
    // 容量
    private int cap;

    public LruMap(int cap) {
        // 初始化，hashMap为指定size
        super(cap, 0.7f, true);
        this.cap = cap;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        if (size() > cap) {
            return true;
        } else {
            return false;
        }
    }
    public static void main(String[] args) {
        LruMap lruMap = new LruMap(3);
        lruMap.put(1, 1);
        System.out.println(lruMap);
        lruMap.put(2, 1);
        System.out.println(lruMap);
        lruMap.put(3, 1);
        System.out.println(lruMap);
        lruMap.put(4, 1);
        System.out.println(lruMap);
        lruMap.put(5, 1);
        System.out.println(lruMap);
    }
}

以上实现的问题：

• 线程不安全
• ....