LRU策略的实现

LRU策略的实现

LRU：一种缓存淘汰策略，即当缓存空间已满时，优先淘汰最近最少使用的数据。

我们实现这个算法要做到put和get方法时间复杂度为O（1），那么就可以总结出cache缓存数据结构必须具有如下条件：

1、cache 中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。

2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val；

3、每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置快速插入和删除元素。

哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

java中就具有这样的数据结构——LinkedHashMap，弥补了HashMap中元素没有顺序的弊端。

之所以链表中保存了key是因为要通过链表中的元素反向找到map中的元素，如进行删除操作时，map和list中都要删除，而双向链表也是为了找到前驱元素，删除时确保时间复杂度为O(1)

代码实现，手动实现LinkedHashMap

class Node {
        //链表中的节点
        public int key;//对应哈希中的key
        public int val;//值

        public Node next;//下一个节点
        public Node prev;//上一个节点

        public Node(int k, int v) {//初始化节点
            this.key = k;
            this.val = v;
        }
    }

    class DoubleList{
        //头尾虚节点
        private Node head, tail;
        //链表元素数
        private int size;

        public DoubleList(){
            //初始化双向链表的数据
            //用双向链表的原因是为了删除时找到前驱结点，确保时间复杂度是O(1)
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        //在链表尾部添加x节点，时间O(1)
        //最近使用的数据
        public void addLast(Node x){
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            size++;
        }

        //删除链表中的x节点（x一定存在，因为有HashMap）
        //由于是双链表且给的是目标Node节点，时间O(1)
        public void remove(Node x){
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }


        //删除链表中的第一个节点，并返回给该节点，时间O(1)
        public Node removeFirst(){
            if(head.next == tail){
                return null;
            }
            Node first = head.next;
            remove(first);
            return first;
        }

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

    class LRUCache{
        //key -> Node(key, val)
        private HashMap<Integer, Node> map;
        //Node(k1, v1) <->Node(k2, v2)...
        private DoubleList cache;
        //最大容量
        private int cap;

        public LRUCache(int capacity){
            this.cap = capacity;
            map = new HashMap<>();
            cache = new DoubleList();
        }


        /** 将某个key提升为最近使用的 */
        private void makeRecently(int key){
            Node x = map.get(key);
            //先从链表中删除这个节点
            cache.remove(x);
            //重新插到队尾
            cache.addLast(x);
        }

        /** 添加最近使用的元素 */
        private void addRecently(int key, int val){
            Node x = new Node(key, val);
            //链表尾部就是最近使用元素
            cache.addLast(x);
            //在map中添加key的映射
            map.put(key, x);
        }

        /** 删除某一个key */
        private void deleteKey(int key){
            Node x = map.get(key);
            //从链表中删除
            cache.remove(x);
            //从map中删除
            map.remove(x);
        }


        /** 删除最久未使用元素 */
        private void removeLeastRecently(){
            //链表头部的第一个元素就是最久未使用的
            Node deleteNode = cache.removeFirst();
            //从map中删除它的key
            int deleteKey = deleteNode.key;
            map.remove(deleteKey);
        }

        /** 最终对外的接口get */
        public int get(int key){
            if(!map.containsKey(key)){
               return -1;
            }
            //将该数据提升为最近使用的
            makeRecently(key);
            return map.get(key).val;
        }


        /** 最终对外的接口put */
        public void put(int key, int val){
            //已经存过这个数据
            if(map.containsKey(key)){
                //删除旧的数据
                deleteKey(key);

                //新插入的数据作为最近使用的数据
                addRecently(key, val);
                return;
            }
            //这个数据没存过

            //容量已经存满了
            if(cap == cache.size){
                //删除最久未使用的元素
                removeLeastRecently();
            }

            //添加为最近使用的元素
            addRecently(key, val);
        }

    }

代码实现2，java封装LinkedHashMap

class LRUCache {
        int cap;
        LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
        public LRUCache(int capacity) {
            this.cap = capacity;
        }

        public int get(int key) {
            if (!cache.containsKey(key)) {
                return -1;
            }
            // 将 key 变为最近使用
            makeRecently(key);
            return cache.get(key);
        }

        public void put(int key, int val) {
            if (cache.containsKey(key)) {
                // 修改 key 的值
                cache.put(key, val);
                // 将 key 变为最近使用
                makeRecently(key);
                return;
            }

            if (cache.size() >= this.cap) {
                // 链表头部就是最久未使用的 key
                int oldestKey = cache.keySet().iterator().next();
                cache.remove(oldestKey);
            }
            // 将新的 key 添加链表尾部
            cache.put(key, val);
        }

        private void makeRecently(int key) {
            int val = cache.get(key);
            // 删除 key，重新插入到队尾
            cache.remove(key);
            cache.put(key, val);
        }
    }