如何实现LFU缓存(最近最少频率使用)

article/2025/10/17 3:28:28

目录

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);}
}


http://chatgpt.dhexx.cn/article/q3uMLJiL.shtml

相关文章

LFU缓存策略算法

在之前的文章中&#xff0c;我们介绍了如何设计一个LRU算法–如何设计LRU Cache算法&#xff0c;今天我们再聊一聊另一种缓存策略LFU。目前博主个人博客已经搭建发布&#xff0c;后期相关文章也会发布在上面&#xff0c;大家有兴趣可以去上面学习&#xff0c;点击即可前往文青乐…

国内编程学习网站

在本文中&#xff0c;我们介绍了来自两岸三地的编程学习网站&#xff0c;通过它们&#xff0c;不仅可以一窥国内App开发的发展现状&#xff0c;而且这些网站各有特点&#xff0c;无论是主打游戏学习还是视频学习&#xff0c;对于想要自学的开发者而言&#xff0c;都是个好去处。…

如何高效的自学编程

现在的社会对于IT人才的需求越来越大&#xff0c;程序员的薪资水平在各个行业中都算比较高的。所以很多人都想往IT行业发展&#xff0c;已经身处这个行业的人也需要不断的学习新的知识&#xff0c;因为IT行业的技术更新实在是太快了&#xff0c;不像传统行业那样是越老越吃香。…

电脑编程自学(零基础自学编程怎么入门)

电脑编程自学入手:确定编程学习的方向。编程语言有多种:php,C++,C,C#,JAVA,Python等,每种语言都有不同的优缺点,可以根据自己的兴趣方向选择一门编程语言作为自己的学习目标。 基础阶段的语法学习。学习任何一门编程语言,都需要掌握其编程的语法规则,可以通过阅读一…

自学编程的 6 个致命误区

嗨&#xff0c;小伙伴们大家好&#xff0c;我是沉默王二。本篇文章来和大家聊聊自学编程中的一些误区——这是我在 B 站上看了羊哥的一期视频后有感而发的文章。因为确实有很多读者也曾私信问过我这些方面的问题&#xff0c;很有代表性&#xff0c;所以我就结合自己的亲身体会来…

java编程自学app_Java编程自学软件

Java编程自学软件是是一款Java学习软件。Java编程自学软件为用户提供Java语言&#xff0c;ISh和SQL 数据库编程等技术方便用户学习Java知识。有需要自学Java编程的小伙伴们可在华军软件园下载Java编程自学软件。 Java编程自学软件功能特色 专业化、具体化。 有真正意义上的实战…

c语言 软件编程入门自学,软件编程入门自学

文章目录[隐藏] 软件编程入门自学 作为界面&#xff0c;MFC方便上手&#xff0c;QT也不错。您好&#xff0c;自学编程建议从C语言开始。可以说60%~80%的程序员都是从C语言开始的。 众所周知&#xff0c;编程语言分为结构化编程语言和面向对象编程语言。结构化编程语言比面向对象…

自学编程,收藏好这7个免费网站,可省你上万块钱的学费

如果你要自学编程&#xff0c;一定要收藏好这7个网站&#xff0c;上面免费的优质教程很多&#xff0c;完全可以省去你上万块钱的学费&#xff01; 话不多说&#xff0c;直接上干货&#xff01; 第一个&#xff0c;W3school 一个主打图文教程的网站&#xff0c;不管是前端开发…

蛙跳算法优化VMD参数,惩罚系数,分解层数,matlab语言 ,最小包络熵为适应度函数。

蛙跳算法优化VMD参数&#xff0c;惩罚系数&#xff0c;分解层数&#xff0c;matlab语言 &#xff0c;最小包络熵为适应度函数。

粒子群算法(6)-----几个适应度评价函数

下面给出几个适应度评价函数&#xff0c;并给出图形表示 头几天机子种了病毒&#xff0c;重新安装了系统&#xff0c;不小心把程序全部格式化了&#xff0c;痛哭&#xff01;&#xff01;&#xff01;没办法&#xff0c;好多程序不见了&#xff0c;现在把这几个典型的函数重新编…

粒子群算法几个适应度评价函数

http://blog.csdn.net/niuyongjie/article/details/1619496 粒子群算法(6)-----几个适应度评价函数 标签&#xff1a; 算法图形function 2007-05-21 16:28 37960人阅读 评论(25) 收藏 举报 分类&#xff1a; 粒子群算法研究&#xff08;8&#xff09; 版权声明&#xff1…

遗传算法优化LSTM网络结构(实现自动根据适应度函数:即准确率来全局搜索最佳网络结构):主要被优化参数:网络层数,每层的神经元个数,全连接的层数,全连接层的神经元个数。代码有详细注解

代码视频链接:https://www.bilibili.com/video/BV19q4y1Q7DR/ 代码效果图: 1.优化参数 本文优化的是LSTM的层数参数和各层神经元参数,其中包含了lstm层和Dense层,其中我们规定了神经网络的层数不超过3层,每层的神经元个数在[32,256]之间。 2.注意事项 2.1.本文的遗传算…

粒子群算法的几个适应度评价函数

下面给出几个适应度评价函数&#xff0c;并给出图形表示 第一个函数&#xff1a;Griewank函数&#xff0c;图形如下所示&#xff1a; 适应度函数如下&#xff1a;&#xff08;为了求最大值&#xff0c;我去了所有函数值的相反数&#xff09; function y Griewank(x) % Griew…

【人工智能】人工智能二——遗传算法的基本概念遗传算法的基本算法(编码群体设定适应度函数选择交叉变异遗传算法步骤)解决带约束的函数优化问题多目标的遗传算法遗传算法的改进算法

人工智能二——遗传算法的基本概念&遗传算法的基本算法&#xff08;编码&群体设定&适应度函数&选择&交叉&变异&遗传算法步骤&#xff09;&解决带约束的函数优化问题&多目标的遗传算法&遗传算法的改进算法 遗传算法的基本概念遗传算法的…

【建模必备】遗传算法的基本原理与步骤(适应度函数与适应度分配)

如果喜欢这里的内容&#xff0c;你能够给我最大的帮助就是转发&#xff0c;告诉你的朋友&#xff0c;鼓励他们一起来学习。 If you like the content here, you can give me the greatest help is forwarding, tell your friends, encourage them to learn together.

2018-3-19 损失函数与适应度函数,稳定选择与分裂选择

1.适应度与损失函数 我觉的&#xff1a; &#xff08;1&#xff09;都是用来描述目标函数一个方面的效能的一个函数 &#xff08;2&#xff09;进行输入之后&#xff0c;结果都是一个可以进行比较的值 来源&#xff1a;机器学习之 损失函数和风险函数 - CSDN博客 http://bl…

遗传算法(2):对适应度函数的改进

Review&#xff1a; 基本遗传算法 ----------------------------- 关于适应度的问题 1. 有的时候&#xff0c;目标函数可能不一定可以直接作为适应度函数。 2. f(x1), f(x2), ... f(xN)之间的差别可能不是很大&#xff0c;个体被选出的概率差不多&#xff0c;这可能导致GA的选择…

遗传算法原理,交叉、变异、适应度函数的设置

遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;由霍兰德教授在20世纪70年代提出&#xff0c;是以自然选择和遗传变异为理论依据的全局性概率搜索优化算法模型。采用遗传算法寻优时需要将问题的候选解进行编码&#xff0c;即一个候选解对应一个编码&#xff…

利用遗传算法GA和粒子群算法PSO优化算法,将BP神经网络训练集的MSE作为适应度函数

利用遗传算法GA和粒子群算法PSO优化算法&#xff0c;将BP神经网络训练集的MSE作为适应度函数&#xff0c;获取最优的权值和阈值在反向输入到BP神经网络里构建回归预测模型&#xff0c;同时能够打印出模型的多个评价指标&#xff0c;具体效果可以看图 ID:3250669194443543Matl…

麻雀算法SSA,优化VMD,适应度函数为最小包络熵,包含MATLAB源代码

针对大家评论区给出的很多问题&#xff0c;作者一直都有关注&#xff0c;因此在这里又写了一篇文章&#xff0c;而且思路与这篇文章有不同之处&#xff0c;至于具体的不同之处放在下一篇文章了&#xff0c;大家感兴趣的可以移步观看&#xff0c;下一篇文章可以说是作者的呕心力…