关于java:实现LRU缓存淘汰算法

缓存是一种进步数据读取性能的技术，在硬件设计、软件开发中都有着十分宽泛的利用，比方常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小无限，当缓存被用满时，哪些数据应该被清理进来，哪些数据应该被保留？这就须要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO（First In，First Out）、起码应用策略 LFU（Least Frequently Used）、最近起码应用策略 LRU（Least Recently Used）。
​

leetcode-266
思路是这样的：咱们保护一个有序单链表，越凑近链表尾部的结点是越早之前拜访的。当有一个新的数据被拜访时，咱们从链表头开始程序遍历链表。

1. 如果此数据之前曾经被缓存在链表中了，咱们遍历失去这个数据对应的结点，并将其从原来的地位删除，而后再插入到链表的尾部。
2. 如果此数据没有在缓存链表中，又能够分为两种状况：如果此时缓存未满，则将此结点直接插入到链表的尾部；如果此时缓存已满，则链表头结点删除，将新的数据结点插入链表的头部。

代码如下：

public class LRUCache{
    int capacity;
    Map<Integer, Integer> map;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<>();}
    /**
     * @Title: get
     * @Description: 往缓存获取元素
     * @param key:
     * @return int
     * @Author: Ansen
     */
    public int get(int key) {if (!map.containsKey(key)) {return -1;}
        // 先删除旧的地位，再放入新地位
        Integer value = map.remove(key);
        map.put(key, value);
        return value;
    }

    /**
     * @Title: put
     * @Description: 往缓存增加元素
     * @param key:
     * @param value:
     * @return void
     * @Author: Ansen
     */
    public void put(int key, int value) {if (map.containsKey(key)) {map.remove(key);
            map.put(key, value);
            return;
        }
        map.put(key, value);
        // 超出 capacity，删除最久没用的, 利用迭代器删除第一个
        if (map.size() > capacity) {map.remove(map.entrySet().iterator().next().getKey());
        }
    }
    /**
     * @Description: 测试
     * @param args:
     * @return void
     * @Author: Ansen
     */
    public static void main(String[] args) {LRUCache lruCache = new LRUCache(4);
        lruCache.put(0,0);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.put(4,4);
        lruCache.put(5,5);
        lruCache.put(6,6);
        int i = lruCache.get(3);
        System.out.println(lruCache.map);
    }
}

输入：
{4=4, 5=5, 6=6, 3=3}