南上海网站建设,做什么网站比较简单,网站优化推广公司推荐,永久免费建站程序目录
1.什么是LFU缓存#xff1f;
2.LFU的使用场景有哪些#xff1f;
3.LFU缓存的实现方式有哪些#xff1f;
4.put/get 函数实现具体功能 1.什么是LFU缓存#xff1f; LFU缓存是一个具有指定大小的缓存#xff0c;随着添加元素的增加#xff0c;达到容量的上限…目录
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),cachemap保证get/put操作的时间复杂度是O(1),freqMap中双向链表保证在头部和尾部添加元素的时间复杂度是O(1),自实现的双向链表保证删除任何元素的时间复杂度是O(1) 4.put/get 函数实现具体功能
put(keyvalue)函数功能实现
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的nodecache中也删除对应的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 getkey函数功能实现
分两种情况
1.key不在缓存中直接返回-1.
2.key在缓存中- freqMap 删除旧key中nodelist对应的node节点如果node的频率等于最小频率且删除后的nodelist为空更新最小频率的标记min为min1,- freq- freqMap中新key对应的nodelist新增node节点更新cache中的(keynode)信息 两个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;}}MapInteger, Node cache new HashMap();MapInteger, LinkedHashSetNode 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,freqMapcacheMap 新增(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中的keyLinkedHashSetNode 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) {LinkedHashSetNode 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) {LinkedHashSetNode 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 DoubleLinkedListN {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是默认的keyMapInteger, Node cache new HashMap();//freq的key是词频,相同词频的node链成一个双向链表MapInteger, DoubleLinkedListNode 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中的nodeDoubleLinkedListNode 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,freqMapcacheMap 新增(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为空更新minmin1)//3.更新cache,size不变(因为删除一个增加一个)node.value value;DoubleLinkedListNode 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中DoubleLinkedListNode 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) {DoubleLinkedListNode list freqMap.get(node.freq);if (list null) {list new DoubleLinkedList();}list.addNode(node);freqMap.put(node.freq, list);cache.put(node.key, node);}
}
