如何实现LFU缓存（最近最少频率使用）

目录

1.什么是LFU缓存？

2.LFU的使用场景有哪些？

3.LFU缓存的实现方式有哪些？

4.put/get 函数实现具体功能

---

1.什么是LFU缓存？

        LFU缓存是一个具有指定大小的缓存，随着添加元素的增加，达到容量的上限，会最先移除最少使用频率的值。如果最少使用频率的值有多个，按照插入的先后顺序移除。要求put/get操作的时间复杂度O(1)

2.LFU的使用场景有哪些？

       redis 缓存的过期淘汰策略，leetcode 460. LFU 缓存设计等

3.LFU缓存的实现方式有哪些？

      LFU实现的底层数据结构图如下

     有两种实现方式，核心都是两个hashmash

     两个hashmap的含义是

      cache是 map(key,node)， key是正常的key值，value是node节点。

      freqMap是map(key,nodelist)， key是频率值，value是相同频率的key组成的双向链表。插入使用头插法，尾结点是最早未使用的节点，删除节点时删除尾结点。

      实现思路：

      要求get/put操作时间复杂度是O(1),cache（map）保证get/put操作的时间复杂度是O(1),freqMap中双向链表保证在头部和尾部添加元素的时间复杂度是O(1),自实现的双向链表保证删除任何元素的时间复杂度是O(1)

4.put/get 函数实现具体功能

put(key，value)函数功能实现

cache Map(key,node) 其中key是添加元素的key
freqMap map(key,nodelist)其中 key是频率
分三种情况
1.key不在在cache中不存在,没有达到容量上限- freq++- nodelist新增node,freqMap新增（key,nodelist）,cacheMap 新增(key,node),size++
2.key在cache中不存在,达到容量上限- 获得最小频率的nodelist中的第一个元素,freqMap中删除的listnode的node，cache中也删除对应的key- freq++- nodelist新增node,freqMap新增（key,nodelist）和cacheMap新增（key,node）- size不变(因为删除了一个元素，添加了一个元素)
3.key在cache中
步骤如下：-  更新value值-  freqMap中删除的listnode的node,如果当前频率是最小值且list列表为空,min++-  freq++-  nodelist新增node,freqMap新增（key,nodelist）,cache新增（key,node）

get（key）函数功能实现

分两种情况
1.key不在缓存中，直接返回-1.
2.key在缓存中- freqMap 删除旧key中nodelist对应的node节点（如果node的频率等于最小频率，且删除后的nodelist为空，更新最小频率的标记min为min+1）,- freq++- freqMap中新key对应的nodelist新增node节点，更新cache中的(key，node)信息

两个hashmap,其中nodelist使用jdk自带的linkedhashset的代码实现如下

package com.mashibing.my;import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;public class LFUCache3 {class Node {int key;int value;int freq;public Node(int key, int value) {this.key = key;this.value = value;}}Map<Integer, Node> cache = new HashMap<>();Map<Integer, LinkedHashSet<Node>> freqMap = new HashMap<>();int size;int capacity;int min;public static void main(String[] args) {LFUCache3 cache = new LFUCache3(2);cache.put(1, 1);cache.put(2, 2);// 返回 1System.out.println(cache.get(1));cache.put(3, 3);    // 去除 key 2// 返回 -1 (未找到key 2)System.out.println(cache.get(2));// 返回 3System.out.println(cache.get(3));cache.put(4, 4);    // 去除 key 1// 返回 -1 (未找到 key 1)System.out.println(cache.get(1));// 返回 3System.out.println(cache.get(3));// 返回 4System.out.println(cache.get(4));}public LFUCache3(int capacity) {this.capacity = capacity;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}freqInc(node);return node.value;}//put分三种情况//1.key在cache中不存在,没有达到容量上限，freq值增加1,freqMap，cacheMap 新增(key,value)，size++//2.key在cache中不存在,达到容量上限，获得最小频率的set,删除第一个元素，cache中也删除，//同时freqMap和cacheMap(key,value),size不变，因为删除了一个元素，添加了一个元素//3.key在cache中//步骤如下//3.1 更新value值//3.2 删除freqMap从对应key的set集合中删除元素,如果当前频率是最小值且list列表为空,min++//3.3. freq++//3.4 freqMap新增(key,value),更新cache中的valuepublic void put(int key, int value) {Node node = cache.get(key);if (node == null) {Node n = new Node(key, value);if (size == capacity) {//移除最小容量的元素//移除map中的keyLinkedHashSet<Node> set1 = freqMap.get(min);if (set1 != null) {//获得列表的第一个元素Node o = set1.iterator().next();set1.remove(o);cache.remove(o.key);}n.freq++;AddNode(n);} else {n.freq++;AddNode(n);size++;min = 1;}} else {node.value = value;//先从旧的set中删除nodefreqInc(node);}}public void freqInc(Node node) {LinkedHashSet<Node> set = freqMap.get(node.freq);//时间复杂度O(n) 需要自实现频次链表set.remove(node);if (node.freq == min && set.size() == 0) {min++;}node.freq++;AddNode(node);}public void AddNode(Node node) {LinkedHashSet<Node> set = freqMap.get(node.freq);if (set == null) {set = new LinkedHashSet<>();}set.add(node);freqMap.put(node.key, set);cache.put(node.key, node);}
}

两个hashmap,nodelist使用自实现的linkedlist的代码实现如下

package com.mashibing.my;import java.util.HashMap;
import java.util.Map;//双map+自实现linkedlist
public class LFUCache4 {class Node {int key;int value;int freq;Node pre;Node next;public Node(int key, int value) {this.key = key;this.value = value;}public Node() {}}class DoubleLinkedList<N> {Node head, tail;//初始化双向循环链表public DoubleLinkedList() {head = new Node();tail = new Node();head.next = tail;tail.pre = head;}//头插法,新加入的节点放在节点的头部,最久未访问的节点放在尾部public void addNode(Node n) {Node next = head.next;n.next = next;n.pre = head;head.next = n;next.pre = n;}public void deleteNode(Node n) {n.pre.next = n.next;n.next.pre = n.pre;}public boolean isEmpty() {return head.next == tail;}}//cache的key是默认的keyMap<Integer, Node> cache = new HashMap<>();//freq的key是词频,相同词频的node链成一个双向链表Map<Integer, DoubleLinkedList<Node>> freqMap = new HashMap<>();//标记最小频率int min;//lFU最大容量int capacity;//当前容量int size;//    [2],[3,1],[2,1],[2,2],[4,4],[2]]public static void main(String[] args) {LFUCache4 lFUCache4 = new LFUCache4(2);lFUCache4.put(1, 1);lFUCache4.put(2, 2);// 返回 1System.out.println(lFUCache4.get(1));lFUCache4.put(3, 3);    // 去除 key 2// 返回 -1 (未找到key 2)System.out.println(lFUCache4.get(2));// 返回 3System.out.println(lFUCache4.get(3));lFUCache4.put(4, 4);    // 去除 key 1// 返回 -1 (未找到 key 1)System.out.println(lFUCache4.get(1));// 返回 3System.out.println(lFUCache4.get(3));// 返回 4System.out.println(lFUCache4.get(4));}public LFUCache4(int capacity) {this.capacity = capacity;}public int get(int key) {Node node = cache.get(key);if (node == null) {return -1;}//1.删除旧的freqmap中的node,freq++,新增freqMap中的nodeDoubleLinkedList<Node> list = freqMap.get(node.freq);list.deleteNode(node);if (node.freq == min && list.isEmpty()) {min++;}node.freq++;addNode(node);return node.value;}//put分三种情况//1.key在cache中不存在,没有达到容量上限，freq值增加1,freqMap，cacheMap 新增(key,value)，size++//2.key在cache中不存在,达到容量上限，获得最小频率的set,删除第一个元素，cache中也删除，//同时freqMap和cacheMap(key,value),size不变，因为删除了一个元素，添加了一个元素//3.key在cache中//步骤如下//3.1 更新value值//3.2 删除freqMap从对应key的set集合中删除元素,如果当前频率是最小值且list列表为空,min++//3.3. freq++//3.4 freqMap新增(key,value),更新cache中的valuepublic void put(int key, int value) {Node node = cache.get(key);if (node != null) {//1.更新value//2.删除旧的词频的list中node,freq++增加新node到新词频的list集合中(删除旧的词频，//如果旧词频是min,且list为空，更新min=min+1)//3.更新cache,size不变(因为删除一个，增加一个)node.value = value;DoubleLinkedList<Node> list = freqMap.get(node.freq);list.deleteNode(node);if (node.freq == min && list.isEmpty()) {min++;}node.freq++;addNode(node);} else {Node n = new Node(key, value);if (size == capacity) {//1.删除最小频率的node，更新对应的map//2.添加新node到freqmap,cache中DoubleLinkedList<Node> list = freqMap.get(min);Node pre = list.tail.pre;list.deleteNode(pre);if (pre.freq == min && list.isEmpty()) {min++;}cache.remove(pre.key);size--;}n.freq++;addNode(n);size++;min = 1;}}public void addNode(Node node) {DoubleLinkedList<Node> list = freqMap.get(node.freq);if (list == null) {list = new DoubleLinkedList<>();}list.addNode(node);freqMap.put(node.freq, list);cache.put(node.key, node);}
}