手撕 LFU 缓存

大家好，我是 方圆。LFU 的缩写是 Least Frequently Used，简单理解则是将使用最少的元素移除，如果存在多个使用次数最小的元素，那么则需要移除最近不被使用的元素。LFU 缓存在 LeetCode 上是一道困难的题目，实现起来并不容易，所以决定整理和记录一下。如果大家想要找刷题路线的话，可以参考 Github: LeetCode。

LFU 缓存

LeetCode 原题：460. LFU 缓存 困难。

思路：我们需要维护两个 HashMap，分别为 keyNodeMap 和 accessNodeMap，它们的职责如下：

  • keyNodeMap: key 为 put 的值的 key 值，value 为该 key 对应的节点，那么我们便可以通过这个 map 以 O(1) 的时间复杂度 get 到对应的值

  • accessNodeMap: key 为访问次数，各个节点被 put 和 get 都会使节点 accessNum 访问次数加 1，value 为该访问次数下的 循环双向链表的头节点，通过双向链表我们能以 O(1) 的时间复杂度将节点移除。我们定义 在相同访问次数下，越早插入的节点越靠近双向链表的尾端，在进行节点移除时，会将尾节点移除。

为了更好的理解两个 map 与链表节点的关系，我们用下图对容量为 3 的缓存进行表示，其中绿色代表链表节点，节点中各个值对应的字段为 key, value, accessNum

lfu.png

除此之外，我们要定义一个 minAccessNum 的字段来维护当前缓存中最小的访问次数，这样我们就能够在时间复杂度为 O(1) 的情况下在 accessNodeMap 中获取到对应访问次数的双向链表。

大致的方向确定了，我们需要再想一下具体的实现：

get 方法：我们首先去 keyNodeMap 中拿，没有的话返回 -1 即可。如果有对应的 key 的话，那么我们需要将对应节点的访问次数加 1，并需要改变它所在 accessNodeMap 中的位置：首先需要断开它与原链表的连接，之后加入到新的链表中，如果在 accessNodeMap 中有对应次数的链表，那么我们需要把它插入到该链表的 头节点；如果没有对应访问次数的双向链表的话，我们需要创建该访问次数的链表，并以该节点为头节点，维护在 accessNodeMap 中。这里需要注意，我们要对 minAccessNum 进行 更新，如果该节点的访问次数和 minAccessNum 相等，并且该节点在原来链表删除后，该访问次数下的链表中不存在其他任何节点，那么 minAccessNum 也要加 1。

put 方法：我们同样也需要在 keyNodeMap 中判断是否存在，存在的话需要将值进行覆盖，之后的处理逻辑与 get 方法一致。如果不存在的话，我们这里需要判断缓存的容量 是否足够，足够的话比较简单，先将其 put 到 keyNodeMap 中，再在 accessNodeMap 中将其插入到 key 为 1 的双向链表的头节点即可，这里要注意更改 minAccessNum 为 1，因为新插入的节点一定是访问次数最少的；如果不够的话那么先要 将最少使用的节点移除（在两个 map 中都要移除），在 accessNodeMap 中进行移除时，需要根据 minAccessNum 获取对应的双向链表，移除它的尾节点。在尾节点移除完之后，执行的逻辑和上述容量足够时执行插入节点的逻辑一致。

具体实现已经比较清楚了，直接上代码吧，大家可以关注一下注释信息：

class LFUCache {/*** 双向链表节点*/static class Node {Node left;Node right;int key;int value;int accessNum;public Node(int key, int value, int accessNum) {this.key = key;this.value = value;this.accessNum = accessNum;}}private HashMap<Integer, Node> keyNodeMap;private HashMap<Integer, Node> accessNodeMap;private int minAccessNum;private int capacity;public LFUCache(int capacity) {keyNodeMap = new HashMap<>(capacity);accessNodeMap = new HashMap<>(capacity);minAccessNum = 0;this.capacity = capacity;}public int get(int key) {if (keyNodeMap.containsKey(key)) {Node node = keyNodeMap.get(key);// 如果所在链表只有一个节点的话，那么直接将该访问次数的链表删掉if (node == node.right) {accessNodeMap.remove(node.accessNum);// 维护缓存中最小的访问次数if (minAccessNum == node.accessNum) {minAccessNum++;}} else {// 断开与原链表的连接node.left.right = node.right;node.right.left = node.left;// 如果该节点是头节点的话，那么需要替换为它的下一个节点作为头节点if (node == accessNodeMap.get(node.accessNum)) {accessNodeMap.put(node.accessNum, node.right);}}// 增加后的访问次数链表看看有没有node.accessNum++;if (accessNodeMap.containsKey(node.accessNum)) {Node target = accessNodeMap.get(node.accessNum);// 插入头节点insertHead(node, target);} else {// 没有的话，直接 put 即可accessNodeMap.put(node.accessNum, node);// 单节点循环链表node.left = node;node.right = node;}return node.value;} else {return -1;}}public void put(int key, int value) {if (keyNodeMap.containsKey(key)) {Node node = keyNodeMap.get(key);node.value = value;// 执行get方法get(key);} else {Node node = new Node(key, value, 1);if (keyNodeMap.size() == capacity) {// 容量不够需要将最少使用的节点移除Node oldNodeHead = accessNodeMap.get(minAccessNum);Node tail = oldNodeHead.left;// 如果所在链表只有一个节点的话，那么直接将该访问次数的链表删掉if (tail.right == tail) {accessNodeMap.remove(tail.accessNum);} else {// 断开与原链表的连接tail.left.right = tail.right;tail.right.left = tail.left;// 如果该节点是头节点的话，那么需要替换为它的下一个节点作为头节点if (oldNodeHead == accessNodeMap.get(tail.accessNum)) {accessNodeMap.put(tail.accessNum, tail.right);}}keyNodeMap.remove(tail.key);}// 这样就有有足够的容量了keyNodeMap.put(key, node);// 是否有对应的链表if (accessNodeMap.containsKey(node.accessNum)) {// 插入头节点insertHead(node, accessNodeMap.get(node.accessNum));} else {// 没有对应的链表 直接插入accessNodeMap.put(node.accessNum, node);node.left = node;node.right = node;}minAccessNum = 1;}}private void insertHead(Node node, Node target) {// 拼接到该链表头，并构建循环双向链表node.right = target;node.left = target.left;target.left.right = node;target.left = node;// 覆盖头节点accessNodeMap.put(node.accessNum, node);}}

需要注意的是：

  1. 因为我们维护的是循环双向链表，所以在插入头节点时注意尾节点和头节点的引用关系

  2. 因为我们在 accessNodeMap 中维护的是头节点，所以当我们将链表的头结点进行移除时，需要将头节点的下一个节点作为新的头节点保存在 accessNodeMap 中

针对第二点我们可以做一个优化，每当第一次生成双向链表的时候，我们创建一个哨兵节点作为头节点，那么这样我们就无需在头节点被移除后再将新的头节点插入 accessNodeMap 中进行覆盖了，始终保持 accessNodeMap 中 value 值保存的是哨兵节点，最终代码如下：

class LFUCache {/*** 双向链表节点*/static class Node {int key, value;Node pre, next;int accessNum;public Node(int key, int value, int accessNum) {this.key = key;this.value = value;this.accessNum = accessNum;}}/*** 记录访问最小的值*/private int minAccessNum;private final int capacity;private final HashMap<Integer, Node> accessNodeMap;private final HashMap<Integer, Node> keyNodeMap;public LFUCache(int capacity) {this.capacity = capacity;accessNodeMap = new HashMap<>(capacity);keyNodeMap = new HashMap<>(capacity);// 初始化访问次数为 1 的哨兵节点minAccessNum = 1;accessNodeMap.put(minAccessNum, initialSentinelNode(minAccessNum));}public int get(int key) {if (keyNodeMap.containsKey(key)) {Node node = keyNodeMap.get(key);// 找到新的位置insertIntoNextSentinel(node);return node.value;}return -1;}public void put(int key, int value) {if (keyNodeMap.containsKey(key)) {Node node = keyNodeMap.get(key);node.value = value;insertIntoNextSentinel(node);} else {if (keyNodeMap.size() == capacity) {// 移除最老的节点removeEldest();}// 新加进来的肯定是最小访问次数 1minAccessNum = 1;Node newNode = new Node(key, value, minAccessNum);// 插入到头节点insertIntoHead(newNode, accessNodeMap.get(minAccessNum));keyNodeMap.put(key, newNode);}}/*** 插入下一个链表中*/private void insertIntoNextSentinel(Node node) {// 在原来的位置移除remove(node);// 尝试更新 minAccessNumtryToIncreaseMinAccessNum(node.accessNum++);// 获取增加 1 后的哨兵节点Node nextCacheSentinel = getSpecificAccessNumSentinel(node.accessNum);// 插入该链表的头节点insertIntoHead(node, nextCacheSentinel);}/*** 在原链表中移除*/private void remove(Node node) {node.pre.next = node.next;node.next.pre = node.pre;node.next = null;node.pre = null;}/*** 尝试更新 minAccessNum*/private void tryToIncreaseMinAccessNum(int accessNum) {// 原访问次数的哨兵节点Node originSentinel = accessNodeMap.get(accessNum);// 如果只剩下哨兵节点的话，需要看看需不需要把 minAccessNum 增加 1if (originSentinel.next == originSentinel && originSentinel.accessNum == minAccessNum) {minAccessNum++;}}/*** 获取指定访问次数的哨兵节点*/private Node getSpecificAccessNumSentinel(int accessNum) {if (accessNodeMap.containsKey(accessNum)) {return accessNodeMap.get(accessNum);} else {// 没有的话得初始化一个Node nextCacheSentinel = initialSentinelNode(accessNum);accessNodeMap.put(accessNum, nextCacheSentinel);return nextCacheSentinel;}}/*** 生成具体访问次数的哨兵节点*/private Node initialSentinelNode(int accessNum) {Node sentinel = new Node(-1, -1, accessNum);// 双向循环链表sentinel.next = sentinel;sentinel.pre = sentinel;return sentinel;}/*** 插入头节点*/private void insertIntoHead(Node node, Node nextCacheSentinel) {node.next = nextCacheSentinel.next;nextCacheSentinel.next.pre = node;nextCacheSentinel.next = node;node.pre = nextCacheSentinel;}/*** 如果容量满了的话，需要把 minAccessNum 访问次数的尾巴节点先移除掉*/private void removeEldest() {Node minSentinel = accessNodeMap.get(minAccessNum);Node tail = minSentinel.pre;tail.pre.next = tail.next;minSentinel.pre = tail.pre;keyNodeMap.remove(tail.key);}
}

巨人的肩膀

  • LFU 缓存官方题解

  • 【宫水三叶】运用「桶排序」&「双向链表」实现 LFUCache

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/137780.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

C语言指针笔试题讲解

C语言指针笔试题讲解

大家好&#xff0c;我们来学习一些C语言的指针笔试题。对于C语言指针的模块想必大家都非常的头疼吧&#xff0c;那么我们就来就来看看一些关于C语言指针的笔试题。 首先让我们看到我们今天的第一题。 int main() { int a[5] { 1, 2, 3, 4, 5 }; int *ptr (int *)(&a 1)…
阅读更多...
AI AIgents时代-（四.）应用上手

AI AIgents时代-（四.）应用上手

HuggingGPT & MetaGPT . &#x1f7e2; HuggingGPT HuggingGPT是一个多模型调用的 Agent 框架&#xff0c;利用 ChatGPT 作为任务规划器&#xff0c;根据每个模型的描述来选择 HuggingFace 平台上可用的模型&#xff0c;最后根据模型的执行结果生成总结性的响应。 这个项…
阅读更多...
Cesium 地球(2)-瓦片创建

Cesium 地球(2)-瓦片创建

Cesium 地球(2)-瓦片创建 QuadtreePrimitive代码执行4个步骤: step1: update()step2: beginFrame()step3: render()step4: endFrame() 但并不是瓦片的创建步骤。 1、创建 QuadtreeTile 基于 step3: render() step3: render()┖ selectTilesForRendering()在 selectTilesFo…
阅读更多...
循环神经网络-简洁实现

循环神经网络-简洁实现

参考&#xff1a; https://zh-v2.d2l.ai/chapter_recurrent-neural-networks/rnn-concise.html https://pytorch.org/docs/stable/generated/torch.nn.RNN.html?highlightrnn#torch.nn.RNN RNN import torch from torch import nn from torch.nn import functional as F from…
阅读更多...
排序算法：归并排序（递归和非递归）

排序算法：归并排序（递归和非递归）

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关排序算法的相关知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通…
阅读更多...
什么是ELK

什么是ELK

什么是ELK ELK 并不是一个技术框架的名称&#xff0c;它其实是一个三位一体的技术名词&#xff0c;ELK 的每个字母都来自一个技术组件&#xff0c;分别是 Elasticsearch&#xff08;简称 ES&#xff09;、Logstash 和 Kibana。 三个技术组件是独立的&#xff0c;后两个被elast…
阅读更多...
table 写表格

table 写表格

<!-- colspan"3" 合并3列 --> <!-- rowspan"4" 合并4行 --> <!-- 7行4列 --><table><tr><th>企业名称</th><td>2020.11.11</td><th>法定代表人</th><td>2020.11.11</td>&l…
阅读更多...
Nginx替代产品-Tengine健康检测

Nginx替代产品-Tengine健康检测

1、官网地址 官网地址&#xff1a;The Tengine Web Server 文档地址&#xff1a;文档 - The Tengine Web Server 健康检测模块&#xff1a;ngx_http_upstream_check_module - The Tengine Web Server 2、安装 下载 wget https://tengine.taobao.org/download/tengine-3.…
阅读更多...
如何使用ArcGIS Pro提取河网水系

如何使用ArcGIS Pro提取河网水系

DEM数据除了可以看三维地图和生成等高线之外&#xff0c;还可以用于水文分析&#xff0c;这里给大家介绍一下如何使用ArcGIS Pro通过水文分析提取河网水系&#xff0c;希望能对你有所帮助。 数据来源 本教程所使用的数据是从水经微图中下载的DEM数据&#xff0c;除了DEM数据&a…
阅读更多...
PASCAL VOC2012数据集详细介绍

PASCAL VOC2012数据集详细介绍

PASCAL VOC2012数据集详细介绍 0、数据集介绍2、Pascal VOC数据集目标类别3、 数据集下载与目录结构4、目标检测任务5、语义分割任务6、实例分割任务7、类别索引与名称对应关系 0、数据集介绍 2、Pascal VOC数据集目标类别 在Pascal VOC数据集中主要包含20个目标类别&#xff…
阅读更多...
初见QT，控件的基本应用，实现简单登录窗口

初见QT，控件的基本应用，实现简单登录窗口

窗口实现代码 #include "widget.h"Widget::Widget(QWidget *parent): QWidget(parent) {//窗口设置this->setFixedSize(538, 373); //固定窗口大小this->setWindowIcon(QIcon("G:\\QT_Icon\\windos_icon2.png"))…
阅读更多...
线性代数基础-行列式

线性代数基础-行列式

一、行列式之前的概念 1.全排列&#xff1a; 把n个不同的元素排成一列&#xff0c;称为n个元素的全排列&#xff0c;简称排列 &#xff08;实际上就是我们所说的排列组合&#xff0c;符号是A&#xff0c;arrange&#xff09; 2.标准序列&#xff1a; 前一项均小于后一项的序列…
阅读更多...
微博情绪分类

微博情绪分类

引自&#xff1a;https://blog.csdn.net/no1xiaoqianqian/article/details/130593783 友好借鉴&#xff0c;总体抄袭。 所需要的文件如下&#xff1a;https://download.csdn.net/download/m0_37567738/88340795 import os import torch import torch.nn as nn import numpy a…
阅读更多...
32:TX Text Control ActiveX/ASP.NET/WinForms/WPF Crack

32:TX Text Control ActiveX/ASP.NET/WinForms/WPF Crack

TX Text Control ActiveX 32.0 添加操作“普通”样式表的能力。 2023 年 9 月 14 日 - 15:38新版本 特征 脚注- 在文档中插入与 Microsoft Word 兼容的脚注。脚注是一种文字处理功能&#xff0c;允许用户在页面底部插入附加信息。 可编辑的[普通]样式表- 添加了操作[普通]样式的…
阅读更多...
9.20号作业实现钟表

9.20号作业实现钟表

1.widget.h #include <QPainter> //画家 #include <QTimerEvent> #include <QTime> #include<QTimer> //定时器类QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Wid…
阅读更多...
物联网网络安全：保护物理世界和数字世界的融合

物联网网络安全：保护物理世界和数字世界的融合

我们正在见证数字技术如何成为我们日常生活和经济系统的一部分&#xff0c;从而提高福利并增强竞争力。尽管如此&#xff0c;新的尖端互联技术的迅速出现和采用也对政府、企业和整个社会构成了重大威胁。 长期以来&#xff0c;网络安全威胁一直是电影行业的一个现成的灵感来源&…
阅读更多...
el-table表格中加入输入框

el-table表格中加入输入框

<template><div class"box"><div class"btn"><el-button type"primary">发送评委</el-button><el-button type"primary" click"flag true" v-if"!flag">编辑</el-button…
阅读更多...
RFID技术在仓储物流供应链管理中的应用

RFID技术在仓储物流供应链管理中的应用

仓储物流供应链管理的透明度和库存周转率成为管控的重点&#xff0c;为了提高仓储物流的效率和减少库存损失&#xff0c;RFID技术被广泛应用于仓储、分发、零售管理等各个环节&#xff0c;为供应链管理带来了巨大的改变和提升。 首先&#xff0c;采用RFID技术进行仓库物流智能化…
阅读更多...
Jenkins “Trigger/call builds on other project“用法及携带参数

Jenkins “Trigger/call builds on other project“用法及携带参数

1.功能 “Trigger/call builds on other project” 功能是 Jenkins 中的一个特性&#xff0c;允许您在某个项目的构建过程中触发或调用另一个项目的构建。 当您在 Jenkins 中启用了 “Trigger/call builds on other project” 功能并配置了相应的触发条件后&#xff0c;当主项…
阅读更多...
（三十二）大数据实战——Maxwell安装部署及其应用案例实战

（三十二）大数据实战——Maxwell安装部署及其应用案例实战

前言 Maxwell是一个开源的MySQL数据库binlog解析工具&#xff0c;用于将MySQL数据库的binlog转换成易于消费的JSON格式&#xff0c;并通过Kafka、RabbitMQ、Kinesis 等消息队列或直接写入文件等方式将其输出。本节内容主要介绍如何安装部署Maxwell以及如何使用Maxwell完成数据…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023