146. LRU 缓存机制

什么是LRU？
很多时候尤其以前内存比较值钱的时候，我们空间比较宝贵，不会很大，那么就存在了重点数据和非重点数据，我们要在内存不够的时候有限保存重点数据淘汰非重点数据；LRU也就是说我们认为最近使用过的数据应该是重点数据，很久都没用过的数据应该是非重点数据，内存满了就优先删那些很久没用过的数据。
有哪些应用场景呢？
1.手机上划显示的任务列表，都是按照最近打开顺序排列的
2.redis的lru淘汰策略

思路：

• 1.利用linkedhashmap实现lru，因为其本身就存在lru策略，只需要使用即可，这部分代码放最下面
• 2.自己写lru

手写LRU算法思路：

• 关注LRU算法需要什么？第一快，要能做到快速增加快速查找，以及数据根据访问顺序淘汰
• 那么这里就想到用Map保障数据的随机访问速度，用双链表保障数据的快速增加
• 如下代码，我们定义了双链表的结点以及双链表的重要操作（都是我们做数据新增和删除需要的数据）

手写LRU算法代码：

class LRUCache {
        private HashMap<Integer,Node> lruCache;
        private DoubleList doubleList;
        private int capacity;

        public LRUCache(int capacity){
            this.capacity=capacity;
            lruCache=new HashMap<>(capacity);
            doubleList=new DoubleList();
        }

        public int get(int key){
            if (!lruCache.containsKey(key)){
                return -1;
            }

            int value = lruCache.get(key).val;
            //将顺序提前
            put(key,value);
            return value;
        }

        public void put(int key, int value) {
            //创建新结点
            Node node=new Node(key,value);

            if (lruCache.containsKey(key)){
                //删除旧结点
                doubleList.remove(lruCache.get(key));
                //新结点添加
                doubleList.addFirst(node);
                //更新map数据
                lruCache.put(key,node);
            }else {
                if (lruCache.size()==this.capacity){
                    Node last = doubleList.removeLast();
                    lruCache.remove(last.key);
                }
                doubleList.addFirst(node);
                lruCache.put(key,node);
            }

        }


        //构建node结点
        class Node {
            public int key, val;
            public Node next, prev;
            public Node(int k, int v) {
                this.key = k;
                this.val = v;
            }
        }
        //构建双链表
        class DoubleList {
            //头结点
            private Node head;
            //尾结点
            private Node tail;

            private int size=0;

            // 在链表头部添加节点 node，时间 O(1)
            public void addFirst(Node node){
                if (head==null){
                    head=tail=node;
                }else {
                    Node temp= head;
                    temp.prev=node;
                    node.next=temp;
                    head=node;
                }
            }

            // 删除链表中的 node 节点（node 一定存在）
            // 由于是双链表且给的是目标 Node 节点，时间 O(1)
            public void remove(Node node){
                if (node==head&&node==tail){
                    head=tail=null;
                }else if (tail==node){
                    tail.prev.next=null;
                    tail=node.prev;
                }else if (head==node){
                    head.next.prev=null;
                    head=node.next;
                }else{
                    node.prev.next=node.next;
                    node.next.prev=node.prev;
                }
            }

            // 删除链表中最后一个节点，并返回该节点，时间 O(1)
            public Node removeLast(){
                Node temp=tail;
                remove(tail);
                return temp;
            }

            // 返回链表长度，时间 O(1)
            public int size(){
                return size;
            }
        }

    }

LinkedHashMap实现lru代码：

class LRUCache extends LinkedHashMap<Integer, Integer> {
        private int capacity;

        public LRUCache(int capacity) {
            super(capacity, 0.75f, true);
            this.capacity=capacity;
        }

        public int get(int key) {
            return super.getOrDefault(key,-1);
        }

        public void put(int key, int value) {
            super.put(key,value);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return super.size()>capacity;
        }
    }