缓存是一种进步数据读取性能的技术，在硬件设计、软件开发中都有着十分宽泛的利用，比方常见的 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}