当前位置: 首页 > news >正文

每日一题——LRU缓存机制的C语言实现详解

LRU缓存机制的C语言实现详解

    • 参考
    • 1. 数据结构设计
      • 双向链表节点
      • 哈希表节点
      • 哈希表
      • LRU缓存结构
    • 2. 初始化哈希表和双向链表
      • 哈希函数
      • 初始化哈希表
      • 初始化双向链表
      • 创建LRU缓存
    • 3. 更新双向链表
    • 4. 实现Get操作
    • 5. 实现Put操作
      • 更新节点值
      • 删除最久未使用节点
      • 插入或更新节点
    • 6. 释放缓存
      • 释放双向链表
      • 释放哈希表
      • 释放LRU缓存
    • 7. 完整代码及测试
      • 测试用例
      • 输出结果
    • 总结

参考

建议先参考下面的视频

在这里插入图片描述

1. 数据结构设计

双向链表节点

typedef struct DulNode {int key;           // 缓存项的键int value;         // 缓存项的值struct DulNode* pre;  // 前驱节点指针struct DulNode* next; // 后继节点指针
} DulNode;
  • 作用:维护缓存项的使用顺序,最近访问的节点靠近链表头部,未使用的节点靠近尾部。

哈希表节点

typedef struct HashTableNode {DulNode* node;          // 指向双向链表中的节点struct HashTableNode* next; // 处理哈希冲突的链表指针
} HashTableNode;
  • 作用:通过哈希表快速定位缓存项,键为key,值为对应的双向链表节点。

哈希表

typedef struct HashTable {int capacity;         // 哈希表容量(桶数量)hash_cal_f hash_func; // 哈希函数指针HashTableNode** bucket; // 桶数组(存储链表头节点)
} HashTable;
  • 作用:以O(1)时间复杂度查找键是否存在,结合双向链表实现LRU策略。

LRU缓存结构

typedef struct {int cur_node;       // 当前缓存中的节点数HashTable* hash_table; // 哈希表DulNode* head;      // 双向链表头节点(哨兵)DulNode* tail;      // 双向链表尾节点(哨兵)
} Solution;
  • 作用:整合哈希表和双向链表,封装LRU缓存的核心操作。

2. 初始化哈希表和双向链表

哈希函数

int hash_cal(int capacity, int val) {return val % capacity; // 简单取模哈希
}
  • 设计意图:将键值映射到哈希表的桶索引,均匀分布以减少冲突。

初始化哈希表

void InitHashTable(Solution* lruCache, int capacity) {HashTable* hash_table = malloc(sizeof(HashTable));hash_table->capacity = capacity;hash_table->hash_func = hash_cal;hash_table->bucket = calloc(capacity, sizeof(HashTableNode*));lruCache->hash_table = hash_table;
}
  • 关键点:动态分配桶数组并初始化为NULL,避免野指针问题。

初始化双向链表

void InitDoubleList(Solution* lruCache) {// 创建头尾哨兵节点并连接成环lruCache->head = (DulNode*)malloc(sizeof(DulNode));lruCache->tail = (DulNode*)malloc(sizeof(DulNode));lruCache->head->pre = lruCache->tail;lruCache->head->next = lruCache->tail;lruCache->tail->pre = lruCache->head;lruCache->tail->next = lruCache->head;
}
  • 设计优势:哨兵节点简化链表操作,无需处理头尾边界条件。

创建LRU缓存

Solution* SolutionCreate(int capacity) {Solution* lruCache = malloc(sizeof(Solution));lruCache->cur_node = 0;InitHashTable(lruCache, capacity);InitDoubleList(lruCache);return lruCache;
}
  • 流程:分配内存后,初始化哈希表和双向链表。

3. 更新双向链表

void DulLinkLinkUpdateNode(DulNode* head, DulNode* node) {if (node->pre == head) return; // 已在头部无需处理// 摘除节点node->pre->next = node->next;node->next->pre = node->pre;// 插入到头部node->pre = head;node->next = head->next;head->next->pre = node;head->next = node;
}
  • 作用:将节点移动到链表头部,表示最近被访问。

4. 实现Get操作

int SolutionGet(Solution* obj, int key) {if (obj->cur_node == 0) return -1;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];// 遍历哈希冲突链表while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {DulLinkLinkUpdateNode(obj->head, hash_node->node); // 更新链表return hash_node->node->value;}return -1;
}
  • 时间复杂度:O(1)(哈希表平均情况)。

5. 实现Put操作

更新节点值

void LRUCacheUpdateNode(Solution* obj, int key, int value) {// 查找并更新值,随后移动节点到头部int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);HashTableNode* hash_node = obj->hash_table->bucket[h_index];while (hash_node && hash_node->node->key != key) hash_node = hash_node->next;if (hash_node) {hash_node->node->value = value;DulLinkLinkUpdateNode(obj->head, hash_node->node);}
}

删除最久未使用节点

void LRUCacheDelLastNode(Solution* obj) {DulNode* del_node = obj->tail->pre; // 尾节点的前驱为LRU节点// 从哈希表中删除int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, del_node->key);HashTableNode *pre = NULL, *cur = obj->hash_table->bucket[h_index];while (cur && cur->node->key != del_node->key) {pre = cur;cur = cur->next;}if (cur) {if (pre) pre->next = cur->next;else obj->hash_table->bucket[h_index] = cur->next;free(cur);}// 从链表中删除del_node->pre->next = del_node->next;del_node->next->pre = del_node->pre;free(del_node);obj->cur_node--;
}

插入或更新节点

void SolutionPut(Solution* obj, int key, int value) {if (obj->cur_node >= obj->hash_table->capacity)LRUCacheDelLastNode(obj); // 缓存满时删除LRU节点if (SolutionGet(obj, key) != -1) { // Key存在则更新LRUCacheUpdateNode(obj, key, value);return;}// 创建新节点并插入链表头部DulNode* new_dul_node = malloc(sizeof(DulNode));new_dul_node->key = key;new_dul_node->value = value;new_dul_node->pre = obj->head;new_dul_node->next = obj->head->next;obj->head->next->pre = new_dul_node;obj->head->next = new_dul_node;// 插入哈希表HashTableNode* new_hash_node = malloc(sizeof(HashTableNode));new_hash_node->node = new_dul_node;int h_index = obj->hash_table->hash_func(obj->hash_table->capacity, key);new_hash_node->next = obj->hash_table->bucket[h_index];obj->hash_table->bucket[h_index] = new_hash_node; // 头插法obj->cur_node++;
}

6. 释放缓存

释放双向链表

void DulLinkLinkFree(DulNode* head) {DulNode* cur = head->next;while (cur != head) {DulNode* tmp = cur;cur = cur->next;free(tmp);}free(head->pre); // 释放尾节点free(head);
}

释放哈希表

void HashTableNodeFree(Solution* obj) {for (int i = 0; i < obj->hash_table->capacity; i++) {HashTableNode* cur = obj->hash_table->bucket[i];while (cur) {HashTableNode* tmp = cur;cur = cur->next;free(tmp);}}free(obj->hash_table->bucket);
}

释放LRU缓存

void SolutionFree(Solution* obj) {DulLinkLinkFree(obj->head);HashTableNodeFree(obj);free(obj->hash_table);free(obj);
}

7. 完整代码及测试

测试用例

int main() {Solution* cache = SolutionCreate(2);SolutionPut(cache, 1, 1);SolutionPut(cache, 2, 2);printf("Get(1) -> %d\n", SolutionGet(cache, 1)); // 1SolutionPut(cache, 3, 3); // 淘汰2printf("Get(2) -> %d\n", SolutionGet(cache, 2)); // -1SolutionFree(cache);return 0;
}

输出结果

Get(1) -> 1
Get(2) -> -1

总结

  • 核心机制:通过双向链表维护访问顺序,哈希表实现快速查找。
  • 时间复杂度GetPut操作均摊时间复杂度为O(1)。
  • 优化点:哈希表采用链地址法处理冲突,双向链表使用哨兵节点简化操作。
  • 适用场景:高频访问的缓存系统,需快速淘汰最久未使用数据。
    反正以我的能力远远不能解决问题。还是只能勉强把代码看懂。这题还是很难得,感觉没有一天时间,完全搞不定。放弃了,放弃了。

相关文章:

每日一题——LRU缓存机制的C语言实现详解

LRU缓存机制的C语言实现详解 参考1. 数据结构设计双向链表节点哈希表节点哈希表LRU缓存结构 2. 初始化哈希表和双向链表哈希函数初始化哈希表初始化双向链表创建LRU缓存 3. 更新双向链表4. 实现Get操作5. 实现Put操作更新节点值删除最久未使用节点插入或更新节点 6. 释放缓存释…...

Leetcode3162:优质数对的总数 I

题目描述&#xff1a; 给你两个整数数组 nums1 和 nums2&#xff0c;长度分别为 n 和 m。同时给你一个正整数 k。 如果 nums1[i] 可以除尽 nums2[j] * k&#xff0c;则称数对 (i, j) 为 优质数对&#xff08;0 < i < n - 1, 0 < j < m - 1&#xff09;。 返回 优…...

docker安装etcd:docker离线安装etcd、docker在线安装etcd、etcd镜像下载、etcd配置详解、etcd常用命令、安装常见问题总结

官方网站 官方网址&#xff1a;etcd 二进制包下载&#xff1a;Install | etcd GitHub社区项目&#xff1a;etcd-io GitHub GitHub社区项目版本历史&#xff1a;Releases etcd-io/etcd GitHub 一、镜像下载 1、在线下载 在一台能连外网的linux上执行docker镜像拉取命令…...

Apache SeaTunnel 构建实时数据同步管道(最新版)

文章作者 王海林 白鲸开源 数据集成引擎研发 Apache SeaTunnel Committer & PMC Member&#xff0c;Apache SkyWalking Committer&#xff0c;多年平台研发经验&#xff0c;目前专注于数据集成领域。 导读 在当今数字化快速发展的时代&#xff0c;数据已然成为企业决策…...

递归、搜索与回溯第二讲:二叉树中的深搜 穷举vs暴搜vs深搜vs回溯vs剪枝

递归、搜索与回溯第二讲&#xff1a;二叉树中的深搜 && 穷举vs暴搜vs深搜vs回溯vs剪枝 1.计算布尔二叉树的值2.求根节点到叶结点数字之和3.二叉树剪枝4.验证二叉搜索树5.二叉搜索树中第K小的元素6.二叉树的所有路径7.全排列8.子集 1.计算布尔二叉树的值 2.求根节点到叶…...

Hbase分布式——储存机制

说明&#xff1a; 客户端调用&#xff0c;到达zk。然后到大HMaster&#xff08;主节点可以有多个但是只有和active在一起的才有效。&#xff09;。然后找到一个HRegionServer&#xff08;从节点可以有多个&#xff09;去做保存操作。 每一个HRegionServer上管理着表的HRegion…...

Word表格中如何只单独调整某一单元格宽度

大家好&#xff0c;我是小鱼。 在日常制作Word表格时&#xff0c;表格中不同单元格有时需要设置不同的宽度&#xff0c;但是很多小伙伴会发现想单独调整某一个单元格宽度时&#xff0c;发现其它单元格宽度也会发生变化。那么&#xff0c;到底怎么才能单独调整某一单元格宽度呢…...

Build错误:Cannot determine build data storage root for project 和 无法加载主类的解决办法的经验分享

Build错误&#xff1a;Cannot determine build data storage root for project 解决方案与经验分享 1. 引言 查看错误信息 “Cannot determine build data storage root for project”的含义&#xff1a; 这是一个关于构建项目时遇到的常见错误。错误信息表明构建工具无法确定…...

【Springboot知识】Logback从1.2.x升级到1.3.x需要注意哪些点?

文章目录 **1. 确认依赖版本**示例依赖配置&#xff08;Maven&#xff09;&#xff1a; **2. 处理 StaticLoggerBinder 的移除**解决方案&#xff1a; **3. 修改日志配置文件**示例 logback.xml 配置&#xff1a; **4. 检查兼容性问题**Spring Boot 2.x 的兼容性解决方案&#…...

大语言加持的闭环端到端自动驾驶模型 学习笔记纯干货

LMDrive&#xff1a;大语言模型辅助闭环端到端 LMDrive&#xff1a;大语言模型辅助闭环端到端 背景框架输入部分&#xff1a;导航指令&#xff1a;视觉数据&#xff1a;提示指令&#xff08;可选&#xff09;&#xff1a;处理部分&#xff1a;输出部分&#xff1a; 视觉编码器…...

初阶数据结构(C语言实现)——2算法的时间复杂度和空间复杂度

目录 本节目标1. 算法效率1.1 如何衡量一个算法的好坏1.2 算法的复杂度 2.时间复杂度2.1 时间复杂度的概念2.1.1 入门习题2.1.2 进阶习题 2.2 常见时间复杂度 3. 空间复杂度3.1 常见空间复杂度 本节目标 算法效率时间复杂度空间复杂度常见时间复杂度以及复杂度oj练习 1. 算法…...

MySQL知识

1.Navicat客户端连接 打开navicat&#xff0c;点击连接&#xff0c;点击MySQL 输入连接名与密码&#xff0c;如果连接的mysql是windows下的mysql主机号就填写localhost 填写好后点击测试连接 点击确定&#xff0c;mysql连接navicat成功 2.MySQL数据定义语言(DDL) DDL用于数据库…...

【前端定位线上问题的多种方案(不依赖 Sentry)】

前端定位线上问题的多种方案&#xff08;不依赖 Sentry&#xff09; &#x1f6e0;️ 一、构建时注入调试信息 &#x1f527; 1. 注入版本信息与 Git 提交哈希 Webpack 配置&#xff1a; // webpack.config.js const webpack require(webpack); const gitRevision require(…...

怎么修改node_modules里的文件,怎么使用patch-package修改node_modules的文件,怎么修改第三方库原文件。

在开发中会遇到需要node_modules里第三方库有bug&#xff0c;然后需要修改node_modules文件的情况 使用patch-package包可以修改node_modules里的文件 patch-package npm 官网&#xff1a;patch-package - npm 安装 npm i patch-package 修改文件后 npx patch-package s…...

muduo网络库2

Muduo网络库&#xff1a;底层实质上为Linux的epoll pthread线程池&#xff0c;且依赖boost库。 muduo的网络设计核心为一个线程一个事件循环&#xff0c;有一个main Reactor负载accept连接&#xff0c;然后把连接分发到某个sub Reactor(采用轮询的方式来选择sub Reactor)&…...

什么是DrawCall?DrawCall为什么会影响游戏运行效率?如何减少DrawCall?

目录 1 什么是DrawCall&#xff1f; 2 DrawCall为什么会影响游戏运行效率&#xff1f; 3 如何减少 DrawCall&#xff1f;&#xff08;结合性能分析工具&#xff09; 1 什么是DrawCall&#xff1f; DrawCall&#xff08;绘制调用&#xff09; 是 GPU 的一个指令&#xff0c…...

LabVIEW电能质量分析软件

随着电力系统的复杂性增加&#xff0c;电能质量问题日益突出&#xff0c;传统的电能质量检测装置多采用DSP技术&#xff0c;不仅开发周期长、功能单一&#xff0c;而且在多功能集成方面存在局限性。基于LabVIEW虚拟仪器开发平台的电能质量分析软件利用FFT、STFT、WT、HHT等多种…...

【十二】Golang 映射

&#x1f4a2;欢迎来到张胤尘的开源技术站 &#x1f4a5;开源如江河&#xff0c;汇聚众志成。代码似星辰&#xff0c;照亮行征程。开源精神长&#xff0c;传承永不忘。携手共前行&#xff0c;未来更辉煌&#x1f4a5; 文章目录 映射映射的定义映射初始化make 函数使用字面量 源…...

PHP商协会管理系统小程序源码

&#x1f4ca; 商协会管理系统 &#x1f4bb; 这是一款基于ThinkPHPUniapp框架&#xff0c;经过深度定制与匠心打造的商协会系统&#xff0c;被誉为商协会领域数字化运营管理的新锐之星。它以“智慧化会员体系、智敏化内容运营、智能化活动构建”为三大核心动力源&#xff0c;…...

React进阶之React核心源码解析(三)

React核心源码解析 diff多节点比较diff两轮遍历比较第一轮比较第二轮比较Update 状态更新Concurrent Modediff 多节点比较diff isArray方法比较 节点更新// 更新前 <ul><li key="0" className="before">0<li><li key=...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

论文阅读:Matting by Generation

今天介绍一篇关于 matting 抠图的文章&#xff0c;抠图也算是计算机视觉里面非常经典的一个任务了。从早期的经典算法到如今的深度学习算法&#xff0c;已经有很多的工作和这个任务相关。这两年 diffusion 模型很火&#xff0c;大家又开始用 diffusion 模型做各种 CV 任务了&am…...

机器学习的数学基础:线性模型

线性模型 线性模型的基本形式为&#xff1a; f ( x ) ω T x b f\left(\boldsymbol{x}\right)\boldsymbol{\omega}^\text{T}\boldsymbol{x}b f(x)ωTxb 回归问题 利用最小二乘法&#xff0c;得到 ω \boldsymbol{\omega} ω和 b b b的参数估计$ \boldsymbol{\hat{\omega}}…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

UE5 音效系统

一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类&#xff0c;将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix&#xff0c;将上述三个类翻入其中&#xff0c;通过它管理每个音乐…...