每日一题-LFU缓存

爱被打了一巴掌 2023-07-23 03:51 77阅读 0赞

今天是2020年4月5日，也是开始记录每日一题的第一天。

### 题目描述 ###

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。  
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。  
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶：  
你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
    
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1);       // 返回 1
    cache.put(3, 3);    // 去除 key 2
    cache.get(2);       // 返回 -1 (未找到key 2)
    cache.get(3);       // 返回 3
    cache.put(4, 4);    // 去除 key 1
    cache.get(1);       // 返回 -1 (未找到 key 1)
    cache.get(3);       // 返回 3
    cache.get(4);       // 返回 4

### 题目分析 ###

在本题目中，维护一个双线链表。双向链表中记录了该链表的频次，即链表中节点被访问的频次。head、tail链表为虚拟链表，不存储任何节点。

在put操作时，如果此时size==capacity，则需要删除最不经常使用的节点，即tail.pre链表的最后一个节点。此时如果链表为空，需要将此链表一同删除。在get操作时，当前节点的访问次数增加，需要将此节点从旧的链表中删除，放入新的频次的链表中。如下图所示。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MTM1NDIx_size_16_color_FFFFFF_t_70]

### 代码实现 ###

public class LFUCache {
        /**
         * 存储缓存的内容，Node中除了value值外，还有key、freq、所在doublyLinkedList、所在doublyLinkedList中的postNode、所在doublyLinkedList中的preNode，具体定义在下方。
         */
        Map<Integer, Node> cache;
        /**
         * firstLinkedList.post 是频次最大的双向链表
         */
        DoublyLinkedList firstLinkedList;
        /**
         * lastLinkedList.pre 是频次最小的双向链表，满了之后删除 lastLinkedList.pre.tail.pre 这个Node即为频次最小且访问最早的Node
         */
        DoublyLinkedList lastLinkedList;
        int size;
        int capacity;
    
        public LFUCache3(int capacity) {
            cache = new HashMap<>(capacity);
            firstLinkedList = new DoublyLinkedList();
            lastLinkedList = new DoublyLinkedList();
            firstLinkedList.post = lastLinkedList;
            lastLinkedList.pre = firstLinkedList;
            this.capacity = capacity;
        }
    
        public int get(int key) {
            Node node = cache.get(key);
            if (node == null) {
                return -1;
            }
            // 该key访问频次+1
            freqInc(node);
            return node.value;
        }
    
        public void put(int key, int value) {
            if (capacity == 0) {
                return;
            }
    
            Node node = cache.get(key);
            // 若key存在，则更新value，访问频次+1
            if (node != null) {
                node.value = value;
                freqInc(node);
            } else {
                // 若key不存在
                if (size == capacity) {
                    // 如果缓存满了，删除lastLinkedList.pre这个链表（即表示最小频次的链表）中的tail.pre这个Node（即最小频次链表中最先访问的Node），如果该链表中的元素删空了，则删掉该链表。
                    cache.remove(lastLinkedList.pre.tail.pre.key);
                    lastLinkedList.removeNode(lastLinkedList.pre.tail.pre);
                    size--;
                    if (lastLinkedList.pre.head.post == lastLinkedList.pre.tail) {
                        removeDoublyLinkedList(lastLinkedList.pre);
                    }
                }
                // cache中put新Key-Node对儿，并将新node加入表示freq为1的DoublyLinkedList中，若不存在freq为1的DoublyLinkedList则新建。
                Node newNode = new Node(key, value);
                cache.put(key, newNode);
                if (lastLinkedList.pre.freq != 1) {
                    DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(1);
                    addDoublyLinkedList(newDoublyLinedList, lastLinkedList.pre);
                    newDoublyLinedList.addNode(newNode);
                } else {
                    lastLinkedList.pre.addNode(newNode);
                }
                size++;
            }
        }
    
        /**
         * node的访问频次 + 1
         */
        void freqInc(Node node) {
            // 将node从原freq对应的双向链表里移除, 如果链表空了则删除链表。
            DoublyLinkedList linkedList = node.doublyLinkedList;
            DoublyLinkedList preLinkedList = linkedList.pre;
            linkedList.removeNode(node);
            if (linkedList.head.post == linkedList.tail) {
                removeDoublyLinkedList(linkedList);
            }
            // 将node加入新freq对应的双向链表，若该链表不存在，则先创建该链表。
            node.freq++;
            if (preLinkedList.freq != node.freq) {
                DoublyLinkedList newDoublyLinedList = new DoublyLinkedList(node.freq);
                addDoublyLinkedList(newDoublyLinedList, preLinkedList);
                newDoublyLinedList.addNode(node);
            } else {
                preLinkedList.addNode(node);
            }
        }
    
        /**
         * 增加代表某1频次的双向链表
         */
        void addDoublyLinkedList(DoublyLinkedList newDoublyLinedList, DoublyLinkedList preLinkedList) {
            newDoublyLinedList.post = preLinkedList.post;
            newDoublyLinedList.post.pre = newDoublyLinedList;
            newDoublyLinedList.pre = preLinkedList;
            preLinkedList.post = newDoublyLinedList;
        }
    
        /**
         * 删除代表某1频次的双向链表
         */
        void removeDoublyLinkedList(DoublyLinkedList doublyLinkedList) {
            doublyLinkedList.pre.post = doublyLinkedList.post;
            doublyLinkedList.post.pre = doublyLinkedList.pre;
        }
    }
    
    
    class Node {
        int key;
        int value;
        int freq = 1;
        /**
         * Node所在频次的双向链表的前继Node
         */
        Node pre;
        /**
         * Node所在频次的双向链表的后继Node
         */
        Node post;
        /**
         * Node所在频次的双向链表
         */
        DoublyLinkedList doublyLinkedList;
    
        public Node() {
        }
    
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    
    class DoublyLinkedList {
        /**
         * 该双向链表表示的频次
         */
        int freq;
        /**
         * 该双向链表的前继链表（pre.freq < this.freq）
         */
        DoublyLinkedList pre;
        /**
         * 该双向链表的后继链表 (post.freq > this.freq)
         */
        DoublyLinkedList post;
        /**
         * 该双向链表的头节点，新节点从头部加入，表示最近访问
         */
        Node head;
        /**
         * 该双向链表的尾节点，删除节点从尾部删除，表示最久访问
         */
        Node tail;
    
    
        public DoublyLinkedList() {
            head = new Node();
            tail = new Node();
            head.post = tail;
            tail.pre = head;
        }
    
    
        public DoublyLinkedList(int freq) {
            head = new Node();
            tail = new Node();
            head.post = tail;
            tail.pre = head;
            this.freq = freq;
        }
    
        void removeNode(Node node) {
            node.pre.post = node.post;
            node.post.pre = node.pre;
    
        }
    
        void addNode(Node node) {
            node.post = head.post;
            head.post.pre = node;
            head.post = node;
            node.pre = head;
            node.doublyLinkedList = this;
        }
    }

此题目思路参考了LeetCode的题解：[https://leetcode-cn.com/problems/lfu-cache/solution/yan-jiu-ban-tian-gei-tian-jie-de-jie-fa-zuo-liao-z/][https_leetcode-cn.com_problems_lfu-cache_solution_yan-jiu-ban-tian-gei-tian-jie-de-jie-fa-zuo-liao-z]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3MTM1NDIx_size_16_color_FFFFFF_t_70]: /images/20230528/00a403ef7b3f437ea0d08a29da79b3e1.png
[https_leetcode-cn.com_problems_lfu-cache_solution_yan-jiu-ban-tian-gei-tian-jie-de-jie-fa-zuo-liao-z]: https://leetcode-cn.com/problems/lfu-cache/solution/yan-jiu-ban-tian-gei-tian-jie-de-jie-fa-zuo-liao-z/