1. 什么是LRU

LRU（Least Recently Used），即最近最少使用策略，是一种常用的页面置换算法。
比如当缓存数据在内存越来越多，以至于无法存放即将到来的新缓存数据时，就必须扔掉最不常用的缓存数据。
最新被访问的数据【get、put操作】的‘优先级’是最高的，当缓存达到一定容量时，之前最早被访问的数据将会被清除。
Redis 就使用了LRU作为缓存淘汰策略。

2、设计一个简单的LRUCache【leetcode146】

LRUCache支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
要求get、put操作时间复杂度为O(1).

3、思路

LRU可以用哈希链表实现，即哈希表+双向链表，链表中的node存储了同时存储了缓存的【key和value】，哈希表中存储key和node，这样get操作时能通过key查找到node的地址获取value值，同时get、put操作时间复杂度为O(1)。
在双向链表中，把最新操作【get、put操作】过的node移动到队尾。那么越靠近对尾的元素就是最新被操作的元素。
当缓存达到一定的容量时候，要删除队头的元素。

image.png

4、实现

哈希表+双向链表

    /**
     * 设计双向链表的Node结构
     * key:表示缓存的key，存在Node是为了在后边删除缓存的操作中，删除map和双向链表中的记录
     * val:表示缓存的值
     */
    class Node {
        int key;
        int val;
        Node pre;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    class DoubleList {
        Node head;
        Node tail;

        public DoubleList() {
        }

        /**
         * 因为新加入的节点是最新被访问的，所以将新加入的节点放入对尾
         * @param node
         */
        public void addToTail(Node node) {
            if (node == null) {
                return;
            }
            if (this.head == null) {
                this.head = node;
                this.tail = node;
            } else {
                this.tail.next = node;
                node.pre = this.tail;
                this.tail = node;
            }
        }

        /**
         * 将某个节点放到对尾
         * @param node
         */
        public void moveNodeToTail(Node node) {
            if (node == null || node == this.tail) {
                return;
            }
            if (node == this.head) {
                this.head = this.head.next;
                this.head.pre = null;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            this.tail.next = node;
            node.pre = this.tail;
            node.next = null;
            // 更新tail不要忘了
            this.tail = node;
        }

        /**
         * 删除对头，也就是删除最没有被访问的元素
         * @return
         */
        public Node removeHead() {
            if (this.head == null) {
                return null;
            }
            Node res = this.head;
            // 如果只有一个节点
            if (this.head == this.tail) {
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.pre = null;
            }
            return res;
        }
    }


    /**
     * LRU缓存结构
     */
    class LRUCache {

        Map<Integer, Node> map = new HashMap<>();
        DoubleList doubleList = new DoubleList();
        int capacity;

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        /**
         * 获取指定key 的 value值，同时需要更新被访问的元素的优先级，将其放到对尾
         * @param key
         * @return
         */
        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            Node res = map.get(key);
            doubleList.moveNodeToTail(res);
            return res.val;
        }

        /**
         * 插入一对新的缓存，如果队列已满，需要先删除队头
         * @param key
         * @param value
         */

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                Node node = map.get(key);
                node.val = value;
                map.put(key, node);
                doubleList.moveNodeToTail(node);
            } else {
                Node node = new Node(key, value);
                while (map.size() >= this.capacity) {
                    Node removedNode = doubleList.removeHead();
                    // 这时候就用到了node中的key
                    map.remove(removedNode.key);
                }
                map.put(key, node);
                doubleList.addToTail(node);
            }
        }
    }

    @Test
    public void testFun() {
        LRUCache lruCache = new LRUCache(1);
        lruCache.put(2, 1);
        System.out.println(lruCache.get(2));
        lruCache.put(3, 2);
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.get(3));
    }