[leetcode]-460 LFU Cache

红太狼 2023-06-28 06:21 75阅读 0赞

题目：

Design and implement a data structure for [Least Frequently Used (LFU)][Least Frequently Used _LFU] cache. It should support the following operations: `get` and `put`.

`get(key)` - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.  
`put(key, value)` - Set or insert the value if the key is not already present. When the cache reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least **recently** used key would be evicted.

Note that the number of times an item is used is the number of calls to the `get` and `put` functions for that item since it was inserted. This number is set to zero when the item is removed.

思路：

LFU (Least Frequently Used) 基于访问频率的缓存策略

按每个缓存块的被访问频率将缓存中的各块排序,当缓存空间已满时,替换掉缓存队列中访问频率最低的一项。

1)队列中的数据被访问时，引用计数增加，队列重新排序；

2)插入数据时，如果数据在队列中已经存在，更新数据的值，引用计数增加；如果是新数据，当队列容量不满时，直接插入，引用计数为0，队列容量满时，需要淘汰一个数据，将已经排序的列表最后的数据块（引用计数最小的）删除。

数据结构设计：

两个HashMap： freqList和map，

freqList用来存储每个引用计数count和key集合的映射，map用来存储每个key与value/count的映射

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqaDAzMDI_size_16_color_FFFFFF_t_70][]

源码：

import java.util.HashMap;
    import java.util.LinkedHashSet;
    
    public class LFUCache {
    
        private class Node{
            public int key;
            public int value;
            public int count;
    
            public Node(int key, int value, int count){
                this.key = key;
                this.value = value;
                this.count = count;
            }
        }
    
        private int capacity;
        //k: key, v: Node
        private HashMap<Integer, Node> cache;
        //k: count frequency, v: key of Node
        private HashMap<Integer, LinkedHashSet<Integer>> freqList;
        //min: flag to record the least frequency
        private int min = -1;
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.cache = new HashMap();
            this.freqList = new HashMap();
            this.freqList.put(0, new LinkedHashSet<>());
            this.min = -1;
        }
    
        public int get(int key) {
            if(this.cache.containsKey(key)){
                System.out.println("has key:" + key);
                Node node = this.cache.get(key);
                node.count++;
                this.cache.put(key, node);
                //update the node in freq list
                this.freqList.get(node.count-1).remove(key);
                if(!this.freqList.containsKey(node.count)){
                    LinkedHashSet set = new LinkedHashSet();
                    set.add(key);
                    this.freqList.put(node.count,set);
                }else{
                    this.freqList.get(node.count).add(key);
                }
                //update min
                if(min == node.count-1 && freqList.get(min).isEmpty()){
                    min = node.count;
                }
                return node.value;
            }
            return -1;
        }
    
        public void put(int key, int value) {
            if(this.capacity == 0)
                return;
            //existing key
            if(this.cache.containsKey(key)){
                Node node = this.cache.get(key);
                node.value = value;
                this.cache.put(key, node);
                get(key);
                return;
            }
            //cache is full, remove one
            if(this.cache.size() == this.capacity){
                //remove the least frequently 
                //least recently used key when more than one
                int evict = this.freqList.get(min).iterator().next();
                System.out.println("evict" + evict);
                System.out.println("min" + min);
                cache.remove(evict);
                this.freqList.get(min).remove(evict);
            }
            //add new key
            Node node = new Node(key, value, 0);
            this.cache.put(key, node);
            //update the node in freq list
            this.freqList.get(0).add(key);
            min = 0;
        }
    
    }

[Least Frequently Used _LFU]: https://en.wikipedia.org/wiki/Least_frequently_used
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqaDAzMDI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200107210131907.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xqaDAzMDI=,size_16,color_FFFFFF,t_70